A145131 Expansion of x/((1 - x - x^4)*(1 - x)^2).

0, 1, 3, 6, 10, 16, 25, 38, 56, 81, 116, 165, 233, 327, 457, 637, 886, 1230, 1705, 2361, 3267, 4518, 6245, 8629, 11920, 16463, 22734, 31390, 43338, 59830, 82594, 114015, 157385, 217248, 299876, 413926, 571347, 788632, 1088546, 1502511, 2073898, 2862571

Offset: 0

Author

Alois P. Heinz, Oct 03 2008

Keywords

• nonn
• easy

Comments

The coefficients of the recursion for a(n) are given by the 3rd row of A145152.

Comment from - Enrique Navarrete, May 25 2020: (Start)

a(n-4) is the number of subsets of {1,2,...,n} such that the difference of successive elements is at least 4. For example, for n = 9, a(5) = 16 and the subsets are: {1,5}, {1,6}, {1,7}, {1,8}, {1,9}, {2,6}, {2,7}, {2,8}, {2,9}, {3,7}, {3,8}, {3,9}, {4,8}, {4,9}, {5,9}, {1,5,9}.

For n >=0 the sequence contains the triangular numbers; for n >= 4 have to add the tetrahedral numbers; for n >= 8 have to add the numbers binomial(n,4) (starting with 0,1,5,..); for n >= 12 have to add the numbers binomial(n,5) (starting with 0,1,6,..); in general, for n >= 4*k have to add to the sequence the numbers binomial(n, k+2), k >= 0.

For example, a(15) = 120+286+210+21, where 120 is a triangular number, 286 is a tetrahedral number, 210 is a number binomial(n,4) and 21 is a number binomial(m,5) (with the proper n, m due to shifts in the names of the sequences).

First difference is A098578.

(End)

Examples

			a(7) = 38 = 3*25 -3*16 +10 +6 -2*3 +1.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (3,-3,1,1,-2,1).

Crossrefs

3rd column of A145153. Cf. A145152.

Programs

Maple

col:= proc(k) local l, j, M, n; l:= `if` (k=0, [1, 0, 0, 1], [seq(coeff( -(1-x-x^4) *(1-x)^(k-1), x, j), j=1..k+3)]); M:= Matrix(nops(l), (i,j)-> if i=j-1 then 1 elif j=1 then l[i] else 0 fi); `if`(k=0, n->(M^n)[2,3], n->(M^n)[1,2]) end: a:= col(3): seq(a(n), n=0..40);

Mathematica

Series[x/((1-x-x^4)*(1-x)^2), {x, 0, 50}] // CoefficientList[#, x]& (* Jean-François Alcover, Feb 13 2014 *)
LinearRecurrence[{3,-3,1,1,-2,1},{0,1,3,6,10,16},50] (* Harvey P. Dale, Aug 08 2015 *)

PARI

concat(0,Vec(1/(1-x-x^4)/(1-x)^2+O(x^99))) \\ Charles R Greathouse IV, Sep 25 2012

Formula

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