18
$\begingroup$

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?

$\endgroup$
30
$\begingroup$

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.

$\endgroup$
1
$\begingroup$
  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.

$\endgroup$
1
$\begingroup$

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!$.

$\endgroup$
1
$\begingroup$

Here's a visualisation (following the reasoning which Brian outlined above) for those more visually inclined to see what's going on: https://charleslow.github.io/binomial_coefficient/

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.