Intuitive explanation of binomial coefficient

Question

We know that

$$\dbinom{n}r = \dfrac{n!}{(n-r)!r!}$$

An intuitive explanation of the formula is that, if I partition the total number of permutations of objects by $r!$, and choose one member of each partition, then no similarly ordered pattern will be registered more than once.

Is there a more intuitive explanation than this?

Answer 1

1. Intuitive Explanation for a Combinatorial Identity

2. Proof of binomial coefficient formula.

3. https://www.khanacademy.org/math/algebra2/polynomial_and_rational/binomial_theorem/v/binomial-theorem-and-combinatorics-intuition

These will certainly suffice, and other Khan Academy videos (Link 3) will be of further help.

Answer 2

Let's say you have $n$ letters and you want the number of permutations of length $r$ from your alphabet. You have $n$ choices for the first letter, $n-1$ choices for the second letter, and so on for all $r$ of your letters. Thus the number of permutations is $\frac{n!}{(n-r)!}$.

Combinations are permutations where order doesn't matter. Instead of caring about which letter is first, which is second, etc., you only care about which letters you have. Your $r$ letters you've chosen can be ordered in $r!$ ways, so to get rid of the ordering, divide by $r!$.

Answer 3

Think of it this way. Suppose that I have balls numbered $1$ through $n$, I want to pick $r$ of them, and I do it one ball at a time. There are $n$ different ways in which I could choose the first ball. Once it’s been chosen, there are only $n-1$ balls left, so there are $n-1$ different ways in which I could pick the second ball. Thus, there are $n(n-1)$ different ways in which I could pick the first two balls. If I continue in this fashion, after I’ve picked $r-1$ balls, there will be $n-(r-1)=n-r+1$ balls left, so I’ll be able to pick the $r$-th ball in $n-r+1$ different ways. Thus, the sequence of $r$ balls can be chosen in

$$n(n-1)(n-2)\ldots(n-r+1)=\frac{n!}{(n-r)!}\tag{1}$$

different ways. The $(n-r)!$ in the denominator merely serves to cancel out the unwanted factors in $n!$.

However, $(1)$ is the number of different sequences of $r$ balls that we could choose: if $B$ is a set of $r$ balls, $(1)$ counts every possible permutation of the balls in $B$ separately. For example, if $B=\{b_1,b_2,b_3\}$, expression $(1)$ counts $B$ six times, once for each of the $3!=6$ possible sequences in which we could have chosen $B$: $\langle b_1,b_2,b_3\rangle,\langle b_1,b_3,b_2\rangle,\langle b_2,b_1,b_3\rangle,\langle b_2,b_3,b_1\rangle,\langle b_3,b_1,b_2\rangle$, and $\langle b_3,b_2,b_1\rangle$.

The same reasoning that I used to arrive at $(1)$ shows that there are $r!$ different ways to arrange a set of $r$ balls in order, so each $r$-element set of balls has been counted $r!$ times in $(1)$. Thus, to get the actual number of $r$-element subsets of our set of $n$ balls, we must divide $(1)$ by $r!$, getting

$$\binom{n}r=\frac{n!}{(n-r)!r!}\;$$

From the standpoint of seeing why this works, it’s better to think of it as

$$\frac{n(n-1)(n-2)\ldots(n-r+1)}{r!}=\frac{\prod_{i=0}^{r-1}(n-i)}{r!}\;;$$

that actually reflects the reasoning involved.

Answer 4

Imagine writing down a list of all the possible combinations where you select $r$ items out of $n$. For each combination, there are $r!$ ways of ordering it. Therefore, each combination corresponds to $r!$ permutations, giving us the formula $P(n,r)=r!\times C(n,r)$. Since $P(n,r)=n!/(n-r)!$, the desired result immediately follows.