login
A155822
Number of compositions of n with no part greater than 3 such that no two adjacent parts are equal.
2
1, 1, 1, 3, 3, 4, 8, 9, 12, 21, 27, 37, 58, 78, 109, 164, 227, 319, 467, 656, 928, 1341, 1896, 2689, 3859, 5477, 7782, 11126, 15817, 22496, 32103, 45679, 65003, 92668, 131912, 187777, 267556, 380941, 542363, 772581, 1100098, 1566414, 2230997
OFFSET
0,4
COMMENTS
Carlitz compositions with no part greater than 3.
LINKS
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 206.
FORMULA
From David Bevan, Feb 02 2009: (Start)
For n>5, a(n) = a(n-1) - a(n-2) + 2*a(n-3) - a(n-4) + 2*a(n-5).
For n>6, a(n) = a(n-3) + a(n-4) + a(n-5) + 2*a(n-6). (End)
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
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
EXAMPLE
a(5) = 4 because we have 5 = 1 + 3 + 1 = 2 + 1 + 2 = 2 + 3 = 3+2.
MAPLE
From David Bevan, Feb 02 2009: (Start)
a := proc(k) if k=0 then 1 else b(1, k)+b(2, k)+b(3, k) fi end;
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)
MATHEMATICA
nn=20; CoefficientList[Series[1/(1-Sum[z^j/(1+z^j), {j, 1, 3}]), {z, 0, nn}], z] (* Geoffrey Critzer, Nov 21 2013 *)
CROSSREFS
Sequence in context: A357306 A285445 A327745 * A160646 A019466 A111573
KEYWORD
nonn,easy
AUTHOR
David Bevan, Jan 28 2009
STATUS
approved