A326322 Square array A(n,k), n>=0, k>=0, read by antidiagonals: A(n,k) = sum of the k-th powers of multinomials M(n; mu), where mu ranges over all compositions of n.

1, 1, 1, 1, 1, 2, 1, 1, 3, 4, 1, 1, 5, 13, 8, 1, 1, 9, 55, 75, 16, 1, 1, 17, 271, 1077, 541, 32, 1, 1, 33, 1459, 19353, 32951, 4683, 64, 1, 1, 65, 8263, 395793, 2699251, 1451723, 47293, 128, 1, 1, 129, 48115, 8718945, 262131251, 650553183, 87054773, 545835, 256

Offset: 0

Author

Alois P. Heinz, Sep 11 2019

Keywords

• nonn
• tabl

Comments

For k>=1, A(n,k) is the number of k-tuples (p_1,p_2,...,p_k) of ordered set partitions of [n] such that the sequence of block lengths in each ordered partition p_i is identical. Equivalently, A(n,k) is the number of chains from s to t where [s,t] is any n-interval in the binomial poset B_k = B*B*...*B (k times), B is the lattice of all finite subsets of {1,2,...} ordered by inclusion and * is the Segre product. See Stanley reference. - Geoffrey Critzer, Dec 16 2020

Examples

			A(2,2) = M(2; 2)^2 + M(2; 1,1)^2 = 1 + 4 = 5.
Square array A(n,k) begins:
   1,   1,     1,       1,         1,           1, ...
   1,   1,     1,       1,         1,           1, ...
   2,   3,     5,       9,        17,          33, ...
   4,  13,    55,     271,      1459,        8263, ...
   8,  75,  1077,   19353,    395793,     8718945, ...
  16, 541, 32951, 2699251, 262131251, 28076306251, ...
		

References

• R. P. Stanley, Enumerative Combinatorics, Vol. I, second edition, Example 3.18.3d page 322.

Links

• Alois P. Heinz, Antidiagonals n = 0..60, flattened
• Wikipedia, Multinomial coefficients

Crossrefs

Columns k=0-2 give: A011782, A000670, A102221.

Rows n=0+1, 2 give A000012, A000051.

Main diagonal gives A326321.

Cf. A183610.

Programs

Maple

b:= proc(n, k) option remember; `if`(n=0, 1,
      add(b(n-i, k)/i!^k, i=1..n))
    end:
A:= (n, k)-> n!^k*b(n, k):
seq(seq(A(n, d-n), n=0..d), d=0..12);
# second Maple program:
A:= proc(n, k) option remember; `if`(n=0, 1,
      add(binomial(n, j)^k*A(j, k), j=0..n-1))
    end:
seq(seq(A(n, d-n), n=0..d), d=0..12);

Mathematica

A[n_, k_] := A[n, k] = If[n==0, 1, Sum[Binomial[n, j]^k A[j, k], {j, 0, n-1}]];
Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 12}] // Flatten  (* Jean-François Alcover, Dec 03 2020, after 2nd Maple program *)

Formula

Let E_k(x) = Sum_{n>=0} x^n/n!^k. Then 1/(2-E_k(x)) = Sum_{n>=0} A(n,k)*x^n/n!^k. - Geoffrey Critzer, Dec 16 2020