A262313 - OEIS

%I #32 Sep 27 2015 10:30:54

%S 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,

%T 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,

%U 4,4,5,5,9,4,2,1,0,7,7,6,1,0,7,2

%N 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.

%C 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).

%H Danny Rorabaugh, <a href="/A262313/b262313.txt">Table of n, a(n) for n = 0..185</a>

%H D. Rorabaugh, <a href="http://arxiv.org/abs/1509.04372">Toward the Combinatorial Limit Theory of Free Words</a>, University of South Carolina, ProQuest Dissertations Publishing (2015). See section 5.2.

%H A. I. Zimin, <a href="http://mi.mathnet.ru/msb2889">Blokirujushhie mnozhestva termov</a> (Russian), Mat. Sbornik, 119 (1982), 363-375; <a href="http://mi.mathnet.ru/eng/msb2889">Blocking sets of terms</a> (English), Math. USSR-Sbornik, 47 (1984), 353-364.

%F The constant is Sum_{n=1..infinity} A003000(n)*(Sum_{i=0..infinity} G_n(i)+H_n(i)), with:

%F 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)),

%F r_n(x) = 2*x^(2n+1) - x^(4n) + x^(5n) - 2*x^(5n+1) + x^(6n),

%F s_n(x) = 1 - 2*x^(1-n) + x^(-n);

%F 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)),

%F u_n(x) = 2*x^(4n+1) - x^(5n) + 2*x^(5n+1) + x^(6n),

%F v_n(x) = 1 - 2*x^(1-n) + x^(-n) - 2*x^(1-2n) + x^(-2n).

%F 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:

%F Lower bound, Sum_{n=1..N} A003000(n)*(Sum_{i=0..2K-1} G_n(i)+H_n(i));

%F Upper bound, (1/2)^N + Sum_{n=1..N} A003000(n)*(Sum_{i=0..2K} G_n(i)+H_n(i)).

%e The constant is 0.11944369525286337300011858612688510481590798881680833086306522202891445594210776107239...

%Y Cf. A003000, A123121, A262312 (aba).

%K nonn,cons

%O 0,3

%A _Danny Rorabaugh_, Sep 17 2015