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

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

D. I. Bevan, Table of n, a(n) for n = 0..5000

Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 206.

Index entries for linear recurrences with constant coefficients, signature (1,-1,2,-1,2).

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

Cf. A000073, A003242.

Sequence in context: A357306 A285445 A327745 * A160646 A019466 A111573

Adjacent sequences: A155819 A155820 A155821 * A155823 A155824 A155825

Keyword

nonn,easy

Author

David Bevan, Jan 28 2009

Status

approved