A050232 -id:A050232 - cp's OEIS frontend

A008466 a(n) = 2^n - Fibonacci(n+2).

0, 0, 1, 3, 8, 19, 43, 94, 201, 423, 880, 1815, 3719, 7582, 15397, 31171, 62952, 126891, 255379, 513342, 1030865, 2068495, 4147936, 8313583, 16655823, 33358014, 66791053, 133703499, 267603416, 535524643, 1071563515, 2143959070, 4289264409, 8580707127

Offset: 0

N. J. A. Sloane, I. J. Kennedy, Eric W. Weisstein

Toss a fair coin n times; a(n) is number of possible outcomes having a run of 2 or more heads.
Also the number of binary words of length n with at least two neighboring 1 digits. For example, a(4)=8 because 8 binary words of length 4 have two or more neighboring 1 digits: 0011, 0110, 0111, 1011, 1100, 1101, 1110, 1111 (cf. A143291). - Alois P. Heinz, Jul 18 2008
Equivalently, number of solutions (x_1, ..., x_n) to the equation x_1*x_2 + x_2*x_3 + x_3*x_4 + ... + x_{n-1}*x_n = 1 in base-2 lunar arithmetic. - N. J. A. Sloane, Apr 23 2011
Row sums of triangle A153281 = (1, 3, 8, 19, 43, ...). - Gary W. Adamson, Dec 23 2008
a(n-1) is the number of compositions of n with at least one part >= 3. - Joerg Arndt, Aug 06 2012
One less than the cardinality of the set of possible numbers of (leaf-) nodes of AVL trees with height n (cf. A143897, A217298). a(3) = 4-1, the set of possible numbers of (leaf-) nodes of AVL trees with height 3 is {5,6,7,8}. - Alois P. Heinz, Mar 20 2013
a(n) is the number of binary words of length n such that some prefix contains three more 1's than 0's or two more 0's than 1's. a(4) = 8 because we have: {0,0,0,0}, {0,0,0,1}, {0,0,1,0}, {0,0,1,1}, {0,1,0,0}, {1,0,0,0}, {1,1,1,0}, {1,1,1,1}. - Geoffrey Critzer, Dec 30 2013
With offset 0: antidiagonal sums of P(j,n) array of j-th partial sums of Fibonacci numbers. - Luciano Ancora, Apr 26 2015

			From _Gus Wiseman_, Jun 25 2020: (Start)
The a(2) = 1 through a(5) = 19 compositions of n + 1 with at least one part >= 3 are:
  (3)  (4)    (5)      (6)
       (1,3)  (1,4)    (1,5)
       (3,1)  (2,3)    (2,4)
              (3,2)    (3,3)
              (4,1)    (4,2)
              (1,1,3)  (5,1)
              (1,3,1)  (1,1,4)
              (3,1,1)  (1,2,3)
                       (1,3,2)
                       (1,4,1)
                       (2,1,3)
                       (2,3,1)
                       (3,1,2)
                       (3,2,1)
                       (4,1,1)
                       (1,1,1,3)
                       (1,1,3,1)
                       (1,3,1,1)
                       (3,1,1,1)
(End)

W. Feller, An Introduction to Probability Theory and Its Applications, Vol. 1, 2nd ed. New York: Wiley, p. 300, 1968.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 14, Exercise 1.

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 301 terms from T. D. Noe)
D. Applegate, M. LeBrun and N. J. A. Sloane, Dismal Arithmetic, arXiv:1107.1130 [math.NT], 2001. [Note: we have now changed the name from "dismal arithmetic" to "lunar arithmetic" - the old name was too depressing]
Simon Cowell, A Formula for the Reliability of a d-dimensional Consecutive-k-out-of-n:F System, arXiv preprint arXiv:1506.03580 [math.CO], 2015.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1020
T. Langley, J. Liese, and J. Remmel, Generating Functions for Wilf Equivalence Under Generalized Factor Order, J. Int. Seq. 14 (2011) # 11.4.2.
B. E. Merkel, Probabilities of Consecutive Events in Coin Flipping, Master's Thesis, Univ. Cincinatti, May 11 2011.
D. J. Persico and H. C. Friedman, Another Coin Tossing Problem, Problem 62-6, SIAM Review, 6 (1964), 313-314.
Eric Weisstein's World of Mathematics, Run.
Index entries for sequences related to dismal (or lunar) arithmetic
Index entries for linear recurrences with constant coefficients, signature (3,-1,-2).

