1,5

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.

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). [From Alois P. Heinz (heinz(AT)hs-heilbronn.de), Oct 07 2008]

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.

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); [From Alois P. Heinz (heinz(AT)hs-heilbronn.de), Oct 07 2008]

Adjacent sequences: A133922 A133923 A133924 this_sequence A133926 A133927 A133928

Sequence in context: A054656 A080096 A068915 this_sequence A071492 A096067 A098861

easy,nonn

Joel Lewis (jblewis(AT)post.harvard.edu), Jan 07 2008