A187925 -id:A187925 - cp's OEIS frontend

A305161 Number A(n,k) of compositions of n into exactly n nonnegative parts <= k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 3, 1, 0, 1, 1, 3, 7, 1, 0, 1, 1, 3, 10, 19, 1, 0, 1, 1, 3, 10, 31, 51, 1, 0, 1, 1, 3, 10, 35, 101, 141, 1, 0, 1, 1, 3, 10, 35, 121, 336, 393, 1, 0, 1, 1, 3, 10, 35, 126, 426, 1128, 1107, 1, 0, 1, 1, 3, 10, 35, 126, 456, 1520, 3823, 3139, 1, 0

Offset: 0

Alois P. Heinz, Aug 17 2018

			A(3,1) = 1: 111.
A(3,2) = 7: 012, 021, 102, 111, 120, 201, 210.
A(3,3) = 10: 003, 012, 021, 030, 102, 111, 120, 201, 210, 300.
A(4,2) = 19: 0022, 0112, 0121, 0202, 0211, 0220, 1012, 1021, 1102, 1111, 1120, 1201, 1210, 2002, 2011, 2020, 2101, 2110, 2200.
A(4,3) = 31: 0013, 0022, 0031, 0103, 0112, 0121, 0130, 0202, 0211, 0220, 0301, 0310, 1003, 1012, 1021, 1030, 1102, 1111, 1120, 1201, 1210, 1300, 2002, 2011, 2020, 2101, 2110, 2200, 3001, 3010, 3100.
Square array A(n,k) begins:
  1, 1,    1,    1,    1,    1,    1,    1,    1, ...
  0, 1,    1,    1,    1,    1,    1,    1,    1, ...
  0, 1,    3,    3,    3,    3,    3,    3,    3, ...
  0, 1,    7,   10,   10,   10,   10,   10,   10, ...
  0, 1,   19,   31,   35,   35,   35,   35,   35, ...
  0, 1,   51,  101,  121,  126,  126,  126,  126, ...
  0, 1,  141,  336,  426,  456,  462,  462,  462, ...
  0, 1,  393, 1128, 1520, 1667, 1709, 1716, 1716, ...
  0, 1, 1107, 3823, 5475, 6147, 6371, 6427, 6435, ...

Alois P. Heinz, Antidiagonals n = 0..200

Columns k=0-10 give: A000007, A000012, A002426, A005725, A187925, A318113, A318114, A318115, A318116, A167403, A318117.
Rows n=0-1 give: A000012, A057427.
Main diagonal gives A088218 or A001700(n-1) for n>0.
A(n+1,n) gives A048775.
Cf. A180281.

A:= (n, k)-> coeff(series(((x^(k+1)-1)/(x-1))^n, x, n+1), x, n):
seq(seq(A(n, d-n), n=0..d), d=0..12);
# second Maple program:
b:= proc(n, i, k) option remember; `if`(n=0, 1,
      `if`(i=0, 0, add(b(n-j, i-1, k), j=0..min(n, k))))
    end:
A:= (n, k)-> b(n$2, k):
seq(seq(A(n, d-n), n=0..d), d=0..12);

b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i == 0, 0, Sum[b[n - j, i - 1, k], {j, 0, Min[n, k]}]]];
A[n_, k_] := b[n, n, k];
Table[A[n, d - n], {d, 0, 12}, {n, 0, d}] // Flatten (* Jean-François Alcover, May 05 2019, after Alois P. Heinz *)

A(n,k) = [x^n] ((x^(k+1)-1)/(x-1))^n.
A(n,k) - A(n,k-1) = A180281(n,k) for n,k > 0.
A(n,k) = A(n,n) for all k >= n.

A213743 Triangle T(n,k), read by rows, of numbers T(n,k)=C^(4)(n,k) of combinations with repetitions from n different elements over k for each of them not more than four appearances allowed.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 1, 3, 6, 10, 1, 4, 10, 20, 35, 1, 5, 15, 35, 70, 121, 1, 6, 21, 56, 126, 246, 426, 1, 7, 28, 84, 210, 455, 875, 1520, 1, 8, 36, 120, 330, 784, 1652, 3144, 5475, 1, 9, 45, 165, 495, 1278, 2922, 6030, 11385, 19855, 1, 10, 55, 220, 715, 1992, 4905, 10890, 22110, 41470, 72403

Offset: 0

