How to choose r objects from n objects

 

Let’s say that we have 6 objects ({\{a,b,c,d,e,f\}}) and we want to know the number of ways of picking 4 of them (where the order doesn’t matter, so {\{a,b,c,d\}} is no different from {\{a,b,d,c\}}). We can imagine writing down all of the possible permutations of the 6 objects (of which there are {6!} as we know) and then just taking the first four items. For instance, these are the first few permutations and the items in brackets are the ones that we pick as our 4:

\begin{array}{c} \text{(abcd)ef} \\ \text{(abcd)fe} \\ \text{(abce)df} \\ \text{(abce)fd} \\ \text{(abcf)de} \\ \text{(abcf)ed} \\ \text{(abdc)ef} \\ \text{(abdc)fe} \\ \text{(abde)cf} \\ \text{(abde)fc} \\ ... \\ \end{array}

If we pick the items in the brackets then clearly we are going to get many repetitions of the same thing. For instance, the first two items are the same (both (abcd)). Also many of the items in the brackets are the same, up to a reordering, and we said that we didn’t care about the order, so (abcd) is the same as (abdc). We know that in total there are {6!} items in the long list of permutations, but we have over-counted if we want to know how many ways there are of choosing 4 objects from 6. We’ve double counted because we have got multiple permutations of the last two objects (i.e.. (abcd)ef and (abcd)fe are the same) and we have multiply counted because we have many ways of writing the same items in the brackets. In fact we have over counted by {2!} due to the last items and overcounted by {4!} because of the permutations of the first items. Thus the total number of unique ways of picking 4 items from 6 is not {6!} but {\frac{6!}{2!4!}=15}.

In fact this generalises completely. If we have {n} items and we want to choose {r} from them then we have:

 

 

\displaystyle _nC_r=\left( \begin{array}{c} n \\ r \\ \end{array} \right)=\frac{n!}{r!(n-r)!} \ \ \ \ \

 

 

where we read “n choose r” and both {_nC_r} and {\left( \begin{array}{c} n \\ r \\ \end{array} \right)} are just two different ways of writing this.

 

How many different possible lottery tickets are there?

Clearly the order of the numbers doesn’t matter, and we can choose 6 numbers from 49. This is {_{49}C_6} which is:

 

 

\displaystyle \frac{49!}{6!(49-6)!}=\frac{49\times 48 \times 47 \times 46 \times 45 \times 44}{6!}=13983816 \ \ \ \ \

 

 

If you buy one lottery ticket, then the chances of you winning are 1 in 13983816, which is pretty terrible!

 

How about if you toss a coin 6 times, how many ways are there of getting 2 heads? We can start to enumerate them:

\begin{array}{c} \text{HHTTTT} \\ \text{HTHTTT} \\ \text{HTTHTT} \\ \text{HTTTHT} \\ \text{HTTTTH} \\ \text{THHTTT} \\ ...\\ \end{array}

 

We can think of labeling the positions of the heads. The first in the list above will be (1,2), the second will be (1,3), etc. We can see that what we are doing is choosing 2 numbers from 6, but we know that this is just {_6C_2=\frac{6!}{4!2!}=15} Note that choosing {r} from {n} gives the same number as choosing {n-r} from {n}. There is a nice symmetry because of the denominator in {_nC_r}.

There are some more important properties of {_nC_r}. How many ways are there of choosing {n} objects from {n}: The answer is always 1, whatever the value of {n}. How about how to choose {0} objects from {n}. Again, the answer is {1}. There is also a nice symmetry of this. How many ways are there of choosing 4 objects from 6 is the same as choosing 2 objects from 6 (it’s like choosing not to choose the 4 objects!). In general: {_nC_r=_nC_{n-r}}.

Pascal’s identity

There is a very nice identity, which at first site might not seem very useful, but in fact it will help a lot with working out expressions of the form {_nC_r}. This is Pascal’s identity:

 

 

\displaystyle \left( \begin{array}{c} n \\ r \\ \end{array} \right)+\left( \begin{array}{c} n \\ r+1 \\ \end{array} \right)=\left( \begin{array}{c} n+1 \\ r+1 \\ \end{array} \right) \ \ \ \ \

 

 

We can prove this by starting with the left hand side:

 

 

\left( \begin{array}{c} n \\ r \\ \end{array} \right)+\left( \begin{array}{c} n \\ r+1 \\ \end{array} \right)=\frac{n!}{r!(n-r)!}+\frac{n!} {(r+1)!(n-(r+1))!}
=\frac{n!}{r!(n-r)(n-(r+1))!}+\frac{n!}{(r+1)r!(n-(r+1))!}
=\frac{n!}{r!(n-(r+1))!}\left[\frac{1}{n-r}+\frac{1}{r+1}\right]
=\frac{n!}{r!(n-(r+1))!}\left[\frac{r+1+n-r}{(n-r)(r+1)}\right]
=\frac{n!}{r!(n-(r+1))!}\left[\frac{n+1}{(n-r)(r+1)}\right]
=\frac{(n+1)n!}{(r+1)r!(n-r)(n-(r+1))!}
=\frac{(n+1)!}{(r+1)!(n-r)!}=_{n+1}C_{r+1}

 

 

Alternative derivation:

 

 

\left(\begin{array}{c} n \\ r \\ \end{array} \right)+\left( \begin{array}{c} n \\ r+1 \\ \end{array} \right)=\frac{n!}{r!(n-r)!}+\frac{n!} {(r+1)!(n-(r+1))!}
=\frac{n!(r+1)}{(r+1)r!(n-r)!}+\frac{(n-r)n!} {(n-r)(r+1)!(n-(r+1))!}
=\frac{n!(r+1)}{(r+1)!(n-r)!}+\frac{(n-r)n!} {(n-r)!(r+1)!}
=\left((r+1)+(n-r)\right)\frac{n!}{(n-r)!(r+1)!}
=\left(n+1\right)\frac{n!}{(n-r)!(r+1)!}
=\frac{(n+1)!}{(n-r)!(r+1)!}=\left( \begin{array}{c} n+1 \\ r+1 \\ \end{array} \right)

 

 

So we have an identity which tells us that to work out a term related to choosing from {n+1} objects, we have to add together two terms related to choosing from {n} objects. This is encoded entirely in Pascal’s triangle:

 

{n=0}: 1
{n=1}: 1 1
{n=2}: 1 2 1
{n=3}: 1 3 3 1
{n=4}: 1 4 6 4 1

 

Where each entry is equal to the value of the two numbers above it, and if there is only one number above, it is this number. Pascal’s triangle is the complete enumeration of all {_nC_r}. In fact, the above can be written as:

 

{n=0}: {_0C_0}
{n=1}: {_1C_0} {_1C_1}
{n=2}: {_2C_0} {_2C_1} {_2C_2}
{n=3}: {_3C_0} {_3C_1} {_3C_2} {_3C_3}
{n=4}: {_4C_0} {_4C_1} {_4C_2} {_4C_3} {_4C_4}

 

Check for yourself that the {_nC_r} expressions that you calculate match up exactly with the numbers in Pascal’s triangle. Now, the rather mysterious looking Pascal’s identity makes a lot more sense. It is precisely the algorithm that you use to construct Pascal’s triangle. For instance Pascal’s identity tells you that {_4C_3=_3C_2+_3C_3} which is the same as seeing that the number 4 is given by {3+1} in Pascal’s triangle. In order to work out {_nC_r} then we just need to write out Pascal’s triangle down to the {(n+1)^{th}} layer (the first layer is for {_0C_0}).

 

 

How clear is this post?