A240607 a(n) = 2*a(n-2) + a(n-3) + a(n-4) for n>=4, a(n) = binomial(n,3) for n<4.

0, 0, 0, 1, 0, 2, 1, 5, 4, 13, 14, 35, 45, 97, 139, 274, 420, 784, 1253, 2262, 3710, 6561, 10935, 19094, 32141, 55684, 94311, 162603, 276447, 475201, 809808, 1389452, 2371264, 4063913, 6941788, 11888542, 20318753, 34782785, 59467836, 101772865, 174037210

Offset: 0

Author

Christopher Hunt Gribble, Apr 09 2014

Keywords

• nonn
• easy

Comments

a(n) = term (4,1) in the 4 X 4 matrix [0,1,1,1; 1,0,1,0; 0,1,0,0; 0,0,1,0]^n. There are 96 ways to define the sequence as an element of the n-th power of a 4 X 4 {0,1}-matrix. These are listed in the second Gribble link.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 50 terms from Christopher Hunt Gribble)
• Christopher Hunt Gribble, Matrix elements
• Index entries for linear recurrences with constant coefficients, signature (0,2,1,1).

Crossrefs

Cf. A239748.

Programs

Maple

a:= proc(n) option remember; `if`(n<4, binomial(n, 3),
       2*a(n-2) +a(n-3) +a(n-4))
    end:
seq(a(n), n=0..50);
# second Maple program using the {0,1}-matrix:
a:= n-> (<<0|1|1|1>, <1|0|1|0>, <0|1|0|0>, <0|0|1|0>>^n)[4, 1]:
seq(a(n), n=0..50);  # Alois P. Heinz, Apr 26 2014

Mathematica

LinearRecurrence[{0,2,1,1},{0,0,0,1,0,2,1,5,4},50] (* Harvey P. Dale, Jul 01 2015 *)

PARI

concat([0,0,0], Vec(-x^3/(x^4+x^3+2*x^2-1) + O(x^100))) \\ Colin Barker, Apr 20 2014

Formula

G.f.: -x^3 / (x^4+x^3+2*x^2-1). - Colin Barker, Apr 20 2014

Extensions

More terms from Colin Barker, Apr 20 2014