Proof of Multinomial Coefficients: Binomial Products and Counting

Throughout, a multinomial coefficient is the unique $M\in\mathbb{N}_{0}$ satisfying its defining equation in The Multinomial Coefficient (i) (Existence and Uniqueness of the Multinomial Coefficients (i)), and the product of factorials there is written $a_{1}!\cdots a_{p}!=\prod_{i=1}^{p}a_{i}!$; sums and products in $\mathbb{N}_{0}$ are regrouped and reordered by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order (iii), Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order (iv), Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order (v) and Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order (vi). Write $N=k_{1}+\dots+k_{m}$.

Step 1 ((i)). Let $k_{m+1}\in\mathbb{N}_{0}$, and let $(k_{1},\dots,k_{m+1})$ be the tuple extending $(k_{1},\dots,k_{m})$ by $k_{m+1}$ (Finite Sets: Removing an Element, Injective Self-Maps, Infinite Sets, Sets of Permutations, Pairs and Extended Tuples (vi)). Splitting off the last term (Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (vii)),

$$k_{1}+\dots+k_{m+1}=N+k_{m+1},\qquad k_{1}!\cdots k_{m+1}!=(k_{1}!\cdots k_{m}!)\cdot k_{m+1}!.$$

Let $M=\binom{N}{k_{1},\dots,k_{m}}$ and $B=\binom{N+k_{m+1}}{k_{m+1}}$, so that $M\cdot k_{1}!\cdots k_{m}!=N!$. Since $k_{m+1}\le N+k_{m+1}$ and $(N+k_{m+1})-k_{m+1}=N$ (Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order (vii), The Difference of Two Natural Numbers with Zero (i)), Binomial Coefficients: Existence and Uniqueness by Pascal's Recursion, Vanishing above the Diagonal, Diagonal and First Values, the Factorial Formula and Symmetry (v) gives $k_{m+1}!\,N!\,B=(N+k_{m+1})!$. Hence

$$(MB)\cdot k_{1}!\cdots k_{m+1}!=(M\cdot k_{1}!\cdots k_{m}!)\cdot k_{m+1}!\,B=N!\,k_{m+1}!\,B=(N+k_{m+1})!,$$

and by uniqueness $MB$ is the multinomial coefficient of $(k_{1},\dots,k_{m+1})$, which is the claim.

Step 2 ((ii)). Let $a,b\in\mathbb{N}_{0}$. For the pair $(a,b)\in\mathbb{N}_{0}^{2}$ the entries add up to $a+b$ and the product of their factorials is $a!\,b!$ (Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (i), Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (vii)). Since $a\le a+b$ and $(a+b)-a=b$, Binomial Coefficients: Existence and Uniqueness by Pascal's Recursion, Vanishing above the Diagonal, Diagonal and First Values, the Factorial Formula and Symmetry (v) gives

$$\binom{a+b}{a}\cdot a!\,b!=(a+b)!,$$

so $\binom{a+b}{a}$ is the multinomial coefficient $\binom{a+b}{a,b}$ by uniqueness.

Step 3 (the claim for (iii)). For $p\in\mathbb{N}$, $a\in\mathbb{N}_{0}^{p}$ and a finite set $D$ let

