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
Index entries for linear recurrences with constant coefficients, signature (-1, 0, 1, 1, 1).
FORMULA
a(n) = -a(n-1) + a(n-3) + a(n-4) + a(n-5).
G.f.: (x^2+2*x+2) / (1+x-x^4-x^3-x^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+x-x^4-x^3-x^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
KEYWORD
easy,nonn
AUTHOR
Joel B. Lewis, Jan 07 2008
STATUS
approved