Cf. A050227, A050231, A050232, A050233, A056986.
Cf. A153281, A186244 (ternary words), A335457, A335458, A335516.
The non-contiguous version is A335455.
Row 2 of A340156. Column 3 of A109435.

[2^n-Fibonacci(n+2): n in [0..40]]; // Vincenzo Librandi, Apr 27 2015

a:= n-> (<<3|1|0>, <-1|0|1>, <-2|0|0>>^n)[1, 3]:
seq(a(n), n=0..50); # Alois P. Heinz, Jul 18 2008
# second Maple program:
with(combinat): F:=fibonacci; f:=n->add(2^(n-1-i)*F(i),i=0..n-1); [seq(f(n),n=0..50)]; # N. J. A. Sloane, Mar 31 2014

Table[2^n-Fibonacci[n+2],{n,0,20}] (* Vladimir Joseph Stephan Orlovsky, Jul 22 2008 *)
MMM = 30;
For[ M=2, M <= MMM, M++,
vlist = Array[x, M];
cl[i_] := And[ x[i], x[i+1] ];
cl2 = False; For [ i=1, i <= M-1, i++, cl2 = Or[cl2, cl[i]] ];
R[M] = SatisfiabilityCount[ cl2, vlist ] ]
Table[ R[M], {M,2,MMM}]
(* Find Boolean values of variables that satisfy the formula x1 x2 + x2 x3 + ... + xn-1 xn = 1; N. J. A. Sloane, Apr 23 2011 *)
LinearRecurrence[{3,-1,-2},{0,0,1},40] (* Harvey P. Dale, Aug 09 2013 *)
nn=33; a=1/(1-2x); b=1/(1-2x^2-x^4-x^6/(1-x^2));
CoefficientList[Series[b(a x^3/(1-x^2)+x^2a),{x,0,nn}],x] (* Geoffrey Critzer, Dec 30 2013 *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n+1],Max@@#>2&]],{n,0,10}] (* Gus Wiseman, Jun 25 2020 *)

a(n) = 2^n-fibonacci(n+2) \\ Charles R Greathouse IV, Feb 03 2014

def A008466(n): return 2^n - fibonacci(n+2) # G. C. Greubel, Apr 23 2025

a(1)=0, a(2)=1, a(3)=3, a(n) = 3*a(n-1) - a(n-2) - 2*a(n-3). - Miklos Kristof, Nov 24 2003
G.f.: x^2/((1-2*x)*(1-x-x^2)). - Paul Barry, Feb 16 2004
From Paul Barry, May 19 2004: (Start)
Convolution of Fibonacci(n) and (2^n - 0^n)/2.
a(n) = Sum_{k=0..n} (2^k-0^k)*Fibonacci(n-k)/2.
a(n+1) = Sum_{k=0..n} Fibonacci(k)*2^(n-k).
a(n) = 2^n*Sum_{k=0..n} Fibonacci(k)/2^k. (End)
a(n) = a(n-1) + a(n-2) + 2^(n-2). - Jon Stadler (jstadler(AT)capital.edu), Aug 21 2006
a(n) = 2*a(n-1) + Fibonacci(n-1). - Thomas M. Green, Aug 21 2007
a(n) = term (1,3) in the 3 X 3 matrix [3,1,0; -1,0,1; -2,0,0]^n. - Alois P. Heinz, Jul 18 2008
a(n) = 2*a(n-1) - a(n-3) + 2^(n-3). - Carmine Suriano, Mar 08 2011

A050231 a(n) is the number of n-tosses having a run of 3 or more heads for a fair coin (i.e., probability is a(n)/2^n).

Original entry on oeis.org

0, 0, 1, 3, 8, 20, 47, 107, 238, 520, 1121, 2391, 5056, 10616, 22159, 46023, 95182, 196132, 402873, 825259, 1686408, 3438828, 6999071, 14221459, 28853662, 58462800, 118315137, 239186031, 483072832, 974791728, 1965486047, 3960221519, 7974241118, 16047432332, 32276862265

