|
%I #139 Oct 27 2023 19:47:42
%S 0,0,1,3,8,19,43,94,201,423,880,1815,3719,7582,15397,31171,62952,
%T 126891,255379,513342,1030865,2068495,4147936,8313583,16655823,
%U 33358014,66791053,133703499,267603416,535524643,1071563515,2143959070,4289264409,8580707127
%N a(n) = 2^n - Fibonacci(n+2).
%C Toss a fair coin n times; a(n) is number of possible outcomes having a run of 2 or more heads.
%C 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
%C 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
%C Row sums of triangle A153281 = (1, 3, 8, 19, 43, ...). - _Gary W. Adamson_, Dec 23 2008
%C a(n-1) is the number of compositions of n with at least one part >= 3. - _Joerg Arndt_, Aug 06 2012
%C 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
%C 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
%C With offset 0: antidiagonal sums of P(j,n) array of j-th partial sums of Fibonacci numbers. - _Luciano Ancora_, Apr 26 2015
%D W. Feller, An Introduction to Probability Theory and Its Applications, Vol. 1, 2nd ed. New York: Wiley, p. 300, 1968.
%D J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 14, Exercise 1.
%H Alois P. Heinz, <a href="/A008466/b008466.txt">Table of n, a(n) for n = 0..1000</a> (first 301 terms from T. D. Noe)
%H D. Applegate, M. LeBrun and N. J. A. Sloane, <a href="http://arxiv.org/abs/1107.1130">Dismal Arithmetic</a>, 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]
%H Simon Cowell, <a href="http://arxiv.org/abs/1506.03580">A Formula for the Reliability of a d-dimensional Consecutive-k-out-of-n:F System</a>, arXiv preprint arXiv:1506.03580 [math.CO], 2015.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=1020">Encyclopedia of Combinatorial Structures 1020</a>
%H T. Langley, J. Liese, and J. Remmel, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Langley/langley2.html">Generating Functions for Wilf Equivalence Under Generalized Factor Order</a>, J. Int. Seq. 14 (2011) # 11.4.2.
%H B. E. Merkel, <a href="http://rave.ohiolink.edu/etdc/view?acc_num=ucin1307442290">Probabilities of Consecutive Events in Coin Flipping</a>, Master's Thesis, Univ. Cincinatti, May 11 2011.
%H D. J. Persico and H. C. Friedman, <a href="http://dx.doi.org/10.1137/1004062">Another Coin Tossing Problem</a>, Problem 62-6, SIAM Review, 6 (1964), 313-314.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Run.html">Run.</a>
%H <a href="/index/Di#dismal">Index entries for sequences related to dismal (or lunar) arithmetic</a>
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,-1,-2).
%F 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
%F G.f.: x^2/((1-2*x)*(1-x-x^2)). - _Paul Barry_, Feb 16 2004
%F 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) = 2^n*Sum_{k=0..n} Fibonacci(k)/2^k. - _Paul Barry_, May 19 2004
%F a(n) = a(n-1)+a(n-2)+2^(n-2). - Jon Stadler (jstadler(AT)capital.edu), Aug 21 2006
%F a(n) = 2*a(n-1) + Fibonacci(n-1). - _Thomas M. Green_, Aug 21 2007
%F 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
%F a(n) = 2*a(n-1)-a(n-3)+2^(n-3). - _Carmine Suriano_, Mar 08 2011
%e From _Gus Wiseman_, Jun 25 2020: (Start)
%e The a(2) = 1 through a(5) = 19 compositions of n + 1 with at least one part >= 3 are:
%e (3) (4) (5) (6)
%e (1,3) (1,4) (1,5)
%e (3,1) (2,3) (2,4)
%e (3,2) (3,3)
%e (4,1) (4,2)
%e (1,1,3) (5,1)
%e (1,3,1) (1,1,4)
%e (3,1,1) (1,2,3)
%e (1,3,2)
%e (1,4,1)
%e (2,1,3)
%e (2,3,1)
%e (3,1,2)
%e (3,2,1)
%e (4,1,1)
%e (1,1,1,3)
%e (1,1,3,1)
%e (1,3,1,1)
%e (3,1,1,1)
%e (End)
%p a:= n-> (<<3|1|0>, <-1|0|1>, <-2|0|0>>^n)[1, 3]:
%p seq(a(n), n=0..50); # _Alois P. Heinz_, Jul 18 2008
%p # second Maple program:
%p 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
%t Table[2^n-Fibonacci[n+2],{n,0,20}] (* _Vladimir Joseph Stephan Orlovsky_, Jul 22 2008 *)
%t MMM = 30;
%t For[ M=2, M <= MMM, M++,
%t vlist = Array[x, M];
%t cl[i_] := And[ x[i], x[i+1] ];
%t cl2 = False; For [ i=1, i <= M-1, i++, cl2 = Or[cl2, cl[i]] ];
%t R[M] = SatisfiabilityCount[ cl2, vlist ] ]
%t Table[ R[M], {M,2,MMM}]
%t (* Find Boolean values of variables that satisfy the formula x1 x2 + x2 x3 + ... + xn-1 xn = 1; _N. J. A. Sloane_, Apr 23 2011 *)
%t LinearRecurrence[{3,-1,-2},{0,0,1},40] (* _Harvey P. Dale_, Aug 09 2013 *)
%t 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 *).
%t Table[Length[Select[Join@@Permutations/@IntegerPartitions[n+1],Max@@#>2&]],{n,0,10}] (* _Gus Wiseman_, Jun 25 2020 *)
%o (PARI) a(n) = 2^n-fibonacci(n+2) \\ _Charles R Greathouse IV_, Feb 03 2014
%o (Magma) [2^n-Fibonacci(n+2): n in [0..40]]; // _Vincenzo Librandi_, Apr 27 2015
%Y Cf. A050227.
%Y Cf. A050231, A050232, A050233.
%Y Cf. A153281.
%Y The non-contiguous version is A335455.
%Y Cf. A056986, A335457, A335458, A335516.
%Y Cf. A186244 (ternary words). Row 2 of A340156.
%K nonn,nice,easy
%O 0,4
%A _N. J. A. Sloane_, _I. J. Kennedy_, _Eric W. Weisstein_
|
