Multinomial coefficients

This article page is a stub, please help by expanding it.

The are two versions of [

k

-nomial] multinomial coefficients: [

k

-variate] or [univariate].

[k-variate k-nomial] multinomial coefficients

The

[

k

-variate

k

-nomial] multinomial coefficients
     

(n1, n2, ..., nk  )!  :=  ( n1 + n2 + ⋯ + nk n1, n2, ..., nk )  :=  (n1 + n2 + ⋯ + nk  )! n1! n2! ⋯ nk ! , k  ≥ 1,

where

n!

is a factorial, are a generalization of the [2-variate 2-nomial] binomial coefficients for the [

k

-variate

k

-nomial] multinomials

$\begin{array}{l}{\left(\sum _{i=1}^k{x}_i\right)}^n=\sum _{\genfrac{}{}{0ex}{}{n_i\ge 0,1\le i\le k}{\sum _{i=1}^k{n}_i=n}}(n_1,n_2,\dots ,n_k)!\prod _{i=1}^k{x_i}^{n_i},k\ge 1.\end{array}$

For the degenerate case

k  = 1

(“[1-variate] monomial coefficients”!), we have

(n1 )! = 1

.

[Univariate k-nomial] multinomial coefficients

For [univariate

m

-nomial] multinomial coefficients, see: integer compositions into n parts of size at most m.

The

[univariate

k

-nomial] multinomial coefficients,

k   ≥   2

, given by the recurrence relation

Ck (0, 0)  :=  1;

Ck (n ,   j )  :=    j ∑   i  =  j − (k  − 1) n    Ck (n − 1, i ), n ≥ 1, 0 ≤   j ≤ (k  − 1) n,

where

Ck (n,   j )   :=   0

for

j < 0

or

j > (k  −  1) n

, are a generalization of the [univariate 2-nomial] binomial coefficients for the [univariate

k

-nomial] multinomials

k   − 1 ∑   i  = 0    x i     n  =    (k   − 1) n ∑   j  = 0    Ck (n ,   j ) x   j

.

For the degenerate case

k  = 1

(“[univariate] monomial coefficients”!), we have

Ck (n, 0) = 1

.

Trinomial coefficients

Trivariate trinomial coefficients

The [trivariate] trinomial coefficients

(n1, n2, n3 )!

appear in the series expansion of the

n

th power of the trivariate trinomial

     $\begin{array}{l}(x_1+x_2+x_3{)}^n=\sum _{\genfrac{}{}{0ex}{}{n_1,n_2,n_3\ge 0}{n_1+n_2+n_3=n}}(\genfrac{}{}{0ex}{}{n}{n_1,n_2,n_3}){x_1}^{n_1}{x_2}^{n_2}{x_3}^{n_3}.\end{array}$

The [trivariate] trinomial coefficients, where

n

is the layer,

j

is the row, and

k

is the column, are obtained by the recurrence relation

(0, 0, 0)!  :=  1;

(n ,   j , k )!  :=  (n − 1,   j − 1, k − 1)! + (n − 1,   j − 1, k )! + (n − 1,   j , k )!, n ≥ 1, 0 ≤   j ≤ n, 0 ≤ k ≤   j,

where

(n,   j , k )!   :=   0

for

j < 0

or

j > n

or

k < 0

or

k >   j

.
The [trivariate] trinomial coefficients form a 3-dimensional tetrahedral array of coefficients, where each of the

tn  + 1

terms of the

n

th layer is the sum of the 3 closest terms of the

(n  −  1)

th layer.

Pascal’s tetrahedron
(Pascal’s [triangular] pyramid)

Layer 0 (top layer)	1
Layer 1	1 1 1
Layer 2	1 2 2 1 2 1
Layer 3	1 3 3 3 6 3 1 3 3 1
Layer 4	1 4 4 6 12 6 4 12 12 4 1 4 6 4 1
Layer 5	1 5 5 10 20 10 10 30 30 10 5 20 30 20 5 1 5 10 10 5 1

A046816 Pascal’s tetrahedron: entries in 3-dimensional version of Pascal’s triangle, or [trivariate] trinomial coefficients.

{1, 1, 1, 1, 1, 2, 2, 1, 2, 1, 1, 3, 3, 3, 6, 3, 1, 3, 3, 1, 1, 4, 4, 6, 12, 6, 4, 12, 12, 4, 1, 4, 6, 4, 1, 1, 5, 5, 10, 20, 10, 10, 30, 30, 10, 5, 20, 30, 20, 5, 1, 5, 10, 10, 5, 1, 1, 6, 6, 15, 30, 15, 20, 60, 60, 20, 15, 60, 90, 60, 15, 6, 30, 60, 60, 30, 6, 1, 6, 15, 20, 15, 6, 1, ...}

