This site is supported by donations to The OEIS Foundation.

Multinomial coefficients

From OeisWiki
Jump to: navigation, search


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

     

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 ≤   jn, 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)[1]
Layer 0
(top layer[2])
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  =  xn (x 0 + x 1 + x 2 )n  =  xn
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
xi  )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, ...}

Notes

  1. Pascal's pyramidWikipedia.org.
  2. The [triangular] pyramid grows downwards from the top layer!

External links