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
KEYWORD
nonn,easy
AUTHOR
David Bevan, Jan 28 2009
STATUS
approved