Vladimir Shevelev and Peter J. C. Moses, Jun 19 2012

The left side of triangle consists of 1's, while the right side is formed by A187925. Further, T(n,0)=1, T(n,1)=n, T(n,2)=A000217(n) for n>1, T(n,3)=A000292(n) for n>=3, T(n,4)=A000332(n) for n>=7, T(n,5)=A027659(n) for n>=3, T(n,6)=A064056(n) for n>=4, T(n,7)=A064057(n) for n>=5, T(n,8)=A064058(n) for n>=6, T(n,9)=A000575(n) for n>=6.

			Triangle begins
  n/k.|..0.....1.....2.....3.....4.....5.....6.....7
  ==================================================
  .0..|..1
  .1..|..1.....1
  .2..|..1.....2.....3
  .3..|..1.....3.....6....10
  .4..|..1.....4....10....20....35
  .5..|..1.....5....15....35....70....121
  .6..|..1.....6....21....56...126....246...426
  .7..|..1.....7....28....84...210....455...875....1520
T(4,2)=C^(4)(4,2): From 4 elements {1,2,3,4}, we have the following 10 allowed combinations of 2 elements: {1,1}, {1,2}, {1,3}, {1,4}, {2,2}, {2,3}, {2,4}, {3,3}, {3,4}, {4,4}.

Peter J. C. Moses, Rows n = 0..50 of triangle, flattened

Cf. A007318, A005725, A111808, A187925, A213742, A000217, A000292, A000332, A027659, A064056, A064057, A064058, A000575.

