A239791 Number of compositions of n with no consecutive 2's.
1, 1, 2, 4, 7, 14, 28, 54, 105, 205, 399, 777, 1514, 2949, 5744, 11189, 21795, 42454, 82696, 161083, 313772, 611194, 1190540, 2319043, 4517245, 8799105, 17139705, 33386292, 65032887, 126677032, 246753161, 480648477, 936251262, 1823716224, 3552402011, 6919695006, 13478817664, 26255279382, 51142445325
Offset: 0
Examples
a(5) = 14 because there are 16 compositions of 5, but we don't count 2+2+1 and 1+2+2.
Links
- Vincenzo Librandi, Table of n, a(n) for n = 0..1000
- Index entries for linear recurrences with constant coefficients, signature (2,-1,2,-1,1).
Programs
-
Mathematica
nn=30;k=2;CoefficientList[Series[(1+x^k)/(1-(2x^(2k+1)/(1-x)+x^(2k)+Sum[x^j,{j,1,k-1}]+Sum[2x^j,{j,k+1,2k-1}])),{x,0,nn}],x] CoefficientList[Series[(1 + x^2)/(1 - (2 x^5/(1 - x) + x + x^4 + 2 x^3)), {x, 0, 50}], x] (* Vincenzo Librandi, Mar 29 2014 *) -
PARI
Vec( (1 + x^2)/(1 - (2*x^5/(1-x) + x + x^4 + 2*x^3)) + O(x^66) ) \\ Joerg Arndt, Mar 27 2014
Formula
G.f.: (1 + x^2)/(1 - (2*x^5/(1 - x) + x + x^4 + 2*x^3)) = (x - 1)*(1 + x^2) / (-1 + 2*x - x^2 + 2*x^3 - x^4 + x^5).
Generally, for fixed integer k>=1, the g.f. for the number of compositions with no consecutive k's: (1 + x^k)/(1 - (2*x^(2*k + 1)/(1-x) + x^(2*k) + Sum_{j=1..k-1} x^j + Sum{j=k+1..2*k-1} 2*x^j)).
Another way to write G. Critzer's general g.f. above: 1/((1 - 2*x)/(1 - x) + x^(2*k)/(1 + x^k)). - Petros Hadjicostas, Dec 03 2017
Recurrence: a(n) = 2*a(n-1) - a(n-2) + 2*a(n-3) - a(n-4) + a(n-5). - Petros Hadjicostas, Aug 02 2020