Multinomial numbers

#matematik-discmath

Definition: Multinomial numbers

Let and . Also, let . Then the number of surjections such that where for every is denoted and is called a multinomial number.

In this way, multinomial numbers are generalizations of Binomial numbers. In possibly easier terms, it is the number of ways to choose a sequence of sets where such that is the disjoint union of all 's.

Theorem: Formula for multinomial numbers

Given and nonnegative integers such that , Proof:
Each possible sequence of sets can be done by choosing a permutation of all elements of and then letting contain the first elements, contain the following elements, and so on. There are ways of doing this, but each possible partition is then counted times since that's the number of ways to order the elements and still preserving the sets .

Theorem: Multinomial theorem

For any and , where the sum is over all possible such that .

Proof:
We consider a multiset of copies of , and we are thus interested in the product of these elements, and we see that every term in the result is of the form where , and that the coefficient for that term is the number of ways to choose exactly one term from from each factor such that in total, the number of chosen is precisely , which we see corresponds to the definition of the multinomial number.