Flatten[Table[Sum[(-1)^r Binomial[n,r] Binomial[n-# r+k-1,n-1],{r,0,Floor[k/#]}],{n,0,15},{k,0,n}]/.{0}->{1}]&[5] (* Peter J. C. Moses, Apr 16 2013 *)

C^(4)(n,k) = Sum_{r=0...floor(k/5)} (-1)^r*C(n,r)*C(n-5*r+k-1, n-1).

A213744 Triangle of numbers C^(5)(n,k) of combinations with repetitions from n different elements over k for each of them not more than 5 appearances allowed.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 1, 3, 6, 10, 1, 4, 10, 20, 35, 1, 5, 15, 35, 70, 126, 1, 6, 21, 56, 126, 252, 456, 1, 7, 28, 84, 210, 462, 917, 1667, 1, 8, 36, 120, 330, 792, 1708, 3368, 6147, 1, 9, 45, 165, 495, 1287, 2994, 6354, 12465, 22825, 1, 10

Offset: 0

Vladimir Shevelev and Peter J. C. Moses, Jun 19 2012

For k<=4, the triangle coincides with triangle A213743.

We have over columns of the triangle: T(n,0)=1, T(n,1)=n, T(n,2)=A000217(n) for n>1, T(n,3)=A000292(n) for n>=3, T(n,4)=A000332(n) for n>=7, T(n,5)=A000389(n) for n>=9, T(n,6)=A062989(n) for n>=5, T(n,7)=A063262 for n>=5, T(n,8)=A063263 for n>=6, T(n,9)=A063264 for n>=7.

			Triangle begins
n/k.|..0.....1.....2.....3.....4.....5.....6.....7
==================================================
.0..|..1
.1..|..1.....1
.2..|..1.....2.....3
.3..|..1.....3.....6....10
.4..|..1.....4....10....20....35
.5..|..1.....5....15....35....70....126
.6..|..1.....6....21....56...126....252...456
.7..|..1.....7....28....84...210....462...917....1667

Peter J. C. Moses, Rows n = 0..50 of triangle, flattened

Cf. A007318, A005725, A111808, A187925, A213742, A213743, A000217, A000292, A000332, A000389, A062989, A063262, A063263, A063264.

Flatten[Table[Sum[(-1)^r Binomial[n,r] Binomial[n-# r+k-1,n-1],{r,0,Floor[k/#]}],{n,0,15},{k,0,n}]/.{0}->{1}]&[6] (* Peter J. C. Moses, Apr 16 2013 *)

C^(5)(n,k)=sum{r=0,...,floor(k/6)}(-1)^r*C(n,r)*C(n-6*r+k-1, n-1)

A213745 Triangle of numbers C^(6)(n,k) of combinations with repetitions from n different elements over k for each of them not more than 6 appearances allowed.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 1, 3, 6, 10, 1, 4, 10, 20, 35, 1, 5, 15, 35, 70, 126, 1, 6, 21, 56, 126, 252, 462, 1, 7, 28, 84, 210, 462, 924, 1709, 1, 8, 36, 120, 330, 792, 1716, 3424, 6371, 1, 9, 45, 165, 495, 1287, 3003, 6426, 12789, 23905, 1, 10

Offset: 0

Vladimir Shevelev and Peter J. C. Moses, Jun 19 2012

For k<=5, the triangle coincides with triangle A213744.

We have over columns of the triangle: T(n,0)=1, T(n,1)=n, T(n,2)=A000217(n) for n>1, T(n,3)=A000292(n) for n>=3, T(n,4)=A000332(n) for n>=7, T(n,5)=A000389(n) for n>=9, T(n,6)=A000579(n) for n>=11, T(n,7)=A063267 for n>=5, T(n,8)=A063417 for n>=6, T(n,9)=A063418 for n>=7.

			Triangle begins
n/k.|..0.....1.....2.....3.....4.....5.....6.....7
==================================================
.0..|..1
.1..|..1.....1
.2..|..1.....2.....3
.3..|..1.....3.....6....10
.4..|..1.....4....10....20....35
.5..|..1.....5....15....35....70....126
.6..|..1.....6....21....56...126....252...462
.7..|..1.....7....28....84...210....462...924....1709

Peter J. C. Moses, Rows n = 0..50 of triangle, flattened

Cf. A007318, A005725, A059481, A111808, A187925, A213742, A213743, A213744, A000217, A000292, A000332, A000389, A000579, A063267, A063417, A063418.

Flatten[Table[Sum[(-1)^r Binomial[n,r] Binomial[n-# r+k-1,n-1],{r,0,Floor[k/#]}],{n,0,15},{k,0,n}]/.{0}->{1}]&[7] (* Peter J. C. Moses, Apr 16 2013 *)

C^(6)(n,k)=sum{r=0,...,floor(k/7)}(-1)^r*C(n,r)*C(n-7*r+k-1, n-1).
A generalization. The numbers C^(t)(n,k) of combinations with repetitions from n different elements over k, for each of them not more than t>=1 appearances allowed, are enumerated by the formula:
C^(t)(n,k)=sum{r=0,...,floor(k/(t+1))}(-1)^r*C(n,r)*C(n-(t+1)*r+k-1, n-1).
In case t=1, it is binomial coefficient C^(t)(n,k)=C(n,k), and we have the combinatorial identity: sum{r=0,...,floor(k/2)}(-1)^r*C(n,r)*C(n-2*r+k-1, n-1)=C(n,k). On the other hand, if t=n, then r=0, and for the corresponding numbers of combinations with repetitions without a restriction on appearances of elements we obtain a well known formula C(n+k-1, n-1) (cf. triangle A059481).
In addition, note that, if k<=t, then C^(t)(n,k)=C(n+k-1, n-1). Therefore, triangle {C^(t+1)(n,k)} coincides with the previous triangle {C^(t)(n,k)} for k<=t.

A350407 a(n) = [x^n] 1/(1 + x + x^2 + x^3 + x^4)^n.

Original entry on oeis.org

1, -1, 1, -1, 1, 4, -35, 146, -447, 1133, -2464, 4355, -4355, -9296, 77078, -314636, 1006145, -2738565, 6398155, -12175809, 14621376, 14828330, -179236815, 786257460, -2625667395, 7412386254, -17983703880, 36057065030, -49553122730, -14585596720

Offset: 0

Seiichi Manyama, Dec 29 2021

Seiichi Manyama, Table of n, a(n) for n = 0..1000

Cf. A187925, A228960, A350383, A350406.

a := n -> (-1)^n*hypergeom([-n/5, 1/5 - n/5, 2/5 - n/5, 3/5 - n/5, 4/5 - n/5, n], [1/5, 2/5, 3/5, 4/5, 1], 1): seq(simplify(a(n)), n = 0..30); # Peter Bala, Apr 16 2023

a[n_] := Coefficient[Series[1/(1 + x + x^2 + x^3 + x^4)^n, {x, 0, n}], x, n]; Array[a, 30, 0] (* Amiram Eldar, Dec 29 2021 *)

a(n) = sum(k=0, n, (-1)^(n-k)*binomial(n-1+k, k)*binomial(n, 5*k));

a(n) = Sum_{k=0..n} (-1)^(n-k) * binomial(n-1+k,k) * binomial(n,5*k).
Recurrence: 125*(n-3)*(n-2)*(n-1)*n*(2*n - 7)*(3*n - 11)*(3*n - 8)*(6*n - 23)*(6*n - 17)*(6*n - 11)*a(n) = -50*(n-3)*(n-2)*(n-1)*(3*n - 11)*(6*n - 23)*(6*n - 17)*(576*n^4 - 4896*n^3 + 14402*n^2 - 16875*n + 6250)*a(n-1) - 30*(n-3)*(n-2)*(6*n - 23)*(6*n - 5)*(7884*n^6 - 123516*n^5 + 791601*n^4 - 2652565*n^3 + 4894096*n^2 - 4707500*n + 1842500)*a(n-2) - 2*(n-3)*(3*n - 5)*(6*n - 11)*(6*n - 5)*(60192*n^6 - 1113552*n^5 + 8528546*n^4 - 34608379*n^3 + 78470893*n^2 - 94255700*n + 46855500)*a(n-3) - 5*(2*n - 5)*(3*n - 8)*(3*n - 5)*(5*n - 19)*(5*n - 18)*(5*n - 17)*(5*n - 16)*(6*n - 17)*(6*n - 11)*(6*n - 5)*a(n-4). - Vaclav Kotesovec, Mar 18 2023
From Peter Bala, Apr 16 2023: (Start)
a(n) = (-1)^n*hypergeom([-n/5, 1/5 - n/5, 2/5 - n/5, 3/5 - n/5, 4/5 - n/5, n], [1/5, 2/5, 3/5, 4/5, 1], 1).
Conjecture: the supercongruence a(n*p^r) == a(n*p^(r-1)) (mod p^(2*r)) holds for positive integers n and r and all primes p >= 3. (End)

A333579 a(n) = [x^n] ( (1 + x + x^2)/(1 - x + x^2) )^n.

Original entry on oeis.org

1, 2, 8, 32, 128, 502, 1904, 6862, 22784, 64832, 120008, -223606, -4311424, -33271366, -205802344, -1142307968, -5919738880, -29159028386, -137718099760, -626077804826, -2740865583872, -11523690799904, -46214332516520, -174358991625134, -601230820510720

Offset: 0

Peter Bala, Mar 29 2020

If F(x) = 1 + f(1)*x + f(2)*x^2 + ... is a formal power series with integer coefficients then the sequence u(n) := [x^n] F(x)^n is an integer sequence satisfying the Gauss congruences: u(n*p^k) == u(n*p^(k-1)) ( mod p^k ) for all prime p and positive integers n and k. In particular u(p^k) == u(p^(k-1)) ( mod p^k ) for all prime p and positive integer k. For certain power series F(x) we may get stronger congruences.
According to Zhi-Wei Sun (see his comment in A002426 posted Nov 30, 2016), the central trinomial coefficients A002426(n) = [x^n] (1 + x + x^2)^n, satisfy the congruences A002426(p) == 1 ( mod p^2 ) for prime p >= 5. More generally, calculation suggests that the congruences A002426(p^k) == A002426(p^(k-1)) ( mod p^(2*k) ) hold for prime p >= 5 and any positive integer k.
We conjecture that the present sequence satisfies the congruences a(p) == 2 ( mod p^3 ) for prime p >= 5 (checked up to p = 499). Calculation suggests that a(p^k) == a(p^(k-1)) ( mod p^(2*k) ) for prime p >= 5 and k > 1.
More generally, if c(m,x) denotes the m-th cyclotomic polynomial then the sequences a(m,n) := [x^n] c(m,x)^n and b(m,n) := [x^n] ( c(m,x)/c(m,-x) )^n may satisfy the congruences a(m,p) == a(m,1) ( mod p^2 ) and b(m,p) == b(m,1) ( mod p^3 ), both for prime p >= 5, p not a divisor of m. The present sequence is b(3,n). Note that b(2,n) = A002003(n).

			Examples of congruences a(p) - a(1) == 0 ( mod p^3 ):
a(11) - a(1) = -223606 - 2 = -(2^3)*3*7*11^3 == 0 ( mod 11^3 )
a(19) - a(1) = -626077804826 - 2 = -(2^2)*7*(19^3)*151*21589 == 0 ( mod 19^3 )

Wikipedia, Cyclotomic polynomial

Cf. A002003, A002426, A187925, A318114.

seq(add(add(add((-1)^(n-k-i-j)*binomial(n, k)*binomial(k, i)*binomial(n+j-1, j)*binomial(j, n-k-i-j), j = 0..n-k-i), i = 0..n-k), k = 0..n), n = 0..25);
#alternative program
G := x -> (1 + x + x^2)/(1 - x + x^2):
H := (x,n) -> series(G(x)^n, x, n+1):
a:= n -> coeff(H(x, n), x, n):
seq(a(n), n = 0..25);

a[n_]:=SeriesCoefficient[((1 + x + x^2)/(1 - x + x^2))^n,{x,0,n}]; Array[a,25,0] (* Stefano Spezia, Apr 30 2024 *)

a(n) = polcoeff(((1 + x + x^2)/(1 - x + x^2))^n+ O(x^(n+1)), n, x); \\ Michel Marcus, Mar 31 2020

a(n) = Sum_{0 <= i,j,k <= n} (-1)^(n-k-i-j)*C(n,k)*C(k,i)*C(n+j-1,j)*C(j,n-k-i-j).

A213808 Triangle of numbers C^(7)(n,k) of combinations with repetitions from n different elements over k for each of them not more than 7 appearances allowed.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 1, 3, 6, 10, 1, 4, 10, 20, 35, 1, 5, 15, 35, 70, 126, 1, 6, 21, 56, 126, 252, 462, 1, 7, 28, 84, 210, 462, 924, 1716, 1, 8, 36, 120, 330, 792, 1716, 3432, 6427, 1, 9, 45, 165, 495, 1287, 3003, 6435, 12861, 24229, 1, 10, 55, 220, 715, 2002, 5005, 11440, 24300, 48520, 91828

Offset: 0

Vladimir Shevelev and Peter J. C. Moses, Jun 20 2012

For k <= 6, the triangle coincides with triangle A213745.

			Triangle begins
n/k |  0     1     2     3     4     5     6     7     8
----+---------------------------------------------------
  0 |  1
  1 |  1     1
  2 |  1     2     3
  3 |  1     3     6    10
  4 |  1     4    10    20    35
  5 |  1     5    15    35    70   126
  6 |  1     6    21    56   126   252   462
  7 |  1     7    28    84   210   462   924  1716
  8 |  1     8    36   120   330   792  1716  3432  6427

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened

Cf. A007318, A005725, A059481, A111808, A187925, A213742, A213743, A213744, A000217, A000292, A000332, A000389, A000579, A000580.

Table[Sum[(-1)^r*Binomial[n, r]*Binomial[n - 8*r + k - 1, n - 1], {r, 0, Floor[k/8]}], {n, 0, 10}, {k, 0, n}] // Flatten (* G. C. Greubel, Nov 25 2017 *)

for(n=0,10, for(k=0,n, print1(if(n==0 && k==0, 1, sum(r=0, floor(k/8), (-1)^r*binomial(n,r)*binomial(n-8*r + k-1,n-1))), ", "))) \\ G. C. Greubel, Nov 25 2017

T(n,k) = Sum_{r=0..floor(k/8)} (-1)^r*C(n,r)*C(n-8*r+k-1, n-1).

T(n,0)=1, T(n,1)=n, T(n,2)=A000217(n) for n > 1, T(n,3)=A000292(n) for n >= 3, T(n,4)=A000332(n) for n >= 7, T(n,5)=A000389(n) for n >= 9, T(n,6)=A000579(n) for n >= 11, T(n,7)=A000580(n) for n >= 13.

cp's OEIS Frontend

A305161 Number A(n,k) of compositions of n into exactly n nonnegative parts <= k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A213743 Triangle T(n,k), read by rows, of numbers T(n,k)=C^(4)(n,k) of combinations with repetitions from n different elements over k for each of them not more than four appearances allowed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A213744 Triangle of numbers C^(5)(n,k) of combinations with repetitions from n different elements over k for each of them not more than 5 appearances allowed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A213745 Triangle of numbers C^(6)(n,k) of combinations with repetitions from n different elements over k for each of them not more than 6 appearances allowed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A350407 a(n) = [x^n] 1/(1 + x + x^2 + x^3 + x^4)^n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A333579 a(n) = [x^n] ( (1 + x + x^2)/(1 - x + x^2) )^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A213808 Triangle of numbers C^(7)(n,k) of combinations with repetitions from n different elements over k for each of them not more than 7 appearances allowed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI