A050227 -id:A050227 - 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

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

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