Offset: 1

Eric W. Weisstein

a(n-1) is the number of compositions of n with at least one part >= 4. - Joerg Arndt, Aug 06 2012

W. Feller, An Introduction to Probability Theory and Its Applications, Vol. 1, 2nd ed. New York: Wiley, p. 300, 1968.

T. D. Noe, Table of n, a(n) for n = 1..300
David Broadhurst, Multiple Landen values and the tribonacci numbers, arXiv:1504.05303 [hep-th], 2015.
Simon Cowell, A Formula for the Reliability of a d-dimensional Consecutive-k-out-of-n:F System, arXiv preprint arXiv:1506.03580 [math.CO], 2015.
Erich Friedman, Illustration of initial terms
T. Langley, J. Liese, and J. Remmel, Generating Functions for Wilf Equivalence Under Generalized Factor Order, J. Int. Seq. 14 (2011) # 11.4.2.
Eric Weisstein's World of Mathematics, Run
Index entries for linear recurrences with constant coefficients, signature (3,-1,-1,-2).

Cf. A000073, A008466, A050232, A050233.

Column 4 of A109435.

R:= PowerSeriesRing(Integers(), 60);
[0,0] cat Coefficients(R!( x^3/((1-2*x)*(1-x-x^2-x^3)) )); // G. C. Greubel, Jun 01 2025

LinearRecurrence[{3, -1, -1, -2}, {0, 0, 1, 3}, 50] (* David Nacin, Mar 07 2012 *)

concat([0,0], Vec(1/(1-2*x)/(1-x-x^2-x^3)+O(x^99))) \\ Charles R Greathouse IV, Feb 03 2015

def a(n, adict={0:0, 1:0, 2:1, 3:3}):
    if n in adict:
        return adict[n]
    adict[n]=3*a(n-1)-a(n-2)-a(n-3)-2*a(n-4)
    return adict[n] # David Nacin, Mar 07 2012

def A050231_list(prec):
    P.= PowerSeriesRing(QQ, prec)
    return P( x^3/((1-2*x)*(1-x-x^2-x^3)) ).list()
a=A050231_list(41); a[1:] # G. C. Greubel, Jun 01 2025

a(n) = 2^n - tribonacci(n+3), see A000073. - Vladeta Jovovic, Feb 23 2003
G.f.: x^3/((1-2*x)*(1-x-x^2-x^3)). - Geoffrey Critzer, Jan 29 2009
a(n) = 2 * a(n-1) + 2^(n-4) - a(n-4) since we can add T or H to a sequence of n-1 flips which has HHH, and H to one which ends in THH and does not have HHH among the first (n-4) flips. - Toby Gottfried, Nov 20 2010
a(n) = 3*a(n-1) - a(n-2) - a(n-3) - 2*a(n-4), a(0)=0, a(1)=0, a(2)=1, a(3)=3. - David Nacin, Mar 07 2012

A119706 Total length of longest runs of 1's in all bitstrings of length n.

Original entry on oeis.org

1, 4, 11, 27, 62, 138, 300, 643, 1363, 2866, 5988, 12448, 25770, 53168, 109381, 224481, 459742, 939872, 1918418, 3910398, 7961064, 16190194, 32893738, 66772387, 135437649, 274518868, 556061298, 1125679616, 2277559414, 4605810806, 9309804278, 18809961926

Offset: 1

Adam Kertesz, Jun 09 2006, Jun 13 2006

nonn

a(n) divided by 2^n is the expected value of the longest run of heads in n tosses of a fair coin.

a(n) is also the sum of the number of binary words with at least one run of consecutive 0's of length >= i for i>=1. In other words A000225 + A008466 + A050231 + A050232 + ... . - Geoffrey Critzer, Jan 12 2013

			a(3)=11 because for the 8(2^3) possible runs 0 is longest run of heads once, 1 four times, 2 two times and 3 once and 0*1+1*4+2*2+3*1 = 11.

