Ternary analogue of A094913?

Jonathan Post jvospost3 at gmail.com
Sun Dec 9 00:51:45 CET 2007


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





More information about the SeqFan mailing list