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.

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, 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, 5, 0, 6, 2, 2, 1, 4, 7, 6, 7, 2, 3, 7

Offset

0,1

Comments

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

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"

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

References

Steven R. Finch, Mathematical Constants, Encyclopedia of Mathematics and its Applications, vol. 94, Cambridge University Press, 2003, Section 5.17, p. 369.

Links

Danny Rorabaugh, Table of n, a(n) for n = 0..1000

Danny Rorabaugh, Toward the Combinatorial Limit Theory of Free Words, arXiv:1509.04372 [math.CO], 2015, University of South Carolina, ProQuest Dissertations Publishing (2015). See section 5.1.

Formula

The constant is Sum_{n>=0} A003000(n)*(1/4)^n.

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.

For ternary words, the constant is Sum_{n>=0} A019308(n)*(1/9)^n.

For quaternary words, the constant is Sum_{n>=0} A019309(n)*(1/16)^n.

Example

0.7322131597821108876233285964156974474449401020065154679236881114887...

Prog

(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.

Crossrefs

Cf. A003000, A094536, A123121, A242430, A262313 (abacaba).

Sequence in context: A033327 A024584 A132713 * A135296 A271353 A098907

Adjacent sequences: A262309 A262310 A262311 * A262313 A262314 A262315

Keyword

nonn,cons

Author

Danny Rorabaugh, Sep 17 2015

Status

approved