Deyan Bozhkov - cp's OEIS frontend

User: Deyan Bozhkov

Deyan Bozhkov has authored 1 sequences.

A373046 Number of binary strings of length n that contain the substring 1000.

0, 0, 0, 0, 1, 4, 12, 32, 79, 186, 424, 944, 2065, 4456, 9512, 20128, 42287, 88310, 183492, 379624, 782497, 1607756, 3294164, 6732992, 13732063, 27953522, 56807184, 115269984, 233585121, 472771152, 955843984, 1930635712, 3896121759, 7856343278, 15830584396

Offset: 0

Deyan Bozhkov, Aug 02 2024

a(n)=2^(n-3)+a(n-1)+a(n-2)+a(n-3)-1 for n>=7.
Proof: Copnsider possible endings of the sequence:
1. If it ends with 000, then all sequences except 00...0 work, meaning that 2^(n-3)-1 sequences are valid.
2. If it ends with 100, then there are a(n-3) valid sequences.
3. If it ends with 10, then there are a(n-2) valid sequences.
4. If it ends with 1, then there are a(n-1) valid sequences.
As these are the only possible endings, the conclusion holds.
If we search for a sequence 10...0 (with k zeros), an extended version of the same algorithm gives a(n)=a(n-k)+a(n-k-1)...+a(n-1)+2^(n-k)-1

			a(5) = 4: 01000, 11000, 10000, 10001.

Paolo Xausa, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (4,-4,0,-1,2).

Cf. A050232, A232580.

LinearRecurrence[{4, -4, 0, -1, 2}, {0, 0, 0, 0, 1}, 50] (* Paolo Xausa, Oct 01 2024 *)

def aupton(terms):
    a = [0, 0, 0]
    for n in range(3, terms):
        next_term = 2**(n-3) + a[n-1] + a[n-2] + a[n-3] - 1
        a.append(next_term)
    return a[:terms]
print(aupton(35))

a(n) = 2^(n-3) + a(n-1) + a(n-2) + a(n-3) - 1.
a(n) = 3*a(n-1) - a(n-2) - a(n-3) - 2*a(n-4) + 1.
G.f.: -x^4/((x-1)*(2*x-1)*(x^3+x^2+x-1)). - Alois P. Heinz, Aug 02 2024
2*a(n) = 1+2^(n+1)-A000213(n+3). - R. J. Mathar, Aug 28 2024

cp's OEIS Frontend

User: Deyan Bozhkov

A373046 Number of binary strings of length n that contain the substring 1000.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula