Multinomial coefficient

The multinomial coefficient or polynomial coefficient is an extension of the binomial coefficient . For nonnegative integers and it is defined as ${\displaystyle k_{1},\dotsc ,k_{r}}$ ${\displaystyle n:=k_{1}+\dotsb +k_{r}}$

${\displaystyle {n \choose k_{1},\dotsc ,k_{r}}:={\frac {n!}{k_{1}!\dotsm k_{r}!}}}$

Where is the faculty of . ${\displaystyle x!}$ ${\displaystyle x}$

properties

The multinomial coefficients are always whole numbers.

The multinomial coefficients can also be expressed with the binomial coefficients as

${\displaystyle {k_{1}+\cdots +k_{r} \choose k_{1},\ldots ,k_{r}}={k_{1} \choose k_{1}}{k_{1}+k_{2} \choose k_{2}}\cdots {k_{1}+k_{2}+\cdots +k_{r} \choose k_{r}}=\prod _{i=1}^{r}{\sum _{s=1}^{i}k_{s} \choose k_{i}}}$.

Applications and interpretations

Multinomial theorem

In generalizing the binomial theorem , the so-called multinomial theorem (also polynomial theorem ) applies

${\displaystyle (x_{1}+\dotsb +x_{r})^{n}=\sum _{k_{1}+\dotsb +k_{r}=n}{n \choose k_{1},\dotsc ,k_{r}}\cdot x_{1}^{k_{1}}\dotsm x_{r}^{k_{r}}}$.

From the multinomial theorem it follows immediately:

${\displaystyle \forall r\in \mathbb {N} :r^{n}=\sum _{k_{1}+\dotsb +k_{r}=n}{n \choose k_{1},\dotsc ,k_{r}}\cdot 1^{k_{1}}\dotsm 1^{k_{r}}=\sum _{k_{1}+\dotsb +k_{r}=n}{n \choose k_{1},\dotsc ,k_{r}}.}$

Multinomial distribution

Those coefficients are also used in the multinomial distribution

${\displaystyle P(X_{1}=k_{1},X_{2}=k_{2},\dotsc ,X_{r}=k_{r})\;=\;{n \choose k_{1},\dotsc ,k_{r}}\cdot p_{1}^{k_{1}}\cdot p_{2}^{k_{2}}\dotsm p_{r}^{k_{r}}}$,

a probability distribution of discrete random variables.

Combinatorial Interpretations

Objects in boxes

The multinomial coefficient indicates the number of possibilities for placing objects in boxes, with objects in the first box, objects in the second box , and so on. ${\displaystyle {\tbinom {n}{k_{1},\dotsc ,k_{r}}}}$ ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle k_{1}}$ ${\displaystyle k_{2}}$

example

How many different ways there are of the 32 cards of Skat to give each 10 cards to three players and two cards in the "Skat" when the order of the cards is not respected?

Since these are objects that are to be divided into boxes, with objects in the first three boxes and objects in the fourth box , the number of possibilities is given by the following multinomial coefficients: ${\displaystyle n=32}$ ${\displaystyle r=4}$ ${\displaystyle k_{1}=k_{2}=k_{3}=10}$ ${\displaystyle k_{4}=2}$

${\displaystyle {32 \choose 10,\,10,\,10,\,2}={\frac {32!}{10!\cdot 10!\cdot 10!\cdot 2!}}=2.753.294.408.504.640}$

Arrangement of things

The multinomial coefficient also indicates the number of different arrangements of things, where the first occurs (indistinguishable), the second occurs, etc. ${\displaystyle {\tbinom {n}{k_{1},\dotsc ,k_{r}}}}$ ${\displaystyle n}$ ${\displaystyle k_{1}}$ ${\displaystyle k_{2}}$

example

How many different "words" can be formed from the letters MISSISSIPPI?

We are looking for the number of possibilities to arrange 11 things, whereby the first ("M") -time, the second ("I") -time (indistinguishable) occurs, the third ("S") also and the fourth (" P ") times. So this is the multinomial coefficient ${\displaystyle k_{1}=1}$ ${\displaystyle k_{2}=4}$ ${\displaystyle k_{4}=2}$

${\displaystyle {\binom {11}{1,4,4,2}}={\frac {11!}{1!\cdot 4!\cdot 4!\cdot 2!}}=34.650}$

For comparison: the number of possibilities to arrange eleven completely different things in rows is 11! = 39,916,800 much higher.

Pascal's Simplizes

Analogous to the Pascal triangle of the binomial coefficients, the -th multinomial coefficients can also be arranged as geometric figures ( simplices ): The trinomial coefficients lead to the Pascal pyramid , the other to -dimensional Pascal simplices . ${\displaystyle r}$ ${\displaystyle r}$

Web links

• Eric W. Weisstein : Multinominal Coefficient . In: MathWorld (English).