A262312 -id:A262312 - cp's OEIS frontend

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.

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

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.

A342378 List of numbers whose binary expansion is an instance of the Zimin pattern ABA.

Original entry on oeis.org

5, 7, 9, 11, 13, 15, 17, 18, 19, 21, 22, 23, 25, 27, 29, 31, 33, 34, 35, 37, 38, 39, 41, 42, 43, 45, 46, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 66, 67, 68, 69, 70, 71, 73, 74, 75, 76, 77, 78, 79, 81, 82, 83, 85, 86, 87, 89, 90, 91, 93, 94, 95, 97, 99, 101

Offset: 1

Peter Kagey, Mar 09 2021

This is A091066 with some terms of A020330 removed.

			The binary expansion of 182 is 10110110, which is an instance of the pattern ABA with A=10 and B=1101.

Peter Kagey, Table of n, a(n) for n = 1..1000
Wikipedia, Sesquipower

Cf. A020330, A091066, A254128, A262312.

def ok(n):
  b = bin(n)[2:]
  for i in range(1, (len(b)+1)//2):
    if b[:i] == b[-i:]: return True
  return False
def aupto(lim): return [m for m in range(lim+1) if ok(m)]
print(aupto(101)) # Michael S. Branicky, Mar 09 2021

cp's OEIS Frontend

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A342378 List of numbers whose binary expansion is an instance of the Zimin pattern ABA.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python