login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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(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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 27 03:05 EDT 2021. Contains 347673 sequences. (Running on oeis4.)