A123121 -id:A123121 - 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.

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

Danny Rorabaugh, Sep 17 2015

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

			0.7322131597821108876233285964156974474449401020065154679236881114887...

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

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.

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

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.

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.

A018238 Add 1 to leading digit and put in front.

Original entry on oeis.org

1, 21, 3121, 41213121, 5121312141213121, 61213121412131215121312141213121, 7121312141213121512131214121312161213121412131215121312141213121

Offset: 1

N. J. A. Sloane, Michael Minic (minic(AT)mtsu.edu)

The concatenation of first n terms (if n is small) yields a palindrome: 1, 121, 1213121, etc. - Amarnath Murthy, Apr 08 2003
From M. F. Hasler, May 05 2008: (Start)
This is not the case from n=10 on: According to the formula in A123121 A082215(10) has an even number of digits, the middle digits being "10". (In a strict sense, e.g. Def. 3 of the first reference there, A082215(9) is the last Zimin word on the alphabet {1,...,9}, though.)
While there is less ambiguity about the definition of A018238(10), it is not clear if A018238(11) should start with "11..." or with "10..." (the largest digit of all subsequent terms being "9"). According to the formula in A123121, a(100) has 3 digits more than a(99), so the first choice seems appropriate and has been adopted for the given PARI code.
However, it corresponds to a modified definition, "a(n) = concatenation of n and all preceding terms". a(3) is the only prime term up to a(14) included. The sequence is (1,0,1,0,1,0,...) (mod 3), at least up to a(20). (End)

M. F. Hasler, Table of n, a(n) for n=1,...,11.

Cf. A001511, A082215, A123121, A033564.

A018238(n,t="")=for(k=2,n,t=Str(t,k-1,t));eval(Str(n,t)) \\ M. F. Hasler, May 05 2008

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.

Original entry on oeis.org

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

Danny Rorabaugh, Sep 17 2015

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

			The constant is 0.11944369525286337300011858612688510481590798881680833086306522202891445594210776107239...

Danny Rorabaugh, Table of n, a(n) for n = 0..185
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.

Cf. A003000, A123121, A262312 (aba).

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

A082215 Concatenation of terms of A018238.

Original entry on oeis.org

1, 121, 1213121, 121312141213121, 1213121412131215121312141213121, 121312141213121512131214121312161213121412131215121312141213121, 1213121412131215121312141213121612131214121312151213121412131217121312141213121512131214121312161213121412131215121312141213121

Offset: 1

Amarnath Murthy, Apr 08 2003

Also called Zimin words.

a(n) is a palindrome for n<10; it is debatable whether a(n) can be called a Zimin word for n>=10 (see the Comments in A018238). - Danny Rorabaugh, Sep 26 2015

J. Cooper and D. Rorabaugh, Bounds on Zimin Word Avoidance, arXiv:1409.3080 [math.CO], 2014; Congressus Numerantium, 222 (2014), 87-95.
L. J. Cummings and M. Mays, A one-sided Zimin construction, Electron. J. Combin. 8 (2001), #R27.
A. I. Zimin, Blocking sets of terms, Math. USSR Sbornik, 47 (1984), No. 2, 353-364.

Cf. A018238, A123121, A033564.

See A001511 for another representation of this sequence of digits.

a = {1}; Do[w = IntegerDigits@ a[[n - 1]]; AppendTo[a, FromDigits@ Join[w, IntegerDigits@ n, w]], {n, 2, 7}]; a (* Michael De Vlieger, Sep 26 2015 *)

The Zimin words are defined here by Z_1 = 1, Z_n = Z_{n-1}nZ_{n-1}. - Dmitry Kamenetsky, Sep 30 2006

More terms from Joshua Zucker, May 08 2006
"Palindromes" replaced with "Numbers" in sequence name by Danny Rorabaugh, Sep 26 2015
Shorter name by Joerg Arndt, Aug 28 2021

A262500 Number of binary, minimal instances of Zimin word Z_n that begin with 0.

Original entry on oeis.org

1, 3, 1751

Offset: 1

Danny Rorabaugh, Sep 24 2015

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.

			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.

D. Rorabaugh, Toward the Combinatorial Limit Theory of Free Words, University of South Carolina, ProQuest Dissertations Publishing (2015). See section 2.3.
Danny Rorabaugh, Binary, minimal Z_3-instances that begin with 0
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.

Cf. A123121, A262312, A262313.

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Sage

Formula

A018238 Add 1 to leading digit and put in front.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A082215 Concatenation of terms of A018238.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A262500 Number of binary, minimal instances of Zimin word Z_n that begin with 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs