login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A008466 a(n) = 2^n - Fibonacci(n+2). 23
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 (list; graph; refs; listen; history; text; internal format)
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

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

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 14, Exercise 1.

LINKS

T. D. Noe and 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 [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, 2015

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1020

T. Langley, J. Liese, 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).

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

Convolution of Fibonacci(n) and (2^n-0^n)/2. a(n)=sum{k=0..n, (2^k-0^k)Fib(n-k)/2}; a(n+1)=sum{k=0..n, Fib(k)2^(n-k)}=2^n*sum{k=0..n, Fib(k)/2^k}. - Paul Barry, May 19 2004

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) + Fib(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

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

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=15; 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 *).

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

CROSSREFS

Cf. A050227.

a(n) = A101220(2, 2, n-1), for n > 0.

Cf. A050231, A050232, A050233.

Cf. A153281. - Gary W. Adamson, Dec 23 2008

Sequence in context: A065352 A161993 A259401 * A102712 A054480 A191787

Adjacent sequences:  A008463 A008464 A008465 * A008467 A008468 A008469

KEYWORD

nonn,nice,easy

AUTHOR

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 23 07:28 EST 2018. Contains 299473 sequences. (Running on oeis4.)