The multinomial coefficient $\binom{n}{k_0,\dots,k_{m-1}}$ as the number of ordered partitions of an $n$-set into blocks of prescribed sizes

Let $m, n \in \mathbb{N}$. Write

$\mathcal{W}(n,m) := \Big\{\, k : m \to \mathbb{N} \ \Big|\ \sum_{i<m} k_i = n \,\Big\},$

the set of $m$-tuples of naturals summing to $n$, the sum being the $\mathbb{N}$-valued one of Finite sums and finite products of natural numbers, $\sum_{k<n} a_k$ and $\prod_{k<n} a_k$ in $\mathbb{N}$.

$\mathcal{W}(n,m)$ is finite. If $\sum_{i<m}k_i = n$ then each $k_i \le n$ by the monotonicity clause of Laws of finite sums and products in $\mathbb{N}$, and $\iota\big(\sum_{k<n} a_k\big) = \sum_{k<n} \iota(a_k)$ (a term of a sum of naturals is at most the sum), so $\mathcal{W}(n,m)$ is a subset of the set of functions $m \to \sigma(n)$, which is finite by The set $A^{B}$ of functions $B \to A$ between finite sets is finite, with $\lvert A^{B}\rvert = \lvert A\rvert^{\lvert B\rvert}$; now apply A subset of a finite set is finite, with $\lvert B\rvert \le \lvert A\rvert$, and equality holds if and only if $B = A$.

Block decompositions as colourings. For a finite set $A$ and $k : m \to \mathbb{N}$ put

$\mathcal{B}(A,k) := \big\{\, c : A \to m \ \big|\ \lvert c^{-1}[\{i\}]\rvert = k_i \text{ for every } i < m \,\big\}.$

A colouring $c$ is the same thing as an ordered decomposition of $A$ into the $m$ blocks $c^{-1}[\{0\}], \dots, c^{-1}[\{m-1\}]$; presenting it as a function makes the blocks a partition of $A$ automatically, so that The sum rule: a finite disjoint union is finite with $\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert$ and $\lvert\bigcup_{i \in I} A_i\rvert = \sum_{i \in I}\lvert A_i\rvert$, and a sum over a finite index set splits along a partition and The set $A^{B}$ of functions $B \to A$ between finite sets is finite, with $\lvert A^{B}\rvert = \lvert A\rvert^{\lvert B\rvert}$ apply verbatim. $\mathcal{B}(A,k)$ is a subset of the finite set $m^{A}$, hence finite.

The hypothesis is part of the definition, and it is forced. The fibres $c^{-1}[\{i\}]$, $i < m$, are pairwise disjoint with union $A$, so The sum rule: a finite disjoint union is finite with $\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert$ and $\lvert\bigcup_{i \in I} A_i\rvert = \sum_{i \in I}\lvert A_i\rvert$, and a sum over a finite index set splits along a partition gives $\lvert A\rvert = \sum_{i<m}\lvert c^{-1}[\{i\}]\rvert = \sum_{i<m}k_i$ for any $c \in \mathcal{B}(A,k)$. Hence $\mathcal{B}(A,k) = \varnothing$ unless $k \in \mathcal{W}(\lvert A\rvert, m)$, and the coefficient is defined only under that hypothesis.

$\lvert\mathcal{B}(A,k)\rvert$ depends only on $\lvert A\rvert$. If $h : A \to A'$ is a bijection then $c \mapsto c \circ h^{-1}$ maps $\mathcal{B}(A,k)$ to $\mathcal{B}(A',k)$, because $(c\circ h^{-1})^{-1}[\{i\}] = h\big[c^{-1}[\{i\}]\big]$ has the same cardinality as $c^{-1}[\{i\}]$ (The cardinality $\lvert A\rvert$ of a finite set); and $c' \mapsto c' \circ h$ is its two-sided inverse.

Definition. For $k \in \mathcal{W}(n,m)$ set

$\binom{n}{k_0,\dots,k_{m-1}} := \big\lvert\mathcal{B}(n,k)\big\rvert \in \mathbb{N},$

abbreviated $\binom{n}{k}$ when the tuple is named. By the previous paragraph, $\lvert\mathcal{B}(A,k)\rvert = \binom{\lvert A\rvert}{k}$ for every finite $A$ with $\lvert A\rvert = n$. Like the binomial coefficient, it is defined as a count, so it is a natural number by construction.

Boundary cases.

• $m = 0$. The empty sum is $0$, so $\mathcal{W}(n,0)$ is nonempty only for $n = 0$, where its single element is the empty tuple. And $\mathcal{B}(\varnothing, ())$ contains exactly the empty function, so $\binom{0}{\ } = 1$.
• A block of size $0$ is allowed: $k_i = 0$ simply means $c^{-1}[\{i\}] = \varnothing$.
• $m = 2$ recovers the binomial coefficient: for $k \le n$, $\binom{n}{k,\,n-k} = \binom{n}{k}$. The map $c \mapsto c^{-1}[\{0\}]$ sends $\mathcal{B}(A,(k,n-k))$ into $[A]^{k}$, and $S \mapsto$ the colouring taking the value $0$ on $S$ and $1$ off it is its two-sided inverse, the second fibre having cardinality $n - k$ by The sum rule: a finite disjoint union is finite with $\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert$ and $\lvert\bigcup_{i \in I} A_i\rvert = \sum_{i \in I}\lvert A_i\rvert$, and a sum over a finite index set splits along a partition. So the two notations do not collide.

• Nonemptiness in the other direction. Conversely, if $k \in \mathcal{W}(n,m)$ then $\mathcal{B}(A,k) \ne \varnothing$. This is not proved here and is not needed for the definition: it follows from The multinomial coefficient equals $n!/\prod_{i<m} k_i!$, and $(x_0+\dots+x_{m-1})^{n} = \sum \iota\!\binom{n}{k}\prod_{i<m} x_i^{k_i}$ in $\mathbb{R}$, whose clause 1 gives $\binom{n}{k}\prod_{i<m}k_i! = n! \ne 0$, so the count $\binom{n}{k}$ is nonzero and the set it counts is nonempty.

• Why a colouring and not a tuple of sets. An $m$-tuple $(S_0,\dots,S_{m-1})$ of pairwise disjoint sets with union $A$ carries exactly the same information, but the disjointness and the covering would then be side conditions to be checked at every use. As fibres of a function they hold by construction.

• $\mathcal{W}(n,m)$ will get a name. Its elements are the weak compositions of $n$ into $m$ parts, and they are counted in For $m \ge 1$ the number of weak compositions of $n$ into $m$ parts is $\binom{n+m-1}{m-1}$, and the number of compositions is $\binom{n-1}{m-1}$ for $n \ge 1$; Compositions and weak compositions of a natural number into a fixed number of parts fixes the terminology. The set is introduced here because the multinomial coefficient cannot be stated without it.