Lagmental Vicfred

The Multinomial Coefficient Counts Ordered Blocks by Vicfred

tags: mathematics, enumeration, binomial identities, inclusion-exclusion

Splitting n labeled objects into ordered blocks of prescribed sizes produces the multinomial coefficient. A small computation will anchor the general statement before the abstraction takes over.

The data

Enumerative combinatorics turns a finite set \(\Omega\) into several reversible descriptions. Binomial coefficients \(\binom nk\) appear whenever a choice forgets order but remembers size.

$$ n_1+\cdots+n_r=n $$

The first display fixes the mathematical data. I label it \(\mathsf{data}\) mentally, while the next is the \(\mathsf{claim}\); the bridge between them is the displayed \(\Longrightarrow\), not an automatic implication.

$$ \binom{n}{n_1,\ldots,n_r}=\frac{n!}{n_1!\cdots n_r!} $$

Derivation

The middle display is intentionally dense: it is where signs, bounds, multiplicities, or normalising factors are most likely to be lost.

$$ (x_1+\cdots+x_r)^n=\sum_{\substack{n_1+\cdots+n_r=n\\n_i\ge0}}\binom{n}{n_1,\ldots,n_r}\prod_{i=1}^{r}x_i^{n_i} $$

Invariant content

The compact alignment is a local map of the argument: assumptions on the first row, consequence on the second. Any generalisation must preserve that dependency.

$$ \begin{aligned} \mathsf{D}\;&:\quad n_1+\cdots+n_r=n,\\[5pt] \mathsf{C}\;&:\quad \binom{n}{n_1,\ldots,n_r}=\frac{n!}{n_1!\cdots n_r!}. \end{aligned} $$

Scope

A formula with the correct magnitude can still count the wrong objects. The proof must explain whether order, repetition, labels, and empty parts are allowed.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] \binom{n}{n_1,\ldots,n_r}=\frac{n!}{n_1!\cdots n_r!} \end{gathered}} $$

The final box is a summary, not a new assumption; the proof still lives in the definitions and the intervening calculation. The source keeps each scope delimiter visible for later inspection.

This article was posted on Tue 14 October 2014. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.