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

Author

David Bevan, Jan 28 2009

Keywords

• nonn
• easy

Comments

Carlitz compositions with no part greater than 3.

Examples

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

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).

Crossrefs

Cf. A000073, A003242.

Programs

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
				

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 *)

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