

A133925


Number of compositions of n into parts of size 2 and 3 with no three consecutive 2s and no two consecutive 3s.


1



0, 1, 1, 1, 2, 0, 3, 1, 2, 3, 1, 5, 1, 5, 4, 3, 8, 2, 10, 5, 8, 12, 5, 18, 7, 18, 17, 13, 30, 12, 36, 24, 31, 47, 25, 66, 36, 67, 71, 56, 113, 61, 133, 107, 123, 184, 117, 246, 168, 256, 291, 240, 430, 285, 502, 459, 496, 721, 525, 932, 744, 998, 1180, 1021, 1653, 1269, 1930
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,5


COMMENTS

We give a combinatorial proof of the claimed recursion. We use the phrase "good compositions" to mean "compositions of the desired sort, i.e. into parts of size 2 or 3 with no three consecutive 2s or two consecutive 3s." Take n >= 7. Then good compositions of n and (n  1) beginning with 3 are in bijection with good compositions of (n  3) and (n  4) beginning with 2  remove the leading 3. Good compositions of n beginning with 23 are in bijection with good compositions of (n  5) beginning with 2  remove the leading 23. Good compositions of n and (n  1) beginning with 223 are in bijection with good compositions of (n  4) and (n  5) beginning with 3  remove the leading 22. And good compositions of (n  1) beginning with 23 are in bijection with good compositions of (n  3) beginning with 3  remove the leading 2. Taken together, this gives that good compositions of n and (n  1) are in bijection with good compositions of (n  3), (n  4) and (n  5), so a(n) = a(n  1) + a(n  3) + a(n  4) + a(n  5). A000931(n + 3) gives the number of compositions of n into parts of size 2 and 3 without any additional restrictions.


LINKS

Table of n, a(n) for n=1..67.
Index entries for linear recurrences with constant coefficients, signature (1, 0, 1, 1, 1).


FORMULA

a(n) = a(n1) + a(n3) + a(n4) + a(n5).
G.f.: (x^2+2*x+2) / (1+xx^4x^3x^5).  Alois P. Heinz, Oct 07 2008


EXAMPLE

a(5) = 2 because we have 5 = 2 + 3 = 3 + 2. a(6) = 0 because the only ways to write 6 as a sum of 2s and 3s are 6 = 2 + 2 + 2 = 3 + 3.


MAPLE

a:= n> (Matrix([[1$3, 0, 2]]). Matrix(5, (i, j)> if i+1=j then 1 elif j=1 then [ 1, 0, 1$3][i] else 0 fi)^n)[1, 5]: seq(a(n), n=1..67); # Alois P. Heinz, Oct 07 2008


MATHEMATICA

Rest[CoefficientList[Series[(x^2+2x+2)/(1+xx^4x^3x^5), {x, 0, 100}], x]] (* Harvey P. Dale, Apr 01 2011 *)
LinearRecurrence[{1, 0, 1, 1, 1}, {0, 1, 1, 1, 2}, 20] (* T. D. Noe, Apr 01 2011 *)


CROSSREFS

Sequence in context: A294142 A068915 A302193 * A071492 A259598 A096067
Adjacent sequences: A133922 A133923 A133924 * A133926 A133927 A133928


KEYWORD

easy,nonn


AUTHOR

Joel B. Lewis, Jan 07 2008


STATUS

approved



