cp's OEIS Frontend

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

%I A155822 #20 Mar 24 2024 03:20:37
%S A155822 1,1,1,3,3,4,8,9,12,21,27,37,58,78,109,164,227,319,467,656,928,1341,
%T A155822 1896,2689,3859,5477,7782,11126,15817,22496,32103,45679,65003,92668,
%U A155822 131912,187777,267556,380941,542363,772581,1100098,1566414,2230997
%N A155822 Number of compositions of n with no part greater than 3 such that no two adjacent parts are equal.
%C A155822 Carlitz compositions with no part greater than 3.
%H A155822 D. I. Bevan, <a href="/A155822/b155822.txt">Table of n, a(n) for n = 0..5000</a>
%H A155822 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 A155822 <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (1,-1,2,-1,2).
%F A155822 From _David Bevan_, Feb 02 2009: (Start)
%F A155822 For n>5, a(n) = a(n-1) - a(n-2) + 2*a(n-3) - a(n-4) + 2*a(n-5).
%F A155822 For n>6, a(n) = a(n-3) + a(n-4) + a(n-5) + 2*a(n-6). (End)
%F A155822 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 A155822 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 A155822 a(5) = 4 because we have 5 = 1 + 3 + 1 = 2 + 1 + 2 = 2 + 3 = 3+2.
%p A155822 From _David Bevan_, Feb 02 2009: (Start)
%p A155822 a := proc(k) if k=0 then 1 else b(1,k)+b(2,k)+b(3,k) fi end;
%p A155822 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 A155822 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 A155822 Cf. A000073, A003242.
%K A155822 nonn,easy
%O A155822 0,4
%A A155822 _David Bevan_, Jan 28 2009