A124062 Number of ways to write n as an ordered sum of 1's, 2's and 3's such that no 2 precedes any 1.

1, 1, 2, 3, 5, 8, 12, 19, 29, 44, 67, 101, 152, 228, 341, 509, 758, 1127, 1673, 2480, 3672, 5431, 8025, 11848, 17479, 25769, 37968, 55912, 82297, 121081, 178074, 261803, 384781, 565368, 830500, 1219691, 1790901, 2629140, 3859083, 5663565, 8310696

Offset

0,3

Comments

Also, number of sequences composed of 1's and 2's summing to n which does not contain "...22...11..." where "..." is any (potentially empty) string. So for example, a[7] = 19 because there are 21 sequences without the restriction, but we must exclude 12211 and 22111. The bijection is to interchange "3" with "21." Also, satisfies the recursion a(n)=a(n-1)+a(n-2)+a(n-3)-a(n-4)-a(n-5)-a(n-6). - Joel B. Lewis, Nov 06 2006

Links

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

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

Formula

Sum( binomial(n-b-2c, c), (b = 0..floor[(n -3c)/2]), (c = 0..floor[n/3]) )

G.f.: A(x) = (1 - x^3) / ((1 - x - x^3)(1 - x^2 - x^3)) = (1 - x^3) / (1 - x - x^2 - x^3 + x^4 + x^5 + x^6)

a(n) = a(n-1) +a(n-2) +a(n-3) -a(n-4) -a(n-5) -a(n-6). - Joel B. Lewis, Nov 06 2006

a(n) = A000930(n+3) - A000931(n+7). - R. J. Mathar, Jul 10 2012

Example

a(4) = 5 because we can write 4 = 1+1+1+1 = 1+1+2 = 2+2 = 1+3 = 3+1

Mathematica

Sum[Sum[Binomial[n-b-2c, c], {b, 0, Floor[(n-3c)/2]}], {c, 0, Floor[n/3]}]
CoefficientList[Series[(1 - x^3)/((1 - x - x^3)*(1 - x^2 - x^3)), {x, 0, 50}], x] (* G. C. Greubel, Apr 29 2017 *)

Prog

(PARI) x='x+O('x^50); Vec((1 - x^3)/((1 - x - x^3)*(1 - x^2 - x^3))) \\ G. C. Greubel, Apr 29 2017

Crossrefs

Sequence in context: A369696 A355975 A327421 * A274199 A099823 A358335

Adjacent sequences: A124059 A124060 A124061 * A124063 A124064 A124065

Keyword

easy,nonn

Author

Joel B. Lewis, Nov 03 2006, Nov 11 2006

Status

approved