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

1, 2, 3, 5, 7, 12, 17, 26, 37, 57, 80, 119, 168, 247, 346, 503, 705, 1014, 1417, 2026, 2827, 4015, 5595, 7912, 11009, 15505, 21554, 30260, 42020, 58837, 81639, 114054, 158137, 220521, 305563, 425432, 589179, 819234, 1134015, 1575053, 2179376

Offset

0,2

Comments

This sequence, along with A124062, are the first two of a sequence of sequences which interpolate between the Fibonacci numbers, A000045 and the partition numbers, A000041.

Links

Table of n, a(n) for n=0..40.

Formula

G.f.: A(x) = (1 - x^4)^2 / ((1 - x - x^4)(1 - x^2 - x^4)(1 - x^3 - x^4)) a(n+12) = a(n+11) + a(n+10) + 2a(n+8) - 3a(n+7) - a(n+6) - a(n+5) - 2a(n+4) + 2a(n+3) + a(n+2) + a(n+1) + a(n)

Example

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

Mathematica

CoefficientList[Normal[Series[ -((x^4 + x^3 - 1)(x^4 + x^2 - 1)(x^4 + x - 1))^(-1) (1 - 2x^4 + x^8), {x, 0, 40}]], x]

Crossrefs

Cf. A124062.

Sequence in context: A308992 A326468 A326593 * A305651 A318185 A048816

Adjacent sequences: A123566 A123567 A123568 * A123570 A123571 A123572

Keyword

easy,nonn

Author

Joel B. Lewis, Nov 12 2006

Status

approved