login
Number of compositions of n with no part greater than 3 such that no two adjacent parts are equal.
2

%I #20 Mar 24 2024 03:20:37

%S 1,1,1,3,3,4,8,9,12,21,27,37,58,78,109,164,227,319,467,656,928,1341,

%T 1896,2689,3859,5477,7782,11126,15817,22496,32103,45679,65003,92668,

%U 131912,187777,267556,380941,542363,772581,1100098,1566414,2230997

%N Number of compositions of n with no part greater than 3 such that no two adjacent parts are equal.

%C Carlitz compositions with no part greater than 3.

%H D. I. Bevan, <a href="/A155822/b155822.txt">Table of n, a(n) for n = 0..5000</a>

%H Philippe Flajolet and Robert Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html">Analytic Combinatorics</a>, Cambridge Univ. Press, 2009, page 206.

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

%F From _David Bevan_, Feb 02 2009: (Start)

%F For n>5, a(n) = a(n-1) - a(n-2) + 2*a(n-3) - a(n-4) + 2*a(n-5).

%F For n>6, a(n) = a(n-3) + a(n-4) + a(n-5) + 2*a(n-6). (End)

%F G.f.: -(x+1)*(x^2-x+1)*(x^2+1) / (2*x^5-x^4+2*x^3-x^2+x-1). - _Colin Barker_, Feb 13 2013

%F G.f.: 1/(1 - Sum_{j=1..3} x^j/(1 + x^j) ) and generally for Carlitz compositions with no part greater than r the o.g.f. is 1/(1 - Sum_{j=1..r} x^j/(1 + x^j) ). - _Geoffrey Critzer_, Nov 21 2013

%e a(5) = 4 because we have 5 = 1 + 3 + 1 = 2 + 1 + 2 = 2 + 3 = 3+2.

%p From _David Bevan_, Feb 02 2009: (Start)

%p a := proc(k) if k=0 then 1 else b(1,k)+b(2,k)+b(3,k) fi end;

%p b := proc(r,k) option remember; if k<r then 0 elif k=r then 1 else b(1,k-r)+b(2,k-r)+b(3,k-r)-b(r,k-r) fi end; (End)

%t nn=20;CoefficientList[Series[1/(1-Sum[z^j/(1+z^j),{j,1,3}]),{z,0,nn}],z] (* _Geoffrey Critzer_, Nov 21 2013 *)

%Y Cf. A000073, A003242.

%K nonn,easy

%O 0,4

%A _David Bevan_, Jan 28 2009