A192722 T(n,k) = Sum of multinomial(n; n_1,n_2,...,n_k)^2, where the sum extends over all compositions (n_1,n_2,...,n_k) of n into exactly k nonnegative parts.

1, 1, 4, 1, 18, 36, 1, 68, 432, 576, 1, 250, 3900, 14400, 14400, 1, 922, 32400, 252000, 648000, 518400, 1, 3430, 262542, 3880800, 19404000, 38102400, 25401600, 1, 12868, 2119152, 56664384, 493920000, 1795046400, 2844979200, 1625702400

Offset: 1

Author

Peter Bala, Jul 11 2011

Keywords

• nonn
• easy
• tabl

Comments

Compare with triangle A019538, whose entries are given by

... Sum multinomial(n; n_1,n_2,...,n_k), where the sum extends over all compositions (n_1,n_2,...,n_k) of n into exactly k nonnegative parts.

For related tables see A061691 and A192721.

Let P be the poset of all ordered pairs (S,T) of subsets of [n] with |S|=|T|, ordered componentwise by inclusion. T(n,k) is the number of length k chains in P from ({},{}) to ([n],[n]). - Geoffrey Critzer, Apr 15 2020

Examples

			The triangle begins
n/k|..1.....2.......3........4........5........6
================================================
.1.|..1
.2.|..1.....4
.3.|..1....18.....36
.4.|..1....68.....432......576
.5.|..1...250....3900....14400....14400
.6.|..1...922...32400...252000...648000...518400
...
T(4,2) = 68:
There are 3 compositions of 4 into 2 parts, namely, 4 = 2 + 2 = 1 + 3 = 3 + 1; hence
T(4,2) = (4!/(2!*2!))^2 + (4!/(1!*3!))^2 + (4!/(3!*1!))^2
= 36 + 16 + 16 = 68.
Matrix identity: A192721 * Pascal's triangle = row reverse of A192722:
/...1................\ /..1..............\
|...3.....1...........||..1....1..........|
|..19....16.....5.....||..1....2....1.....|
|.211...299....65....1||..1....3....3....1|
|.....................||..................|
=
/...1...................\
|...4......1.............|
|..36.....18......1......|
|.576....432.....68.....1|
|........................|
		

Links

• Alois P. Heinz, Rows n = 1..100, flattened

Crossrefs

Cf. A001044, A002190, A061691, A192721, A102221 (row sums), A000275 (alternating row sums).

Programs

Maple

J := unapply(BesselJ(0, 2*sqrt(-1)*sqrt(z)), z):
G := 1/(1-x*(J(z)-1)):
Gser := simplify(series(G, z = 0, 15)):
for n from 1 to 14 do
P[n] := n!^2*sort(coeff(Gser, z, n)) od:
for n from 1 to 14 do seq(coeff(P[n], x, k), k = 1..n) od;
# yields sequence in triangular form
# second Maple program:
b:= proc(n) option remember; expand(
      `if`(n=0, 1, add(x*b(n-i)/i!^2, i=1..n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n)*n!^2):
seq(T(n), n=1..14);  # Alois P. Heinz, Sep 10 2019

Mathematica

b[n_] := b[n] = Expand[If[n == 0, 1, Sum[x b[n-i]/i!^2, {i, 1, n}]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 1, n}]][b[n] n!^2];
Table[T[n], {n, 1, 14}] // Flatten (* Jean-François Alcover, Dec 07 2019, after Alois P. Heinz *)

Formula

Generating function: Let J(z) = Sum_{n>=0} z^n/n!^2. Then

1 + Sum_{n>=1} (Sum_{k = 1..n} T(n,k)*x^k)*z^n/n!^2 = 1/(1 - x*(J(z) - 1))

= 1 + x*z + (x + 4*x^2)*z^2/2!^2 + (x + 18*x^2 + 36*x^3)*z^3/3!^2 + ....

Relations with other sequences:

The change of variable z -> z/x followed by x -> 1/(x - 1) transforms the above bivariate generating function 1/(1 - x*(J(z) - 1)) into (1 - x)/(-x + J(z*(x-1))), which is the generating function for A192721.

1/k!*T(n,k) = A061691(n,k).

T(n,n) = n!^2 = A001044(n).

Row sums = A102221.

For n>=1, Sum_{k = 1..n} (-1)^(n+k)*T(n,k)/k = A002190(n).