Why does the multinomial coefficient count permutations but the binomial coefficient count combinations?

Question

The binomial coefficient $n \choose k$ counts the number of ways to choose $k$ objects from a set of $n$ objects (order does not matter).

The more general multinomial coefficient $n \choose {n_1,n_2,...,n_k}$ counts the number of permutations of $n$ elements of $k$ different types with there being $n_i$ of the $i$-th type for $1\le i \le k$. Here, the order is considered. A typical example of the use of the multinomial coefficient is in finding permutations of words with repeated letters.

Perhaps it's my unfamiliarity with the subject, but the fact that there's this "order does/does not matter" difference between the two coefficients seems a little counterintuitive to me. Is there an explanation as to why this is the case?

Answer 1

When we say "order matters", or not, we need to be clear on what is being counted.

The more general multinomial coefficient $n \choose {n_1,n_2,...,n_k}$ counts the number of permutations of $n$ elements of $k$ different types with there being $n_i$ of the $i$-th type for $1\le i \le k$. Here, the order is considered.

That multinomial coefficient counts the ways to partition a set of $n$ distinct elements into $k$ ordered subsets of the specified sizes.

Order matters for the subsets, not for the elements sorted into each.

A binomial coefficient is simply a special case where we partition $n$ elements into two subsets (typically called 'selected' and 'unselected') of specified sizes. It matters which subset is which, but not the order of what goes into each of them.

A typical example of the use of the multinomial coefficient is in finding permutations of words with repeated letters.

It is a possible example.

Think about what you are counting here. It is ways to assign distinct positions in the string to letters where each letter can be assigned has a specified amount of positions.

It is the same count as for the way to sort numbered balls into fixed-size boxes labelled by letters. The order of the balls placed into the boxes does not matter, but we can use the contents of the boxes as guides to place letters into a string in certain order.

Answer 2

The binomial coefficients also count words over an alphabet. The multinomial coefficient $$ \binom{n}{n_1,n_2,\dotsc,n_k} $$ counts the number of words of length $n$ over the alphabet $a_1^{n_1}a_2^{n_2}\dotsb a_k^{n_{k}}$ where the letter $a_i$ appears $n_i$ times and $\sum n_i =n$.

In the event that we have an alphabet with two letters then this formalism reduces to counting the number of words of length $n$ over the alphabet $\{a,b\}$ where $a$ appears $n_1$ times and $b$ appears $n_2$ times and $n_1 + n_2=n$. This number equals $$ \binom{n}{n_1}=\binom{n}{n_2}= \binom{n}{n_1,n_2} $$

Answer 3

The multinomial coefficient has three equivalent forms, eg with win, lose, draw, possible disjoint outcomes in $n$ matches,

$$\binom{n}{w,l,d} \equiv \binom{n}{w}\binom{n-w}{l}\binom{n-w-l}{d} \equiv \frac{n!}{w!l!d!}$$

Note that the last term in the combinatorial form, $$\binom{n-w-l}{d}\text{ can be more simply written as} \binom{d}{d}$$

The formula for the binomial win, lose, could also be written in three forms,

$$\binom{n}{w,l}\equiv \binom{n}{w}\binom{l}{l}\equiv \frac{n!}{w!l!}$$

Since the simplest form for the binomial coefficient is to write $\Large\binom{n}{w}$, we think that we are using combinations here and permutations for the multinomial whereas actually there is no difference whatsoever in reality.