login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A262500 Number of binary, minimal instances of Zimin word Z_n that begin with 0. 1
1, 3, 1751 (list; graph; refs; listen; history; text; internal format)
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
D. Rorabaugh, Toward the Combinatorial Limit Theory of Free Words, University of South Carolina, ProQuest Dissertations Publishing (2015). See section 2.3.
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.
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
Sequence in context: A346653 A258720 A262652 * A290944 A116994 A367542
KEYWORD
nonn,bref,hard,more
AUTHOR
Danny Rorabaugh, Sep 24 2015
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 02:23 EDT 2024. Contains 371264 sequences. (Running on oeis4.)