A. M. Odlyzko, Asymptotic Enumeration Methods, pp. 136-137
R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, page 372.

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Steven Finch, Cantor-solus and Cantor-multus distributions, arXiv:2003.09458 [math.CO], 2020.

Cf. A334833.

A038374 := proc(n) local nshft, thisr, resul; nshft := n ; resul :=0 ; thisr :=0 ; while nshft > 0 do if nshft mod 2 <> 0 then thisr := thisr+1 ; else resul := max(resul, thisr) ; thisr := 0 ; fi ; nshft := floor(nshft/2) ; od ; resul := max(resul, thisr) ; RETURN(resul) ; end : A119706 := proc(n) local count, c, rlen ; count := array(0..n) ; for c from 0 to n do count[c] := 0 ; od ; for c from 0 to 2^n-1 do rlen := A038374(c) ; count[rlen] := count[rlen]+1 ; od ; RETURN( sum('count[c]*c','c'=0..n) ); end: for n from 1 to 40 do print(n,A119706(n)) ; od : # R. J. Mathar, Jun 15 2006
# second Maple program:
b:= proc(n, m) option remember; `if`(n=0, 1,
      `if`(m=0, add(b(n-j, j), j=1..n),
      add(b(n-j, min(n-j, m)), j=1..min(n, m))))
    end:
a:= proc(n) option remember;
     `if`(n<2, n, 2*a(n-1) +b(n, 0))
    end:
seq(a(n), n=1..40);  # Alois P. Heinz, Dec 19 2014

nn=10;Drop[Apply[Plus,Table[CoefficientList[Series[1/(1-2x)-(1-x^n)/(1-2x+x^(n+1)),{x,0,nn}],x],{n,1,nn}]],1]  (* Geoffrey Critzer, Jan 12 2013 *)

a(n+1) = 2*a(n) + A007059(n+2)
a(n) > 2*a(n-1). a(n) = Sum_{i=1..(2^n)-1} A038374(i). - R. J. Mathar, Jun 15 2006
From Geoffrey Critzer, Jan 12 2013: (Start)
O.g.f.: Sum_{k>=1} 1/(1-2*x) - (1-x^k)/(1-2*x+x^(k+1)). - Corrected by Steven Finch, May 16 2020
a(n) = Sum_{k=1..n} A048004(n,k) * k.
(End)
Conjecture: a(n) = A102712(n+1)-2^n. - R. J. Mathar, Jun 05 2025

More terms from R. J. Mathar, Jun 15 2006

Name edited by Alois P. Heinz, Mar 18 2020

A050233 a(n) is the number of n-tosses having a run of 5 or more heads for a fair coin (i.e., probability is a(n)/2^n).

Original entry on oeis.org

0, 0, 0, 0, 1, 3, 8, 20, 48, 112, 255, 571, 1262, 2760, 5984, 12880, 27553, 58631, 124192, 262008, 550800, 1154256, 2412031, 5027575, 10455246, 21697060, 44940472, 92920992, 191818561, 395386763, 813872712, 1673157228, 3435591712, 7046697888, 14438448127, 29555251315, 60444113566

Offset: 1

Eric W. Weisstein

a(n-1) is the number of compositions of n with at least one part >= 6. - Joerg Arndt, Aug 06 2012

W. Feller, An Introduction to Probability Theory and Its Applications, Vol. 1, 2nd ed. New York: Wiley, p. 300, 1968.

T. D. Noe, Table of n, a(n) for n = 1..300
Eric Weisstein's World of Mathematics, Run.
Index entries for linear recurrences with constant coefficients, signature (3,-1,-1,-1,-1,-2).

Cf. A001591, A008466, A050231, A050232.

Column 6 of A109435.

R:= PowerSeriesRing(Integers(), 50);
[0,0,0,0] cat Coefficients(R!( x^5/((1-2*x)*(1-x-x^2-x^3-x^4-x^5)) )); // G. C. Greubel, Jun 01 2025

f[x_] := x^4 / (1-3x+x^2+x^3+x^4+x^5+2x^6); CoefficientList[ Series[f[x], {x, 0, 31}], x] (* Jean-François Alcover, Nov 18 2011 *)
LinearRecurrence[{3,-1,-1,-1,-1,-2},{0,0,0,0,1,3},40] (* Harvey P. Dale, Jan 27 2015 *)

