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,3

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).

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

Example

a(5) = 14 because there are 16 compositions of 5, but we don't count 2+2+1 and 1+2+2.

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 *)

Prog

(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

Crossrefs

Cf. A000213 (compositions with no consecutive 1's), A003242.

Sequence in context: A161713 A018330 A068060 * A358837 A251653 A057744

Adjacent sequences: A239788 A239789 A239790 * A239792 A239793 A239794

Keyword

nonn,easy

Author

Geoffrey Critzer, Mar 26 2014

Status

approved