login
Number of compositions of n with no consecutive 2's.
2

%I #39 Aug 03 2020 01:29:49

%S 1,1,2,4,7,14,28,54,105,205,399,777,1514,2949,5744,11189,21795,42454,

%T 82696,161083,313772,611194,1190540,2319043,4517245,8799105,17139705,

%U 33386292,65032887,126677032,246753161,480648477,936251262,1823716224,3552402011,6919695006,13478817664,26255279382,51142445325

%N Number of compositions of n with no consecutive 2's.

%H Vincenzo Librandi, <a href="/A239791/b239791.txt">Table of n, a(n) for n = 0..1000</a>

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (2,-1,2,-1,1).

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

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

%F 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

%F 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

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

%t 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]

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

%o (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

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

%K nonn,easy

%O 0,3

%A _Geoffrey Critzer_, Mar 26 2014