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
Examples
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)
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)
- 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).
Crossrefs
Programs
-
Magma
[2^n-Fibonacci(n+2): n in [0..40]]; // Vincenzo Librandi, Apr 27 2015
-
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 # 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
-
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 *) -
PARI
a(n) = 2^n-fibonacci(n+2) \\ Charles R Greathouse IV, Feb 03 2014
-
SageMath
def A008466(n): return 2^n - fibonacci(n+2) # G. C. Greubel, Apr 23 2025
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
Comments