A109435 -id:A109435 - cp's OEIS frontend

A109436 Triangle of numbers: row n gives the elements along the subdiagonal of A109435 that connects 2^n with (n+2)*2^(n-1).

0, 0, 1, 1, 2, 3, 4, 7, 8, 8, 15, 19, 20, 16, 31, 43, 47, 48, 32, 63, 94, 107, 111, 112, 64, 127, 201, 238, 251, 255, 256, 128, 255, 423, 520, 558, 571, 575, 576, 256, 511, 880, 1121, 1224, 1262, 1275, 1279, 1280, 512, 1023, 1815, 2391, 2656, 2760, 2798, 2811

Offset: 0

Robert G. Wilson v, Jun 28 2005

In the limit of row number n->infinity, the differences of the n-th row of the table, read from right to left, are 1, 4, 13, 38, 104,... = A084851.

			The triangle A109435 begins
    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;
If we read this triangle starting at 2^n in its first column along its n-th subdiagonal up to the first occurrence of (n+2)*2^(n-1), we get row n of the current triangle, which begins:
   0,   0;
   1,   1;
   2,   3;
   4,   7,   8;
   8,  15,  19,  20;
  16,  31,  43,  47,  48;
  32,  63,  94, 107, 111, 112;

Cf. A109435, A001792, A109434, A084851.

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 + i, i], {n, 0, 9}, {i, 0, n}]]

Edited by R. J. Mathar, Nov 17 2009

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

Original entry on oeis.org

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

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

Original entry on oeis.org

0, 0, 0, 1, 3, 8, 20, 48, 111, 251, 558, 1224, 2656, 5713, 12199, 25888, 54648, 114832, 240335, 501239, 1042126, 2160676, 4468664, 9221281, 18989899, 39034824, 80103276, 164126496, 335808927, 686182387, 1400438814, 2854992080, 5814293120, 11829648225, 24046855887, 48840756608

Offset: 1

Eric W. Weisstein

a(n-1) is the number of compositions of n with at least one part >= 5. - 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
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.
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,-1,-2).

Cf. A000078, A008466, A050231, A050233.

Column 5 of A109435.

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

Flatten[With[{tetrnos=LinearRecurrence[{1,1,1,1},{0,1,1,2},50]}, Table[ 2^n- Take[tetrnos,{n+3}],{n,40}]]] (* Harvey P. Dale, Dec 02 2011 *)
LinearRecurrence[{3,-1,-1,-1,-2}, {0,0,0,1,3}, 31] (* Ray Chandler, Aug 03 2015 *)

a(n)=([0,1,0,0,0; 0,0,1,0,0; 0,0,0,1,0; 0,0,0,0,1; -2,-1,-1,-1,3]^(n-1)*[0;0;0;1;3])[1,1] \\ Charles R Greathouse IV, Feb 09 2017

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

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

a(n) = 2^n - tetranacci(n+4), see A000078. - Vladeta Jovovic, Feb 23 2003
G.f.: x^4/((1-2*x)*(1-x-x^2-x^3-x^4)). - Geoffrey Critzer, Jan 29 2009
a(n) = 3*a(n-1) - a(n-2) - a(n-3) - a(n-4) - 2*a(n-5). - Wesley Ivan Hurt, Apr 23 2021

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

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

Original entry on oeis.org

1, 2, 1, 4, 2, 1, 8, 5, 2, 1, 16, 11, 5, 2, 1, 32, 24, 12, 5, 2, 1, 64, 51, 27, 12, 5, 2, 1, 128, 107, 60, 28, 12, 5, 2, 1, 256, 222, 131, 63, 28, 12, 5, 2, 1, 512, 457, 282, 140, 64, 28, 12, 5, 2, 1, 1024, 935, 601, 307, 143, 64, 28, 12, 5, 2, 1, 2048, 1904, 1270, 666, 316, 144

Offset: 0

Robert G. Wilson v, Jun 27 2005

			T(4,2)=11 because of the sixteen binary digits which are 5 long, {10000, 10001, 10010, 10011, 10100, 10101, 10110, 10111, 11000, 11001, 11010, 11011, 11100, 11101, 11110, 11111}, 11 have "11" as a substring.
Triangle begins:
n\m
0 1 0 0 0 0 0 0 0 0 0
1 2 1 0 0 0 0 0 0 0 0
2 4 2 1 0 0 0 0 0 0 0
3 8 5 2 1 0 0 0 0 0 0
4 16 11 5 2 1 0 0 0 0 0
5 32 24 12 5 2 1 0 0 0 0

First column = A000079 = Powers of 2, the second column = A027934 = number of compositions of n with at least one even part and the last column = A045623 = number of 1's in all compositions of n+1.

Cf. A000079, A027934, A045623, A109434, A109435.

T[n_, m_] := Length[ Select[ StringPosition[ #, ToString[(10^m - 1)/9]] & /@ Table[ ToString[ FromDigits[ IntegerDigits[i, 2]]], {i, 2^n, 2^(n + 1) - 1}], # != {} &]]; Flatten[ Table[ T[n, m], {n, 0, 11}, {m, n + 1}]]

cp's OEIS Frontend

A109436 Triangle of numbers: row n gives the elements along the subdiagonal of A109435 that connects 2^n with (n+2)*2^(n-1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

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

A050232 a(n) is the number of n-tosses having a run of 4 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

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

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

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica