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