OFFSET
0,4
COMMENTS
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
REFERENCES
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.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 301 terms from T. D. Noe)
David Applegate, Marc 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]
Félix Balado and Guénolé C. M. Silvestre, Systematic Enumeration of Fundamental Quantities Involving Runs in Binary Strings, arXiv:2602.10005 [math.CO], 2026. See p. 20.
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.
Andreas M. Hinz and El-Mehdi Mehiri, The Weighted Tower of Hanoi: Algebraic Structure, Phase Transitions, and Integer Sequences, arXiv:2605.16956 [math.CO], 2026. See p. 11.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1020.
Thomas Langley, Jeffrey Liese, and Jeffrey Remmel, Generating Functions for Wilf Equivalence Under Generalized Factor Order, J. Int. Seq. 14 (2011) # 11.4.2.
Benjamin E. Merkel, Probabilities of Consecutive Events in Coin Flipping, Master's Thesis, Univ. Cincinatti, May 11 2011.
Donald J. Persico and Henry 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 linear recurrences with constant coefficients, signature (3,-1,-2).
FORMULA
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
E.g.f.: exp(2*x) - exp(x/2)*(5*cosh(sqrt(5)*x/2) + 3*sqrt(5)*sinh(sqrt(5)*x/2))/5. - Stefano Spezia, Feb 13 2026
EXAMPLE
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)
MAPLE
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
# Alternative:
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
MATHEMATICA
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 *)
PROG
(PARI) a(n) = 2^n-fibonacci(n+2) \\ Charles R Greathouse IV, Feb 03 2014
(Magma) [2^n-Fibonacci(n+2): n in [0..40]]; // Vincenzo Librandi, Apr 27 2015
(SageMath) def A008466(n): return 2^n - fibonacci(n+2) # G. C. Greubel, Apr 23 2025
CROSSREFS
The non-contiguous version is A335455.
KEYWORD
nonn,nice,easy
STATUS
approved