= Allocation to labelled bins
{title2=$N(n_1,\ldots,n_k)=n!/(n_1!\cdots n_k!)$}
Allocate $n$ distinct objects to $k$ labelled bins of specified nonnegative sizes $n_1,\ldots,n_k$, with $\sum_i n_i=n$. Order within a bin is ignored. The number of allocations is the <multinomial coefficient>
$$
N(n_1,\ldots,n_k)=\frac{n!}{n_1!\cdots n_k!}.
$$
To prove this, order all the objects in a <permutation> and assign the first $n_1$ to the first bin, the next $n_2$ to the second, and so on. Every allocation comes from exactly $n_1!\cdots n_k!$ internal orderings. These disjoint classes exhaust the $n!$ <permutations>, proving the formula by the <multiplication principle>. Empty bins are allowed because $0!=1$.
For two bins of sizes $m$ and $n-m$, the count is $\binom nm$ and every allocation has multiplicity $m!(n-m)!$ in the <permutation> sample space. Exchanging two equal-sized labelled bins generally gives a different allocation. In contrast, a <set partition> uses unlabelled nonempty blocks; forgetting bin labels changes the counting problem and must not be done silently.
Back to article page
