login
A262313
Decimal expansion of the limit of the probability that a random binary word is an instance of the Zimin pattern "abacaba" as word length approaches infinity.
3
1, 1, 9, 4, 4, 3, 6, 9, 5, 2, 5, 2, 8, 6, 3, 3, 7, 3, 0, 0, 0, 1, 1, 8, 5, 8, 6, 1, 2, 6, 8, 8, 5, 1, 0, 4, 8, 1, 5, 9, 0, 7, 9, 8, 8, 8, 1, 6, 8, 0, 8, 3, 3, 0, 8, 6, 3, 0, 6, 5, 2, 2, 2, 0, 2, 8, 9, 1, 4, 4, 5, 5, 9, 4, 2, 1, 0, 7, 7, 6, 1, 0, 7, 2
OFFSET
0,3
COMMENTS
Word W over alphabet L is an instance of "abacaba" provided there exists a nonerasing monoid homomorphism f:{a,b,c}*->L* such that f(W)=abacaba. For example "01011010001011010" is an instance of "abacaba" via the homomorphism defined by f(a)=010, f(b)=11, f(c)=0. For a proof of the formula or more information on Zimin words, see Rorabaugh (2015).
LINKS
D. Rorabaugh, Toward the Combinatorial Limit Theory of Free Words, University of South Carolina, ProQuest Dissertations Publishing (2015). See section 5.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.
FORMULA
The constant is Sum_{n=1..infinity} A003000(n)*(Sum_{i=0..infinity} G_n(i)+H_n(i)), with:
G_n(i) = (-1)^i * r_n((1/2)^(2*2^i)) * (Product_{j=0..i-1} s_n((1/2)^(2*2^j))) / (Product_{k=0..i} 1-2*(1/2)^(2*2^k)),
r_n(x) = 2*x^(2n+1) - x^(4n) + x^(5n) - 2*x^(5n+1) + x^(6n),
s_n(x) = 1 - 2*x^(1-n) + x^(-n);
H_n(i) = (-1)^i * u_n((1/2)^(2*2^i)) * (Product_{j=0..i-1} v_n((1/2)^(2*2^j))) / (Product_{k=0..i} 1-2*(1/2)^(2*2^k)),
u_n(x) = 2*x^(4n+1) - x^(5n) + 2*x^(5n+1) + x^(6n),
v_n(x) = 1 - 2*x^(1-n) + x^(-n) - 2*x^(1-2n) + x^(-2n).
The inside sum is an alternating series and the outside sum has positive terms and a simple tail bound. Consequentially, we have the following bounds with any positive integers N and K:
Lower bound, Sum_{n=1..N} A003000(n)*(Sum_{i=0..2K-1} G_n(i)+H_n(i));
Upper bound, (1/2)^N + Sum_{n=1..N} A003000(n)*(Sum_{i=0..2K} G_n(i)+H_n(i)).
EXAMPLE
The constant is 0.11944369525286337300011858612688510481590798881680833086306522202891445594210776107239...
CROSSREFS
Cf. A003000, A123121, A262312 (aba).
Sequence in context: A193712 A249600 A375274 * A097878 A173571 A275915
KEYWORD
nonn,cons
AUTHOR
Danny Rorabaugh, Sep 17 2015
STATUS
approved