A262500 Number of binary, minimal instances of Zimin word Z_n that begin with 0.

1, 3, 1751

Offset: 1

Author

Danny Rorabaugh, Sep 24 2015

Keywords

• nonn
• bref
• hard
• more

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.

Examples

			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.
		

Links

• D. Rorabaugh, Toward the Combinatorial Limit Theory of Free Words, University of South Carolina, ProQuest Dissertations Publishing (2015). See section 2.3.
• Danny Rorabaugh, Binary, minimal Z_3-instances that begin with 0
• W. Rytter, and A. Shur, Searching for Zimin patterns, Theoretical Comp. Sci., 571 (2015), 50-57. [Preprint: On Searching Zimin Patterns (2014). See section 4.2.]
• A. I. Zimin, Blokirujushhie mnozhestva termov (Russian), Mat. Sbornik, 119 (1982), 363-375; Blocking sets of terms (English), Math. USSR-Sbornik, 47 (1984), 353-364.

Crossrefs

Cf. A123121, A262312, A262313.