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,6

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

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

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

Example

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

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

Crossrefs

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

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

Main diagonal gives A326321.

Cf. A183610.

Sequence in context: A320251 A210341 A160449 * A089940 A331598 A123974

Adjacent sequences: A326319 A326320 A326321 * A326323 A326324 A326325

Keyword

nonn,tabl

Author

Alois P. Heinz, Sep 11 2019

Status

approved