A318114 -id:A318114 - 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.

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).

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