The multinomial coefficient $\left(\genfrac{}{}{0px}{}{n}{k_0,\dots ,k_{m-1}}\right)$ 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):=\{k:m\to \mathbb{N}\mid {\sum }_{i<m}{k}_i=n\},$

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 \left({\sum }_{k<n}{a}_k\right)={\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 $\mid A^B\mid =\mid A{\mid }^{\mid B\mid }$; now apply A subset of a finite set is finite, with $\mid B\mid \le \mid A\mid$, 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):=\{c:A\to m\mid \mid c^{-1}[\{i\}]\mid =k_i\text{ for every }i<m\}\mathrm{.}$

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 $\mid A\cup B\mid =\mid A\mid +\mid B\mid$ and $\mid {\bigcup }_{i\in I}{A}_i\mid ={\sum }_{i\in I}\mid A_i\mid$, 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 $\mid A^B\mid =\mid A{\mid }^{\mid B\mid }$ 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 $\mid A\cup B\mid =\mid A\mid +\mid B\mid$ and $\mid {\bigcup }_{i\in I}{A}_i\mid ={\sum }_{i\in I}\mid A_i\mid$, and a sum over a finite index set splits along a partition gives $\mid A\mid ={\sum }_{i<m}\mid c^{-1}[\{i\}]\mid ={\sum }_{i<m}{k}_i$ for any $c\in \mathcal{B}(A,k)$. Hence $\mathcal{B}(A,k)=\mathrm{\varnothing }$ unless $k\in \mathcal{W}(\mid A\mid ,m)$, and the coefficient is defined only under that hypothesis.

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

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

$\left(\genfrac{}{}{0px}{}{n}{k_0,\dots ,k_{m-1}}\right):=\mid \mathcal{B}(n,k)\mid \in \mathbb{N},$

abbreviated $\left(\genfrac{}{}{0px}{}{n}{k}\right)$ when the tuple is named. By the previous paragraph, $\mid \mathcal{B}(A,k)\mid =\left(\genfrac{}{}{0px}{}{\mid A\mid }{k}\right)$ for every finite $A$ with $\mid A\mid =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}(\mathrm{\varnothing },())$ contains exactly the empty function, so $\left(\genfrac{}{}{0px}{}{0}{}\right)=1$.
• A block of size $0$ is allowed: $k_i=0$ simply means $c^{-1}[\{i\}]=\mathrm{\varnothing }$.
• $m=2$ recovers the binomial coefficient: for $k\le n$, $\left(\genfrac{}{}{0px}{}{n}{k,n-k}\right)=\left(\genfrac{}{}{0px}{}{n}{k}\right)$. 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 $\mid A\cup B\mid =\mid A\mid +\mid B\mid$ and $\mid {\bigcup }_{i\in I}{A}_i\mid ={\sum }_{i\in I}\mid A_i\mid$, 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)\mathrm{\ne }\mathrm{\varnothing }$. This is not proved here and is not needed for the definition: it follows from The multinomial coefficient equals $n!\mathrm{/}{\prod }_{i<m}{k}_i!$, and $(x_0+\cdots +x_{m-1}{)}^n=\sum \iota \text{\hspace{0.17em}⁣}\left(\genfrac{}{}{0px}{}{n}{k}\right){\prod }_{i<m}{x}_i^{k_i}$ in $\mathbb{R}$, whose clause 1 gives $\left(\genfrac{}{}{0px}{}{n}{k}\right){\prod }_{i<m}{k}_i!=n!\mathrm{\ne }0$, so the count $\left(\genfrac{}{}{0px}{}{n}{k}\right)$ 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 $\left(\genfrac{}{}{0px}{}{n+m-1}{m-1}\right)$, and the number of compositions is $\left(\genfrac{}{}{0px}{}{n-1}{m-1}\right)$ 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.