$$\mathcal{A}_{p}(D;a)=\{\varphi\in[p]^{D}:\#\varphi^{-1}\{i\}=a_{i}\text{ for every }i\in[p]\},$$

the set of admissible maps; it is finite, as a subset of the finite set $[p]^{D}$, and the fibres are finite as subsets of $D$ (Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice (ix), Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice (iv)). We show by induction on $p$ (The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion (viii)) that for every $a\in\mathbb{N}_{0}^{p}$ and every finite set $D$ with $\#D=a_{1}+\dots+a_{p}$,

$$\#\mathcal{A}_{p}(D;a)=\binom{a_{1}+\dots+a_{p}}{a_{1},\dots,a_{p}}.$$

The case $p=m$, $a=(k_{1},\dots,k_{m})$, $D=[n]$ is (iii), since $\#[n]=n$ (Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (i)).

Step 4 (one value). Let $p=1$; then $[1]=\{1\}$, and the entries of $a$ add up to $a_{1}$ (Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (i)). There is exactly one map $D\to\{1\}$, the one with value $1$ everywhere (Maps Formed Pointwise: Constant Maps, Pairs of Values, Maps Applied to Values, and Families of Maps (i)); its fibre over $1$ is $D$, which has $a_{1}$ elements. So $\mathcal{A}_{1}(D;a)$ has exactly one element (Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (ii)). On the other side, $1\cdot a_{1}!=a_{1}!$ (Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order (iii)), so $\binom{a_{1}}{a_{1}}=1$ by uniqueness.

Step 5 (sorting by the fibre over the last value). Assume the claim for $p$. Let $a\in\mathbb{N}_{0}^{p+1}$, let $(a_{1},\dots,a_{p})\in\mathbb{N}_{0}^{p}$ be the tuple of its first $p$ entries (Finite Sets: Removing an Element, Injective Self-Maps, Infinite Sets, Sets of Permutations, Pairs and Extended Tuples (vi)), and put $N'=a_{1}+\dots+a_{p}$, so that $a_{1}+\dots+a_{p+1}=N'+a_{p+1}$ (Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (vii)). Let $D$ be a finite set with $\#D=N'+a_{p+1}$. Recall that $[p+1]=[p]\cup\{p+1\}$ with $p+1\notin[p]$. Each $\varphi\in\mathcal{A}_{p+1}(D;a)$ has a fibre $\varphi^{-1}\{p+1\}$ with $a_{p+1}$ elements, so

$$F:\mathcal{A}_{p+1}(D;a)\to\mathcal{P}_{a_{p+1}}(D),\qquad\varphi\mapsto\varphi^{-1}\{p+1\}$$

is a map (The k-Element Subsets of a Set (ii)), into a finite set with $\binom{N'+a_{p+1}}{a_{p+1}}$ elements (Counting Subsets (i)).

Step 6 (each fibre of $F$). Let $E\in\mathcal{P}_{a_{p+1}}(D)$ and $C=D\setminus E$. Then $a_{p+1}+\#C=\#D=N'+a_{p+1}$ by Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (v), so $\#C=N'$ by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order (v). Let $\varphi\in F^{-1}\{E\}$. A point $c\in C$ is not in $E$, so $\varphi(c)\neq p+1$ and $\varphi(c)\in[p]$; hence the restriction $\varphi|_{C}$ (Domains and Restrictions of Maps (ii)), read as a map $C\to[p]$ (Gluing Maps on Disjoint Domains, and Shrinking the Codomain (iii)), is defined. For $i\in[p]$, no point of $E$ is mapped to $i$, so the fibre of $\varphi|_{C}$ over $i$ is $\varphi^{-1}\{i\}$, with $a_{i}$ elements. Thus restriction is a map

$$R_{E}:F^{-1}\{E\}\to\mathcal{A}_{p}(C;(a_{1},\dots,a_{p})),\qquad\varphi\mapsto\varphi|_{C}.$$

It is injective: two elements of $F^{-1}\{E\}$ with the same restriction agree on $C$ and take the value $p+1$ everywhere on $E$. It is surjective: given $\chi\in\mathcal{A}_{p}(C;(a_{1},\dots,a_{p}))$, take $\chi$ with codomain $[p+1]$ (Gluing Maps on Disjoint Domains, and Shrinking the Codomain (iii)) and glue it with the map $E\to[p+1]$ of constant value $p+1$ with value $p+1$ (Maps Formed Pointwise: Constant Maps, Pairs of Values, Maps Applied to Values, and Families of Maps (i), Gluing Maps on Disjoint Domains, and Shrinking the Codomain (i)); this gives a map $\varphi:C\cup E=D\to[p+1]$ whose fibre over $p+1$ is $E$, because $\chi$ takes its values in $[p]$, and whose fibre over $i\in[p]$ is $\chi^{-1}\{i\}$, with $a_{i}$ elements. So $\varphi\in F^{-1}\{E\}$ and $R_{E}(\varphi)=\chi$. Since $\#C=N'$, Counting through Bijections, Injections and Surjections (i) and the induction hypothesis give

$$\#F^{-1}\{E\}=\#\mathcal{A}_{p}(C;(a_{1},\dots,a_{p}))=\binom{N'}{a_{1},\dots,a_{p}}.$$

Step 7 (counting). All fibres of $F$ have the same number of elements, so by Counting by Fibres, Double Counting and the Pigeonhole Principle (iv), Step 5 and (i), applied to $a_{1},\dots,a_{p+1}$ in place of $k_{1},\dots,k_{m+1}$,

$$\#\mathcal{A}_{p+1}(D;a)=\binom{N'}{a_{1},\dots,a_{p}}\binom{N'+a_{p+1}}{a_{p+1}}=\binom{N'+a_{p+1}}{a_{1},\dots,a_{p+1}}.$$

This is the claim for $p+1$, which completes the induction and proves (iii).