Ternary analogue of A094913?

[Maximilian Hasler]

If you go on to base 3, then the door is open to do it in any base... :-( !

Also, I don't understand why the empty substring is not counted
without any comment on that. AFAIK, in any context (programming
language, theory of monoids...) the empty string is always considered
as a string.
If the empty string is counted, then A094913_new(n) = A006697(n)
(cf. Jovovic's conjecture)

M.H.


On Dec 8, 2007 7:51 PM, Jonathan Post <jvospost3 at gmail.com> wrote:
> What is the ternary analogue of  A094913 Maximum number of distinct
> substrings of any binary string of length n?
>
> a(n) = Maximum number of distinct substrings of any ternary string of length n.
>
> Cf. A007089  Numbers in base 3.
>
> By hand, it seems to begin:
>
> n   a(n)  example
> 1   1       either 1 or 2 has only itself as substring
> 2   3       12 contains 1, 2, 12
> 3   6       120 contains 1, 2, 0, 12, 20, 120
> 4   9       1201 contains 1,2,0,12,20,01,120,201,1201
> 5   13     12010 has 1,2,0,12,20,01,10,120,201,010,1201,2010,12010
> 6   18     120102 has 1,2,0,12,20,01,10,02,120,201,010,102,1201,2010,0102,12010,
> 20102,120102
> 7  24?
>
> This is related to squarefree ternary words, cf.A006156.
>
> It seems clear that A094913(n) <= a(n) <= A006156(n).
>
> How many times is each maximum achieved?
>
> Is it mere coincidence that the first 7 valkues (if I even got those
> right) coincide with the first 7 values of A005488  Maximal number of
> edges in a b^{hat} graceful graph with n nodes, and with A132352
> Partial sums of A132351.?
>
> Or am I missing something even more obvious.
>
> Best,
>
> Jonathan Vos Post
>