Proof of Existence and Uniqueness of the Multinomial Coefficients

Throughout, sums and products are formed in $\mathbb{N}_{0}$, whose addition and multiplication are associative and commutative with neutral elements $0$ and $1$ (The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion (vi)), and induction on $j$ is that of The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion (viii). For $j\in\{0,\dots,m\}$ let

$$s_{j}=\sum_{i=1}^{j}k_{i}\qquad\text{and}\qquad p_{j}=\prod_{i=1}^{j}k_{i}!,$$

the sum and the product over the interval $\{1,\dots,j\}\subseteq[m]$; for $j=0$ the interval is empty, so $s_{0}=0$ and $p_{0}=1$ by Sums and Products over a Finite Set and over an Interval (ii). For $j<m$, Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (vii) gives

$$s_{j+1}=s_{j}+k_{j+1}\qquad\text{and}\qquad p_{j+1}=p_{j}\,k_{j+1}!.$$

Let $C$ be the map of Binomial Coefficients: Existence and Uniqueness by Pascal's Recursion, Vanishing above the Diagonal, Diagonal and First Values, the Factorial Formula and Symmetry (i).

Claim. For every $j\in\{0,\dots,m\}$, $p_{j}\neq0$ and there is $M_{j}\in\mathbb{N}_{0}$ with $M_{j}\,p_{j}=s_{j}!$.

We argue by induction on $j$. For $j=0$, $p_{0}=1\neq0$ (The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion (ii)), and $M_{0}=1$ works, since $1\cdot1=1=0!$.

Let $j<m$ and assume the claim for $j$. By The Factorial: Recursion, Positivity and Bounds by Powers (ii), $k_{j+1}!\ge1$, so $k_{j+1}!\neq0$ as $0<1$ (The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion (ii), The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion (v)), and $p_{j+1}=p_{j}\,k_{j+1}!\neq0$ by Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order (vii). Since $s_{j}+k_{j+1}=s_{j+1}$, we have $s_{j}\le s_{j+1}$ by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order (vii), and the difference $s_{j+1}-s_{j}$ is $k_{j+1}$. The factorial formula Binomial Coefficients: Existence and Uniqueness by Pascal's Recursion, Vanishing above the Diagonal, Diagonal and First Values, the Factorial Formula and Symmetry (v), applied to $s_{j}\le s_{j+1}$, therefore reads

$$s_{j}!\,k_{j+1}!\,C(s_{j+1},s_{j})=s_{j+1}!.$$

Let $M_{j+1}=M_{j}\,C(s_{j+1},s_{j})$. Then

$$M_{j+1}\,p_{j+1}=C(s_{j+1},s_{j})\,\bigl(M_{j}\,p_{j}\bigr)\,k_{j+1}!=C(s_{j+1},s_{j})\,s_{j}!\,k_{j+1}!=s_{j+1}!,$$

which proves the claim for $j+1$.

Existence. The claim for $j=m$ gives $M=M_{m}$ with $M\prod_{i=1}^{m}k_{i}!=\bigl(\sum_{i=1}^{m}k_{i}\bigr)!$.

Uniqueness. If also $M'\prod_{i=1}^{m}k_{i}!=\bigl(\sum_{i=1}^{m}k_{i}\bigr)!$, then $p_{m}\,M=p_{m}\,M'$ with $p_{m}\neq0$ by the claim, so $M=M'$ by Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order (ix).