cp's OEIS Frontend

A262312 The limit, as word-length approaches infinity, of the probability that a random binary word is an instance of the Zimin pattern "aba"; also the probability that a random infinite binary word begins with an even-length palindrome.

%I A262312 #42 Dec 15 2024 06:32:36
%S A262312 7,3,2,2,1,3,1,5,9,7,8,2,1,1,0,8,8,7,6,2,3,3,2,8,5,9,6,4,1,5,6,9,7,4,
%T A262312 4,7,4,4,4,9,4,0,1,0,2,0,0,6,5,1,5,4,6,7,9,2,3,6,8,8,1,1,1,4,8,8,7,8,
%U A262312 5,0,6,2,2,1,4,7,6,7,2,3,7
%N A262312 The limit, as word-length approaches infinity, of the probability that a random binary word is an instance of the Zimin pattern "aba"; also the probability that a random infinite binary word begins with an even-length palindrome.
%C A262312 Word W over alphabet L is an instance of "aba" provided there exists a nonerasing monoid homomorphism f:{a,b}*->L* such that f(W)=aba. For example "oompaloompa" is an instance of "aba" via the homomorphism defined by f(a)=oompa, f(b)=l. For a proof of the formula or more information on Zimin words, see Rorabaugh (2015).
%C A262312 The second definition comes from a Comment in A094536: "The probability that a random, infinite binary string begins with an even-length palindrome is: lim n -> infinity a(n)/2^n ~ 0.7322131597821108... . - _Peter Kagey_, Jan 26 2015"
%C A262312 Also, the limit, as word-length approaches infinity, of the probability that a random binary word has a bifix; that is, 1-x where x is the constant from A242430. - _Danny Rorabaugh_, Feb 13 2016
%D A262312 Steven R. Finch, Mathematical Constants, Encyclopedia of Mathematics and its Applications, vol. 94, Cambridge University Press, 2003, Section 5.17, p. 369.
%H A262312 Danny Rorabaugh, <a href="/A262312/b262312.txt">Table of n, a(n) for n = 0..1000</a>
%H A262312 Danny Rorabaugh, <a href="http://arxiv.org/abs/1509.04372">Toward the Combinatorial Limit Theory of Free Words</a>, arXiv:1509.04372 [math.CO], 2015, University of South Carolina, ProQuest Dissertations Publishing (2015). See section 5.1.
%F A262312 The constant is Sum_{n>=0} A003000(n)*(1/4)^n.
%F A262312 Using the recursive definition of A003000, one can derive the series Sum_{j>=0} 2*(-1)^j*(1/4)^(2^j)/(Product_{k=0..j} 1-2*(1/4)^(2^k)), which converges more quickly to the same limit and without having to calculate terms of A003000.
%F A262312 For ternary words, the constant is Sum_{n>=0} A019308(n)*(1/9)^n.
%F A262312 For quaternary words, the constant is Sum_{n>=0} A019309(n)*(1/16)^n.
%e A262312 0.7322131597821108876233285964156974474449401020065154679236881114887...
%o A262312 (Sage) N(sum([2*(1/4)^(2^j)*(-1)^j/prod([1-2*(1/4)^(2^k) for k in range(j+1)]) for j in range(8)]),digits=81) #For more than 152 digits of accuracy, increase the j-range.
%Y A262312 Cf. A003000, A094536, A123121, A242430, A262313 (abacaba).
%K A262312 nonn,cons
%O A262312 0,1
%A A262312 _Danny Rorabaugh_, Sep 17 2015