A123908 Number of sequences with terms 1, 2 or 3 summing to n with no three consecutive 1's.

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

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (0,1,2,2,1).

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

Adjacent sequences: A123905 A123906 A123907 * A123909 A123910 A123911

Keyword

easy,nonn

Author

Joel B. Lewis, Oct 28 2006

Status

approved