The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors to the OEIS 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
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
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 24 15:28 EDT 2024. Contains 372778 sequences. (Running on oeis4.)