|
|
A262500
|
|
Number of binary, minimal instances of Zimin word Z_n that begin with 0.
|
|
1
|
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
Zimin words are defined recursively by Z_1 = x_1, Z_{n+1} = Z_nx_{n+1}Z_n. Using a different alphabet: Z_1 = a, Z_2 = aba, Z_3 = abacaba, ... .
Word W over alphabet L is an instance of Z_n provided there exists a nonerasing monoid homomorphism f:{x_1,...,x_n}*->L* such that f(W)=Z_n. For example "abracadabra" is an instance of Z_2 via the homomorphism defined by f(x_1)=abra, f(x_2)=cad.
An instance W is minimal if no proper substring of W is also an instance.
The total number of minimal Z_n-instances over the alphabet {0,1} is 2*a(n).
The minimal, binary Z_3-instances have lengths ranging from 7 to 25. There exist minimal, binary Z_4-instances over 10000 letters long.
|
|
LINKS
|
|
|
EXAMPLE
|
The a(1)=1 instance of Z_1 is '0'.
The a(2)=3 instances of Z_2 are '000', '010', and '0110'. '01110' is not a minimal instance because it contains Z_2-instance '111' as a proper subword.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,bref,hard,more
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|