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

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

Links

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

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

Example

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

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

Crossrefs

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

Sequence in context: A077102 A258152 A259051 * A300141 A057968 A141233

Adjacent sequences: A192719 A192720 A192721 * A192723 A192724 A192725

Keyword

nonn,easy,tabl

Author

Peter Bala, Jul 11 2011

Status

approved