A368475 Expansion of o.g.f. (1-x)^5/((1-x)^5 - x^4).

1, 0, 0, 0, 1, 5, 15, 35, 71, 136, 265, 550, 1211, 2732, 6126, 13485, 29191, 62648, 134408, 289656, 627401, 1363124, 2963186, 6434484, 13951852, 30221185, 65442625, 141745045, 307137901, 665732417, 1443184210, 3128438335, 6780867186, 14696002913, 31848721632

Offset: 0

Author

Enrique Navarrete, Dec 26 2023

Keywords

• nonn
• easy

Comments

For n > 0, a(n) is the number of ways to split [n] into an unspecified number of intervals and then choose 4 blocks (i.e., subintervals) from each interval. For example, for n=12, a(12)=1211 since the number of ways to split [12] into intervals and then select 4 blocks from each interval is C(12,4) + C(8,4)*C(4,4) + C(7,4)*C(5,4) + C(6,4)*C(6,4) + C(5,4)*C(7,4) + C(4,4)*C(8,4) + C(4,4)*C(4,4)*C(4,4) for a total of 1211 ways.

For n > 0, a(n) is also the number of compositions of n using parts of size at least 4 where there are binomial(i,4) types of i, i >= 4 (see example).

Number of compositions of 5*n-4 into parts 4 and 5. - Seiichi Manyama, Feb 01 2024

Examples

			Since there are C(4,4) = 1 type of 4, C(5,4) = 5 types of 5, C(6,4) = 15 types of 6, C(7,4) = 35 types of 7, C(8,4) = 70 types of 8, and (12,4) = 495 types of 12, we can write 12 in the following ways:
  12: 495 ways;
  8+4: 70 ways;
  7+5: 175 ways;
  6+6: 225 ways;
  5+7: 175 ways;
  4+8: 70 ways;
  4+4+4: 1 way, for a total of 1211 ways.
		

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-4,1).

Crossrefs

Cf. A000332, A017827, A099131, A290998.

Cf. A079675, A369803, A369804.

Cf. A088305, A095263, A290998, A369794, A369809.

Programs

Mathematica

CoefficientList[Series[(1 - x)^5/((1 - x)^5 - x^4), {x, 0, 50}], x] (* Wesley Ivan Hurt, Dec 26 2023 *)

PARI

Vec((1-x)^5/((1-x)^5 - x^4) + O(x^40)) \\ Michel Marcus, Dec 27 2023

Formula

a(n) = 5*a(n-1) - 10*a(n-2) + 10*a(n-3) - 4*a(n-4) + a(n-5), n>=6; a(0)=1, a(1)=a(2)=a(3)=0, a(4)=1, a(5)=5.

G.f.: 1/(1-Sum_{k>=4} binomial(k,4)*x^k).

G.f.: 1/p(S), where p(S) = 1 - S^4 - S^5 and S = x/(1-x).

First differences of A099131. - R. J. Mathar, Jan 29 2024

a(n) = A017827(5*n-4) = Sum_{k=0..floor((5*n-4)/4)} binomial(k,5*n-4-4*k) for n > 0. - Seiichi Manyama, Feb 01 2024

a(n) = Sum_{k=0..floor(n/4)} binomial(n-1+k,n-4*k). - Seiichi Manyama, Feb 02 2024