login
A123908
Number of sequences with terms 1, 2 or 3 summing to n with no three consecutive 1's.
1
1, 1, 2, 3, 6, 10, 17, 30, 52, 90, 156, 271, 470, 815, 1414, 2453, 4255, 7381, 12804, 22211, 38529, 66836, 115940, 201120, 348881, 605201, 1049837, 1821143, 3159121, 5480100, 9506282, 16490465, 28605867, 49622350, 86079461, 149321296
OFFSET
0,3
FORMULA
a(n) = a(n-2) + 2*a(n-3) + 2*a(n-4) + a(n-5).
G.f.: (1 + x + x^2)/(1 - x^2 - 2*x^3 - 2*x^4 - x^5). - Chai Wah Wu, May 28 2016
EXAMPLE
a(4) = 6 as 3 + 1, 1 + 3, 2 + 2, 1 + 1 + 2, 1 + 2 + 1 and 2 + 1 + 1 (but not 1 + 1 + 1 + 1).
MAPLE
a[0]:=1; a[1]:=1; a[2]:=2; a[3]:=3; a[4]:=6; for n from 5 to 45 do a[n] := a[n-2] +2*a[n-3] +2*a[n-4] +a[n-5] end do; seq(a[n], n = 0 .. 40); # modified by G. C. Greubel, Aug 06 2019
seq(coeff(series((1+x+x^2)/(1-x^2-2*x^3-2*x^4-x^5), x, n+1), x, n), n = 0 .. 40); # G. C. Greubel, Aug 06 2019
MATHEMATICA
LinearRecurrence[{0, 1, 2, 2, 1}, {1, 1, 2, 3, 6}, 40] (* G. C. Greubel, Aug 06 2019 *)
PROG
(PARI) my(x='x+O('x^40)); Vec((1+x+x^2)/(1-x^2-2*x^3-2*x^4-x^5)) \\ G. C. Greubel, Aug 06 2019
(Magma) R<x>:=PowerSeriesRing(Integers(), 40); Coefficients(R!( (1+x+x^2)/(1-x^2-2*x^3-2*x^4-x^5) )); // G. C. Greubel, Aug 06 2019
(Sage) ((1+x+x^2)/(1-x^2-2*x^3-2*x^4-x^5)).series(x, 40).coefficients(x, sparse=False) # G. C. Greubel, Aug 06 2019
(GAP) a:=[1, 1, 2, 3, 6];; for n in [6..40] do a[n]:=a[n-2]+2*a[n-3]+ 2*a[n-4]+a[n-5]; od; a; # G. C. Greubel, Aug 06 2019
CROSSREFS
Sequence in context: A245437 A285665 A135431 * A233268 A026397 A193200
KEYWORD
easy,nonn
AUTHOR
Joel B. Lewis, Oct 28 2006
STATUS
approved