A059633 Expansion of g.f. x^3/(1 - 2*x + x^3 - x^4).

1, 2, 4, 7, 13, 24, 45, 84, 157, 293, 547, 1021, 1906, 3558, 6642, 12399, 23146, 43208, 80659, 150571, 281080, 524709, 979506, 1828503, 3413377, 6371957, 11894917, 22204960, 41451340, 77379720, 144449397, 269652414

Offset: 3

Author

James R. FitzSimons (cherry(AT)neta.com), Feb 19 2001

Keywords

• nonn
• easy

Links

• G. C. Greubel, Table of n, a(n) for n = 3..1003
• Kevin Beanland, Dmitriy Gorovoy, Jȩdrzej Hodor, and Daniil Homza, Counting Unions of Schreier Sets, arXiv:2211.01049 [math.CO], 2022. See p. 4.
• Jia Huang, A coin flip game and generalizations of Fibonacci numbers, arXiv:2501.07463 [math.CO], 2025. See p. 8.
• Index entries for linear recurrences with constant coefficients, signature (2,0,-1,1).

Crossrefs

I and J are A049856 while K and L are A059633 (with some offsets).

Programs

Magma

I:=[1,2,4,7]; [n le 4 select I[n] else 2*Self(n-1) - Self(n-3) + Self(n-4): n in [1..30]]; // G. C. Greubel, Apr 13 2023

Maple

with(combstruct): SeqSeqSeqL := [T, {T=Sequence(S), S=Sequence(U, card > 1), U=Sequence(Z, card >1)}, unlabeled]: seq(count(SeqSeqSeqL, size=j), j=4..35); # Zerinvary Lajos, Apr 04 2009

Mathematica

LinearRecurrence[{2,0,-1,1},{1,2,4,7},40] (* Harvey P. Dale, Dec 25 2022 *)

SageMath

@CachedFunction
def a(n): # a = A059633
    if (n<4): return (0,0,0,1,2,4,7)[n]
    else: return 2*a(n-1) - a(n-3) + a(n-4)
[a(n) for n in range(3,51)] # G. C. Greubel, Apr 13 2023

Formula

a(n) = 2*a(n-1) - a(n-3) + a(n-4).

Recurrence equations (A059633 is L(n)): I(n+1) = I(n) + J(n) + L(n); J(n+1) = I(n); K(n+1) = J(n) + K(n); L(n+1) = K(n); M(n+1) = L(n) + 2M(n); initial conditions: I(0) = 1; J(0) = 0; K(0) = 0; L(0) = 0; M(0) = 0. Values for n = 0 1 2 3 4 5 6 7 8 ...: I(n) = 1 1 2 3 6 11 21 39 73 ... J(n) = 0 1 1 2 3 6 11 21 39 ... K(n) = 0 0 1 2 4 7 13 24 45 ... L(n) = 0 0 0 1 2 4 7 13 24 ... M(n) = 0 0 0 0 1 4 12 31 75 ...

a(n) = A049856(n+2) - A049856(n+1) - A049856(n) + A049856(n-1).

For n >= 2, a(n+1) = Sum_{i=0..n} Fibonacci(i)*binomial(n-i, i). - Benoit Cloitre, Sep 21 2004

a(n) = Sum_{k=0..n+1} C(k+1, n-k+1)*Fibonacci(n-k+1) [offset 0]. - Paul Barry, Feb 23 2005

Extensions

Comments and more terms from Henry Bottomley, Feb 21 2001

New description from Vladeta Jovovic, Jan 17 2004