a(n)=([0,1,0,0,0,0; 0,0,1,0,0,0; 0,0,0,1,0,0; 0,0,0,0,1,0; 0,0,0,0,0,1; -2,-1,-1,-1,-1,3]^(n-1)*[0;0;0;0;1;3])[1,1] \\ Charles R Greathouse IV, Jun 15 2015

def A050233_list(prec):
    P.= PowerSeriesRing(QQ, prec)
    return P( x^5/((1-2*x)*(1-x-x^2-x^3-x^4-x^5)) ).list()
a=A050233_list(41); a[1:] # G. C. Greubel, Jun 01 2025

a(n) = 2^(n+1) - pentanacci(n+6), cf. A001591. - Vladeta Jovovic, Feb 23 2003
G.f.: x^5/((1-2*x)*(1-x-x^2-x^3-x^4-x^5)). - Geoffrey Critzer, Jan 29 2009
a(n) = 3*a(n-1) - a(n-2) - a(n-3) - a(n-4) - a(n-5) - 2*a(n-6). - Wesley Ivan Hurt, Jan 03 2021

A109435 Triangle read by rows: T(n,m) = number of binary numbers n digits long, which have m 0's as a substring.

Original entry on oeis.org

1, 2, 1, 4, 3, 1, 8, 7, 3, 1, 16, 15, 8, 3, 1, 32, 31, 19, 8, 3, 1, 64, 63, 43, 20, 8, 3, 1, 128, 127, 94, 47, 20, 8, 3, 1, 256, 255, 201, 107, 48, 20, 8, 3, 1, 512, 511, 423, 238, 111, 48, 20, 8, 3, 1, 1024, 1023, 880, 520, 251, 112, 48, 20, 8, 3, 1, 2048, 2047, 1815, 1121, 558

Offset: 0

Robert G. Wilson v, Jun 28 2005

Column 0 is A000079, column 2 is A000225, column 3 is A008466, column 4 is A050231
Column 5 is A050232, column 6 is A050233, the last column is A001792.
A050227 with a leading column of powers of 2. - R. J. Mathar, Mar 25 2014

			Triangle begins:
n\m_0__1__2__3__4__5
0|  1  0  0  0  0  0
1|  2  1  0  0  0  0
2|  4  3  1  0  0  0
3|  8  7  3  1  0  0
4| 16 15  8  3  1  0
5| 32 31 19  8  3  1
T(5,3)=8 because there are 8 length 5 binary words that contain 000 as a contiguous substring:  00000, 00001, 00010, 00011, 01000, 10000, 10001, 11000. - _Geoffrey Critzer_, Jan 07 2014

Cf. A109433, A001792, A109436, A102712 (row sums ?).

A109435 := proc(n,k)
    option remember ;
    if n< k then
        0;
    elif n = k then
        1;
    else
        2*procname(n-1,k)+2^(n-1-k)-procname(n-1-k,k) ;
    end if;
end proc:
seq(seq( A109435(n,k),k=0..n),n=0..12) ; # R. J. Mathar, Jun 05 2025