Univariate trinomial coefficients

The [univariate] trinomial coefficients

C3(n,   j )

appear in the series expansion of the

n

th power of the [univariate] trinomial

(x 1 + x 2 + x 3 ) n  =  x n (x 0 + x 1 + x 2 ) n  =  x n   2n ∑   j  = 0    C3(n,   j ) x  j.

The [univariate] trinomial coefficients are obtained by the recurrence relation

C3(0, 0)  :=  1;

C3(n ,   j )  :=    j ∑   i  = j − 2 n    C3(n − 1, i ), n ≥ 1, 0 ≤   j ≤ 2 n,

where

C3(n,   j )   :=   0

for

j < 0

or

j > 2 n

.
For [univariate] trinomial coefficient array, row

n   ≥   0

is the sequence of coefficients of

x   j, 0   ≤    j   ≤   2 n ,

in

(  ∑ 2 i  = 0 x i  )  n

.

Row

n, n   ≥   0,

is the sequence of [univariate] trinomial coefficients of

x  j, 0   ≤   j   ≤   2 n ,

in

(x 0 + x 1 + x 2 ) n

n		A-number
0	1	A??????
1	1, 1, 1	A??????
2	1, 2, 3, 2, 1	A??????
3	1, 3, 6, 7, 6, 3, 1	A??????
4	1, 4, 10, 16, 19, 16, 10, 4, 1	A??????
5	1, 5, 15, 30, 45, 51, 45, 30, 15, 5, 1	A??????
6	1, 6, 21, 50, 90, 126, 141, 126, 90, 50, 21, 6, 1	A??????
7	1, 7, 28, 77, 161, 266, 357, 393, 357, 266, 161, 77, 28, 7, 1	A??????

A027907 Triangle of [univariate] trinomial coefficients. Row

n, n   ≥   0,

is the sequence of coefficients of

(1 + x + x 2 ) n

.

{1, 1, 1, 1, 1, 2, 3, 2, 1, 1, 3, 6, 7, 6, 3, 1, 1, 4, 10, 16, 19, 16, 10, 4, 1, 1, 5, 15, 30, 45, 51, 45, 30, 15, 5, 1, 1, 6, 21, 50, 90, 126, 141, 126, 90, 50, 21, 6, 1, 1, 7, 28, 77, 161, 266, 357, 393, 357, 266, 161, 77, 28, 7, 1, 1, 8, 36, 112, 266, ...}

Quadrinomial coefficients

Quadrivariate quadrinomial coefficients

A189225 Entries in a 4-dimensional version [4-dimensional simplex: pentachoron] of Pascal’s triangle: [quadrivariate] quadrinomial coefficients of

(x1 + x2 + x3 + x4 ) n

.

{1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 2, 2, 1, 2, 1, 1, 3, 3, 3, 3, 6, 6, 3, 6, 3, 1, 3, 3, 3, 6, 3, 1, 3, 3, 1, 1, 4, 4, 4, 6, 12, 12, 6, 12, 6, 4, 12, 12, 12, 24, 12, 4, 12, 12, 4, 1, 4, 4, 6, 12, 6, 4, 12, 12, 4, 1, ...}

Univariate quadrinomial coefficients

See: Tetrahedral dice.

A008287 Triangle of [univariate] quadrinomial (also called tetranomial) coefficients. Row

n, n   ≥   0,

is the sequence of coefficients of

(1 + x + x 2 + x 3 ) n

.

{1, 1, 1, 1, 1, 1, 2, 3, 4, 3, 2, 1, 1, 3, 6, 10, 12, 12, 10, 6, 3, 1, 1, 4, 10, 20, 31, 40, 44, 40, 31, 20, 10, 4, 1, 1, 5, 15, 35, 65, 101, 135, 155, 155, 135, 101, 65, 35, 15, 5, 1, 1, 6, 21, 56, 120, 216, 336, 456, 546, 580, 546, 456, 336, 216, 120, 56, 21, 6, 1, ...}

External links

• Weisstein, Eric W., Multinomial Coefficient, from MathWorld—A Wolfram Web Resource.
• Weisstein, Eric W., Multinomial Series, from MathWorld—A Wolfram Web Resource.