T[n_, m_] := Length[ Select[ StringPosition[ #, StringDrop[ ToString[10^m], 1]] & /@ Table[ ToString[ FromDigits[ IntegerDigits[i, 2]]], {i, 2^n, 2^(n + 1) - 1}], # != {} &]]; Flatten[ Table[ T[n, m], {n, 0, 11}, {m, 0, n}]]
nn=15;Map[Select[#,#>0&]&,Transpose[Table[CoefficientList[Series[x^m/(1-Sum[x^k,{k,1,m}])/(1-2x),{x,0,nn}],x],{m,0,nn}]]]//Grid (* Geoffrey Critzer, Jan 07 2014 *)

G.f. for column m: x^m/( (1 - Sum_{k=1..m} x^k)*(1-2*x) ). - Geoffrey Critzer, Jan 07 2014

A050227 Triangle of number of n-tosses having a run of r or more heads for a fair coin with r=1 to n across and n=1, 2, ... down.

Original entry on oeis.org

1, 3, 1, 7, 3, 1, 15, 8, 3, 1, 31, 19, 8, 3, 1, 63, 43, 20, 8, 3, 1, 127, 94, 47, 20, 8, 3, 1, 255, 201, 107, 48, 20, 8, 3, 1, 511, 423, 238, 111, 48, 20, 8, 3, 1, 1023, 880, 520, 251, 112, 48, 20, 8, 3, 1, 2047, 1815, 1121, 558, 255, 112, 48, 20, 8, 3, 1, 4095, 3719

Offset: 1

Eric W. Weisstein

			Triangle begins:
   1;
   3,  1;
   7,  3, 1;
  15,  8, 3, 1;
  31, 19, 8, 3, 1
  ...

W. Feller, An Introduction to Probability Theory and Its Applications, Vol. 1, 2nd ed. New York: Wiley, p. 300, 1968.

T. D. Noe, Rows n=1..100 of triangle, flattened
Eric Weisstein's World of Mathematics, Coin Tossing.
Eric Weisstein's World of Mathematics, Run.

Cf. A008466, A119706 (row sums?).

Cf. A050231, A050232, A050233.

Clear[fib]; fib[n_, n_] = 1; fib[n_, k_] /; k > n = 0; fib[n_, k_] := fib[n, k] = If[k == 1, 1, Sum[fib[m, k], {m, n - k , n - 1}]]; Table[ 2^n - fib[n + k + 1 , k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jan 15 2013 *)

A151975 The number of ways one can flip seven consecutive tails (or heads) when flipping a coin n times.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 3, 8, 20, 48, 112, 256, 576, 1279, 2811, 6126, 13256, 28512, 61008, 129952, 275712, 582913, 1228551, 2582048, 5412984, 11321744, 23631056, 49229312, 102377216, 212560127, 440668919, 912310222, 1886316324, 3895528632, 8035861664

Offset: 0

Benjamin Merkel, Aug 05 2012

a(n-1) is the number of compositions of n with at least one part >=8. - Joerg Arndt, Aug 06 2012

			a(0)=0 means that there are no cases of seven consecutive tails (or heads) in zero coin flips.  Likewise, a(1)=a(2)=...=a(6)=0.  a(7)=1 since there is exactly one case of seven consecutive tails in seven coin flips.

Colin Barker, Table of n, a(n) for n = 0..1000
Benjamin E. Merkel, Probabilities of Consecutive Events in Coin Flipping, OhioLINK, 2011
Index entries for linear recurrences with constant coefficients, signature (3,-1,-1,-1,-1,-1,-1,-2).

Cf. A050231, A050232, A050233, A143662.

N=66;  x='x+O('x^N);
gf = (1-x)/(1-2*x); /* A011782(n): compositions of n */
gf -= 1/(1 - (x+x^2+x^3+x^4+x^5+x^6+x^7)); /* A066178(n): compositions of n into parts <=7 */
v151975=Vec(gf + 'a0);  v151975[1]=0; /* kludge to get all terms */
v151975 /* show terms */
/* Joerg Arndt, Aug 06 2012 */

concat(vector(7), Vec(x^7/((2*x-1)*(x^7+x^6+x^5+x^4+x^3+x^2+x-1)) + O(x^100))) \\ Colin Barker, Oct 16 2015

a(n) = A000079(n) - A066178(n+1).

G.f.: x^7 / ((2*x-1)*(x^7+x^6+x^5+x^4+x^3+x^2+x-1)). - Colin Barker, Oct 16 2015

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

Original entry on oeis.org

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

A008466 a(n) = 2^n - Fibonacci(n+2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

A050231 a(n) is the number of n-tosses having a run of 3 or more heads for a fair coin (i.e., probability is a(n)/2^n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

SageMath

Formula

A119706 Total length of longest runs of 1's in all bitstrings of length n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A050233 a(n) is the number of n-tosses having a run of 5 or more heads for a fair coin (i.e., probability is a(n)/2^n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

A109435 Triangle read by rows: T(n,m) = number of binary numbers n digits long, which have m 0's as a substring.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

A050227 Triangle of number of n-tosses having a run of r or more heads for a fair coin with r=1 to n across and n=1, 2, ... down.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs