P1 §8.2 Factorial notation and combination (n choose r, nCr)

Pure mathematics Year 1

Table of contents

1. Introduction
2. Factorial $n!$ and arrangements
3. Permutations (${}_nP_r$)
4. Combination: n choose r
5. An alternative derivation of the formula for 'n choose r'
6. 0! = 1 revisited
7. Pascal's triangle using combinations
8. Examples
9. Edexcel P1 Ch8 Exercise 8B

1. Introduction

While Pascal's triangle is a convenient tool, for large values of the index, $n$, it takes a long time to construct it.

 

For example, for $(a+b)^{10}$, we need:

$$ \begin{array}{ccccccccccccccccccccc} &&&&&&&&&& 1 \\ &&&&&&&&& 1 && 1 \\ &&&&&&&& 1 && 2 && 1 \\ &&&&&&& 1 && 3 && 3 && 1 \\ &&&&&& 1 && 4 && 6 && 4 && 1 \\ &&&&& 1 && 5 && 10 && 10 && 5 && 1 \\ &&&& 1 && 6 && 15 && 20 && 15 && 6 && 1 \\ &&& 1 && 7 && 21 && 35 && 35 && 21 && 7 && 1 \\ && 1 && 8 && 28 && 56 && 70 && 56 && 28 && 8 && 1 \\ & 1 && 9 && 36 && 84 && 126 && 126 && 84 && 36 && 9 && 1 \\ 1 && 10 && 45 && 120 && 210 && 252 && 210 && 120 && 45 && 10 && 1 \end{array}$$ and we find $$ \begin{align} (a+b)^{10}&=a^{10}+10a^9b+45a^8b^2+120a^7b^3+210a^6b^4 \\ &\qquad +252a^5b^5+210a^4b^6+120a^3b^7+45a^2b^8+10ab^9+b^{10} \end{align} $$ One could anticipate how labourious the expressions might be with higher indices such as $(a+b)^{15}$ and $(a+b)^{20}$ and so forth.

 

In this section, we learn the factorial notation ($n!$) and combinations (${}^nC_r$) to reconstruct the binomial expansion. It turns out that this is much quicker, especially for larger values of $n$.

2. Factorial ($n!$) and arrangements

The factorial notation is defined by $$ \begin{align} \boxed{ n!=n\times(n-1)\times(n-2)\times\cdots\times3\times2\times1 } \end{align} $$ For example, we have $$ \begin{align} 1!&=1 \\ 2!&=2\times1=2 \\ 3!&=3\times2\times1=6 \\ 4!&=4\times3\times2\times1=24 \\ 5!&=5\times4\times3\times2\times1=120 \\ 6!&=6\times5\times4\times3\times2\times1=720 \\ 7!&=7\times6\times5\times4\times3\times2\times1=5040 \\ 8! &= 8\times7\times6\times5\times4\times3\times2\times1=40\,320 \\ 9! &= 9\times8\times7\times6\times5\times4\times3\times2\times1=362\,880 \\ 10! &= 10\times9\times8\times7\times6\times5\times4\times3\times2\times1=3\,628\,800 \\ 20! &= 2\,432\,902\,008\,176\,640\,000 \\ 30! &= 265\,252\,859\,812\,191\,058\,636\,308\,480\,000\,000 \\ 40! &= 815\,915\,283\,247\,897\,734\,345\,611\,269\,596\,115\,894\,272\,000\,000\,000 \\ 50! &= 30\,414\,093\,201\,713\,378\,043\,612\,608\,166\,064\,768\,844\,377\,641\,568\,960\,512\,000\,000\,000\,000 \\ &\;\;\vdots \end{align} $$

 

 

Also, by definition, $$ \begin{align} \boxed{ 0!=1 } \end{align} $$ We will look at two proofs for this later.

 

 

The factorial appears frequently when we count the number of possible arrangements.

 

1) Case 1: Consider the number of ways to put 2 balls (numbered $1,2$) into 2 boxes. $$ \begin{array}{|c|c|} \hline & \\ \hline \end{array} $$ Clearly, there are 2 ways: $$ \begin{array}{|c|c|} \hline 1 & 2 \\ \hline \end{array} \qquad{\rm and}\qquad \begin{array}{|c|c|} \hline 2 & 1 \\ \hline \end{array} $$

 

2) Case 2: Consider the number of ways to put 3 balls (numbered $1,2,3$) into 3 boxes.

$$ \begin{array}{|c|c|c|} \hline & & \\ \hline \end{array} $$ We find 6 ways as follows: $$ \begin{array}{|c|c|c|} \hline 1& 2& 3\\ \hline \end{array} \\ \begin{array}{|c|c|c|} \hline 2& 3& 1\\ \hline \end{array} \\ \begin{array}{|c|c|c|} \hline 3& 1& 2\\ \hline \end{array} \\ \begin{array}{|c|c|c|} \hline 2& 1& 3\\ \hline \end{array} \\ \begin{array}{|c|c|c|} \hline 1& 3& 2\\ \hline \end{array} \\ \begin{array}{|c|c|c|} \hline 3& 2& 1\\ \hline \end{array} $$

 

We can understand the 6 ways as follows.

• There are 3 possibilities for the first box.
• Once the first box is decided, there are 2 possibilities left for the second box.
• Once the first and second boxes are decided, there is only 1 possibility left for the third box.
• Hence $$ \begin{align} 3\times 2\times 1 = 3! \end{align} $$

 

3) Case 3: Consider the number of ways to put 4 balls (numbered $1,2,3,4$) into 4 boxes.

• There are 4 possibilities for the first box.
• Once the first box is decided, there are 3 possibilities left for the second box.
• Once the first and second boxes are decided, there are 2 possibilities left for the third box.
• Once the first, second and third boxes are decided, there is only 1 possibility left for the fourth box.
• Hence $$ \begin{align} 4\times 3\times 2\times 1 = 4! \end{align} $$

 

4) Case 4: Similarly, for $n$ balls into $n$ boxes, there are $n!$ ways.

3. Permutations (${}_nP_r$)

The permutations, ${}_nP_r$, count the number of ways to choose an ordered set of $r$ objects out of $n$. (Yes, here the order matters.) It is given by:

$$ \begin{align} \boxed{ {}^nP_r={}_nP_r=\frac{n!}{(n-r)!} } \end{align} $$ We'll look at some simple examples and then derive this general result.

 

1) ${}_4P_2$ counts the number of ways to choose an ordered set of 2 objects out of 4. Suppose that there are 4 balls numbered 1, 2, 3 and 4. Then, it is simple enough to arrange 2 balls where the order matters: $$ \begin{align} 12,\quad 13,\quad 14, \quad 23, \quad 24, \quad 34 \\ 21,\quad 31, \quad 41,\quad 32, \quad 42, \quad 43 \end{align} $$ Hence, there are 12 ways, which agrees with ${}_4P_2=\frac{4!}{(4-2)!}=\frac{24}{2}=12$.

 

2) For ${}_4P_3$, we find: (Once the first row is found, the next five rows are found by cyclic and anti-cyclic permutations.) $$ \begin{align} 123, \quad 124, \quad 134, \quad 234 \\ 231, \quad 241, \quad 341, \quad 342 \\ 312, \quad 412, \quad 413, \quad 423 \\ 213, \quad 214, \quad 314, \quad 324 \\ 132, \quad 142, \quad 143, \quad 243 \\ 321, \quad 421, \quad 431, \quad 432 \end{align} $$ and there are 24 ways, which agrees with ${}_4P_3=\frac{4!}{(4-3)!}=24$.

 

3) For ${}_5P_2$, we find: $$ \begin{align} 12,\quad 13,\quad 14, \quad 15, \quad 23, \quad 24, \quad 25, \quad 34, \quad 35, \quad 45 \\ 21,\quad 31,\quad 41, \quad 51, \quad 32, \quad 42, \quad 52, \quad 43, \quad 53, \quad 54 \end{align} $$ and there are 20 ways, which agrees with ${}_5P_2=\frac{5!}{(5-2)!}=\frac{120}{6}=20$.

 

4) For ${}_5P_3$, we find: $$ \begin{align} 123, \quad 124, \quad 125, \quad 134, \quad 135, \quad 145, \quad 234, \quad 235, \quad 245, \quad 345 \\ 231, \quad 241, \quad 251, \quad 341, \quad 351, \quad 451, \quad 342, \quad 352, \quad 452, \quad 453 \\ 312, \quad 412, \quad 512, \quad 413, \quad 513, \quad 514, \quad 423, \quad 523, \quad 524, \quad 534 \\ 213, \quad 214, \quad 215, \quad 314, \quad 315, \quad 415, \quad 324, \quad 325, \quad 425, \quad 435 \\ 132, \quad 142, \quad 152, \quad 143, \quad 153, \quad 154, \quad 243, \quad 253, \quad 254, \quad 354 \\ 321, \quad 421, \quad 521, \quad 431, \quad 531, \quad 541, \quad 432, \quad 532, \quad 542, \quad 543 \end{align} $$ and there are 60 ways, which agrees with ${}_5P_3=\frac{5!}{(5-3)!}=\frac{120}{2}=60$.

 

5) For ${}_nP_r$, we may count the number of ways to select $r$ balls out of $n$ and place them into $r$ boxes where the order matters.

• There are $n$ possibilities for the first box.
• Once the first box is decided, there are $n-1$ possibilities left for the second box.
• Once the first and second boxes are decided, there are $n-2$ possibilities left for the third box, and so on.
• Once the previous boxes are decided, there are $n-r+1$ possibilities left for the $r$-th box.
• Hence $$ \begin{align} {}_nP_r&=n(n-1)(n-2)\cdots(n-r+1) \\ &=\frac{n(n-1)(n-2)\cdots(n-r+1){\color{blue}{(n-r)(n-r-1)\cdots1}}}{{\color{blue}{(n-r)(n-r-1)\cdots1}}} \\ &=\frac{n!}{(n-r)!} \qquad\square \end{align} $$

4. Combination, n choose r (${}^nC_r$)

The combination, also known as 'n choose r', counts the number of ways to choose $r$ items from a collection of $n$ objects where the order does not matter, i.e. it counts the number of ways to choose an un-ordered set of $r$ objects out of $n$. (The permutations above were for the ordered set.)

 

For a given permutation ${}_nP_r$, we may remove the ordered-ness by dividing it by $r!$ as there are $r!$ possible arrangements among them. For example, for a set of $\{1,2,3\}$, there are $3!=6$ possible arrangements as follows: $$ \begin{align} 123,&\quad 213 \\ 231,&\quad 132 \\ 312,&\quad 321 \end{align} $$ For a set of $\{1,2,3,4\}$, there are $4!=24$ possible arrangements as follows: $$ \begin{align} 1234, \quad 2341, \quad 3412, \quad 4123 \\ 1342, \quad 2413, \quad 3124, \quad 4231 \\ 1423, \quad 2134, \quad 3241, \quad 4312 \\ 1324, \quad 2431, \quad 3142, \quad 4213 \\ 1243, \quad 2314, \quad 3421, \quad 4132 \\ 1432, \quad 2143, \quad 3214, \quad 4321 \end{align} $$

Therefore, we derive the combination, written as ${}^nC_r$ or ${}_nC_r$ or $\binom{n}{r}$ and given by $$ \begin{align} \boxed{ {}^nC_r \equiv {}_nC_r \equiv \binom{n}{r} = \frac{{}_nP_r}{r!} = \frac{n!}{r!(n-r)!} } \end{align} $$

5. An alternative derivation of the formula for 'n choose r'

Without referring to ${}_nP_r$, we derive the formula for ${}^nC_r$ in the following 4 steps.

 

5.1 Simple examples first

 

Example 1. Suppose we have 4 balls numbered $1,2,3,4$ in a bag. If we consider the number of ways to choose 2 balls, it corresponds to ${}^4C_2$, i.e. the number of ways to choose 2 balls from a collection of 4 where the order does not matter. For this case, we can actually count them by hand and there are 6 ways: $$ \begin{align} (1,2) \\ (1,3) \\ (1,4) \\ (2,3) \\ (2,4) \\ (3,4) \end{align} $$ which gives $$ \begin{align} {}^4C_2=6 \end{align} $$

Similarly, we can also find the number of ways to choose 1 ball: $$ \begin{align} (1) \\ (2) \\ (3) \\ (4) \end{align} $$ which gives $$ \begin{align} {}^4C_1=4 \end{align} $$ For the number of ways to choose 3 balls, we find: $$ \begin{align} (1,2,3) \\ (1,2,4) \\ (1,3,4) \\ (2,3,4) \end{align} $$ which gives $$ \begin{align} {}^4C_3=4 \end{align} $$

 

Example 2. Suppose that there are 5 balls numbered $1,2,3,4,5$ in a bag. For the number of ways to choose 2 balls, we find: $$ \begin{align} &(1,2),&& (2,3),&& (3,4),&& (4,5) \\ &(1,3),&& (2,4),&& (3,5) \\ &(1,4),&& (2,5),&& \\ &(1,5) \end{align} $$

 

We can imagine that the number goes up as we have a larger number of objects and let's approach this more systematically.

 

5.2 ${}^4C_2$ revisited

 

For ${}^4C_2$, i.e. the number of ways to choose 2 balls from a collection of 4, we can think of it as choosing the first two boxes after 4 balls have been put into 4 boxes. $$ \begin{array}{|c|c||c|c|} \hline &&& \\ \hline \end{array}$$ There are $4!$ ways but, as far as the first two boxes are concerned, there are redundancies (i.e. over-counting). $$ \begin{array}{|c|c||c|c|} \hline {\bf 1}&{\bf 2}&3&4 \\ \hline \end{array} \qquad \begin{array}{|c|c||c|c|} \hline {\bf 1}&{\bf 3}&2&4 \\ \hline \end{array} \qquad \begin{array}{|c|c||c|c|} \hline {\bf 1}&{\bf 4}&2&3 \\ \hline \end{array} \qquad \begin{array}{|c|c||c|c|} \hline {\bf 2}&{\bf 3}&1&4 \\ \hline \end{array} \qquad \begin{array}{|c|c||c|c|} \hline {\bf 2}&{\bf 4}&1&3 \\ \hline \end{array} \qquad \begin{array}{|c|c||c|c|} \hline {\bf 3}&{\bf 4}&1&2 \\ \hline \end{array} \\ \begin{array}{|c|c||c|c|} \hline {\bf 1}&{\bf 2}&4&3 \\ \hline \end{array} \qquad \begin{array}{|c|c||c|c|} \hline {\bf 1}&{\bf 3}&4&2 \\ \hline \end{array} \qquad \begin{array}{|c|c||c|c|} \hline {\bf 1}&{\bf 4}&3&2 \\ \hline \end{array} \qquad \begin{array}{|c|c||c|c|} \hline {\bf 2}&{\bf 3}&4&1 \\ \hline \end{array} \qquad \begin{array}{|c|c||c|c|} \hline {\bf 2}&{\bf 4}&3&1 \\ \hline \end{array} \qquad \begin{array}{|c|c||c|c|} \hline {\bf 3}&{\bf 4}&2&1 \\ \hline \end{array} \\ \begin{array}{|c|c||c|c|} \hline {\bf 2}&{\bf 1}&3&4 \\ \hline \end{array} \qquad \begin{array}{|c|c||c|c|} \hline {\bf 3}&{\bf 1}&2&4 \\ \hline \end{array} \qquad \begin{array}{|c|c||c|c|} \hline {\bf 4}&{\bf 1}&2&3 \\ \hline \end{array} \qquad \begin{array}{|c|c||c|c|} \hline {\bf 3}&{\bf 2}&1&4 \\ \hline \end{array} \qquad \begin{array}{|c|c||c|c|} \hline {\bf 4}&{\bf 2}&1&3 \\ \hline \end{array} \qquad \begin{array}{|c|c||c|c|} \hline {\bf 4}&{\bf 3}&1&2 \\ \hline \end{array} \\ \begin{array}{|c|c||c|c|} \hline {\bf 2}&{\bf 1}&4&3 \\ \hline \end{array} \qquad \begin{array}{|c|c||c|c|} \hline {\bf 3}&{\bf 1}&4&2 \\ \hline \end{array} \qquad \begin{array}{|c|c||c|c|} \hline {\bf 4}&{\bf 1}&3&2 \\ \hline \end{array} \qquad \begin{array}{|c|c||c|c|} \hline {\bf 3}&{\bf 2}&4&1 \\ \hline \end{array} \qquad \begin{array}{|c|c||c|c|} \hline {\bf 4}&{\bf 2}&3&1 \\ \hline \end{array} \qquad \begin{array}{|c|c||c|c|} \hline {\bf 4}&{\bf 3}&2&1 \\ \hline \end{array} $$ The 4 arrangements within the same column give rise to the same result for the first two boxes. For each selection of 2 balls, there are 4 redundancies which come from permutations of the first two boxes and the last two boxes, i.e. $$ \begin{align} \underbrace{1\quad 2}_{2!}\;|\; \underbrace{3\quad 4}_{2!} \end{align} $$ Thus, we arrive at $$ \begin{align} {}^4C_2=\frac{4!}{2!2!}=6 \end{align} $$

 

5.3 ${}^5C_2$ revisited

 

Similarly, for ${}^4C_2$, we can think of it as choosing the first two boxes after 5 balls have been put into 5 boxes. $$ \begin{array}{|c|c|c|c|c|} \hline &&&& \\ \hline \end{array} $$ As far as the first two boxes are concerned, there are redundancies (i.e. over-counting) $$ \begin{align} \underbrace{1\quad 2}_{2!}\;|\;\underbrace{3 \quad 4 \quad 5}_{3!} \end{align} $$ Indeed, for choosing $(1,2)$, we see the following $2!\times3!=12$ equivalent arrangements. $$ \begin{array}{|c|c|c|c|c|} \hline {\bf 1}&{\bf 2}&3&4&5 \\ \hline \end{array} \\ \begin{array}{|c|c|c|c|c|} \hline {\bf 1}&{\bf 2}&4&5&3 \\ \hline \end{array} \\ \begin{array}{|c|c|c|c|c|} \hline {\bf 1}&{\bf 2}&5&3&4 \\ \hline \end{array} \\ \begin{array}{|c|c|c|c|c|} \hline {\bf 1}&{\bf 2}&4&3&5 \\ \hline \end{array} \\ \begin{array}{|c|c|c|c|c|} \hline {\bf 1}&{\bf 2}&3&5&4 \\ \hline \end{array} \\ \begin{array}{|c|c|c|c|c|} \hline {\bf 1}&{\bf 2}&5&4&3 \\ \hline \end{array} \\ \begin{array}{|c|c|c|c|c|} \hline {\bf 2}&{\bf 1}&3&4&5 \\ \hline \end{array} \\ \begin{array}{|c|c|c|c|c|} \hline {\bf 2}&{\bf 1}&4&5&3 \\ \hline \end{array} \\ \begin{array}{|c|c|c|c|c|} \hline {\bf 2}&{\bf 1}&5&3&4 \\ \hline \end{array} \\ \begin{array}{|c|c|c|c|c|} \hline {\bf 2}&{\bf 1}&4&3&5 \\ \hline \end{array} \\ \begin{array}{|c|c|c|c|c|} \hline {\bf 2}&{\bf 1}&3&5&4 \\ \hline \end{array} \\ \begin{array}{|c|c|c|c|c|} \hline {\bf 2}&{\bf 1}&5&4&3 \\ \hline \end{array} $$ For each choice of 2 numbers, we would have $2!\times3!=12$ equivalent arrangements and thus we find $$ \begin{align} {}^5C_2=\frac{5!}{2!3!}=\frac{120}{12}=10 \end{align} $$

 

5.4 Finally ${}^nC_r$

 

Based on the logic established above, for ${}^nC_r$: We have $n!$ arrangements; For each selection of $r$ items, there are $r!(n-r)!$ redundancies: $$ \begin{align} \underbrace{1\quad \cdots\quad r}_{r!}\;|\;\underbrace{r+1 \quad\cdots \quad n}_{(n-r)!} \end{align} $$ Thus, we find $$ \begin{align} {}^nC_r=\frac{n!}{r!(n-r)!} \end{align} $$ i.e. this gives the number of inequivalent selections of the first $r$ boxes.

6. 0! = 1 revisited

 

We prove this result in two different ways.

 

1) Method 1: Consider ${}^nC_0$. On the one hand, we know that the answer has to be 1 as there is only one way to choose no objects among $n$. On the other hand, the formula reads $$ \begin{align} {}^nC_0 = \frac{n!}{0!n!} = \frac1{0!} = 1 \qquad \Rightarrow \qquad 0! = 1 \qquad \square \end{align} $$

 

2) Method 2: Alternatively, we may introduce the Euler gamma function, which is a generalised factorial function.

$$ \begin{align} \Gamma(n)=\int_0^\infty t^{n-1}\,{\textrm e}^{-t}\,{\textrm d}t \end{align} $$

By integration by parts, $$ \begin{align} u&=t^{n-1},& v'&={\textrm e}^{-t} \\ u'&=(n-1)t^{n-2},& v&=-{\textrm e}^{-t} \end{align} $$ $$ \begin{align} \Gamma(n)&= \underbrace{ \Big[ -(n-1)t^{n-2} \, {\textrm e}^{-t} \Big]_0^\infty }_{=0} + (n-1) \underbrace{ \int_0^\infty t^{n-2}\,{\textrm e}^{-t}\,{\textrm d}t }_{=\Gamma(n-1)} \\ &=(n-1)\Gamma(n-1) \end{align} $$ This reduction formula gives: $$ \begin{align} \Gamma(n) &=(n-1)\Gamma(n-1) \\ &=(n-1)(n-2)\Gamma(n-2) \\ &=\cdots \\ &=\underbrace{(n-1)(n-2)\cdots 1}_{=(n-1)!} \underbrace{\Gamma(1)}_{=1} \\ &=(n-1)! \end{align} $$ since $$ \begin{align} \Gamma(1)=\int_0^\infty {\textrm e}^{-t}\,{\textrm d}t = \Big[ -{\textrm e}^{-t} \Big]_0^\infty = 1 \end{align} $$ We have established $\Gamma(n+1)=n!$ and thus $$ \Gamma(1)=0!=1.\qquad\square $$

7. Pascal's triangle re-written using combinations

Pascal's triangle may be written using combinations.

 

$$ \begin{array}{ccccccccccccccccccccc} &&&&&&&&&& {}^0C_0 \\ &&&&&&&&& {}^1C_0 && {}^1C_1 \\ &&&&&&&& {}^2C_0 && {}^2C_1 && {}^2C_2 \\ &&&&&&& {}^3C_0 && {}^3C_1 && {}^3C_2 && {}^3C_3 \\ &&&&&& {}^4C_0 && {}^4C_1 && {}^4C_2 && {}^4C_3 && {}^4C_4 \\ &&&&& {}^5C_0 && {}^5C_1 && {}^5C_2 && {}^5C_3 && {}^5C_4 && {}^5C_5 \\ &&&& {}^6C_0 && {}^6C_1 && {}^6C_2 && {}^6C_3 && {}^6C_4 && {}^6C_5 && {}^6C_0 \\ &&&& && && && \vdots \end{array}$$

 

Now, for a large index, we can write down the binomial expansion straightforwardly without having to construct Pascal's triangle. For example, $$ \begin{align} (a+b)^{10} &= {}^{10}C_0a^{10}+ {}^{10}C_1a^9b+ {}^{10}C_2a^8b^2+ {}^{10}C_3a^7b^3+ {}^{10}C_4a^6b^4 \\ &\qquad+ {}^{10}C_5a^5b^5+ {}^{10}C_6a^4b^6+ {}^{10}C_7a^3b^7+ {}^{10}C_8a^2b^8+ {}^{10}C_9ab^9+ {}^{10}C_{10}b^{10} \\ \\ (a+b)^{15} &= {}^{15}C_0a^{15}+ {}^{15}C_1a^{14}b+ {}^{15}C_2a^{13}b^2+ {}^{15}C_3a^{12}b^3+ {}^{15}C_4a^{11}b^4 \\ &\qquad+ {}^{15}C_5a^{10}b^5+ {}^{15}C_6a^9b^6+ {}^{15}C_7a^8b^7+ {}^{15}C_8a^7b^8+ {}^{15}C_9a^6b^9 \\ &\qquad+ {}^{15}C_{10}a^5b^{10}+ {}^{15}C_{11}a^4b^{11}+ {}^{15}C_{12}a^3b^{12}+ {}^{15}C_{13}a^2b^{13}+ {}^{15}C_{14}ab^{14}+ {}^{15}C_{15}b^{15} \\ \\ (a+b)^{20} &= {}^{20}C_0a^{20}+ {}^{20}C_1a^{19}b+ {}^{20}C_2a^{18}b^2+ {}^{20}C_3a^{17}b^3+ {}^{20}C_4a^{16}b^4 \\ &\qquad+ {}^{20}C_5a^{15}b^5+ {}^{20}C_6a^{14}b^6+ {}^{20}C_7a^{13}b^7+ {}^{20}C_8a^{12}b^8+ {}^{20}C_9a^{11}b^9 \\ &\qquad+ {}^{20}C_{10}a^{10}b^{10}+ {}^{20}C_{11}a^9b^{11}+ {}^{20}C_{12}a^8b^{12}+ {}^{20}C_{13}a^7b^{13}+ {}^{20}C_{14}a^6b{14} \\ &\qquad+ {}^{20}C_{15}a^5b^{15}+ {}^{20}C_{16}a^4b^{16}+ {}^{20}C_{17}a^3b^{17}+ {}^{20}C_{18}a^2b^{18}+ {}^{20}C_{19}ab^{19}+ {}^{20}C_{20}b^{20} \end{align} $$

 

Using sigma notation (P2 §3), a general binomial expansion is written as $$ \begin{align} (a+b)^{n}= {}^{n}C_0a^{n}+ {}^{n}C_1a^{n-1}b+ {}^{n}C_2a^{n-2}b^2+ \cdots+ {}^{n}C_{n-1}ab^{n-1}+ {}^{n}C_{n}b^{n} =\sum_{r=0}^n{}^nC_r a^{n-r}b^r \end{align} $$

 

The relation between Pascal's triangle (binomial coefficients) and combinations will be understood in more details in the next section, P2 §8.3 The binomial expansion.

 

Summary:

 

• We can use factorial notation and a calculator to find entries in Pascal's triangle quickly.
• The number of ways of choosing $r$ itmes from a group of $n$ items is written as ${}^nC_r$ or ${}_nC_r$ or $\binom{n}{r}$: $$ \begin{align} {}^nC_r={}_nC_r=\binom{n}{r}=\frac{n!}{r!(n-r)!} \end{align} $$
• The $r$th entry in the $n$th row of Pascal's triangle is given by $$ \begin{align} {}^{n-1}C_{r-1}={}_{n-1}C_{r-1}=\binom{n-1}{r-1}=\frac{(n-1)!}{(r-1)!(n-r)!} \end{align} $$

8. Examples

Example. Calculate:

(a) $5!$

(b) ${}^5C_2$

(c) the 6th entry in the 10th row of Pascal's triangle

 

(Edexcel 2017 Specification, P1 Ch8 Example 3.)

 

Solution.

$$ \begin{align} {\rm (a)}&&& 5!=5\times4\times3\times2\times1=120 \\ {\rm (b)}&&& {}^5C_2=\frac{5!}{2!3!}=\frac{120}{2\times6}=10 \\ {\rm (c)}&&& {}^9C_5 \end{align} $$

9. Edexcel P1 Ch8 Exercise 8B

Question 1. Work out:

(a) $4!$

(b) $9!$

(c) $\frac{10!}{7!}$

(d) $\frac{15!}{13!}$

 

(Edexcel 2017 Specification, P1 Ch8 Exercise 8B Q1.)

 

Solution.

$$ \begin{align} \textbf{(a)}&&& 4!=4 \times 3 \times 2 \times 1 = 24 \\ \\ \textbf{(b)}&&& 9!=9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 362\,880 \\ \\ \textbf{(c)}&&& \frac{ 10! }{ 7! } = \frac{ 10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 }{ 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 } = 10 \times 9 \times 8 = 720 \\ \\ \textbf{(d)}&&& \frac{ 15! }{ 13! } = \frac{ 15 \times 14 \times 13 \times 12 \times 11 \times 10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 }{ 13 \times 12 \times 11 \times 10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 } = 15 \times 14 = 210 \end{align} $$

 

Question 2. Without using a calculator, work out:

(a) $\binom{4}{2}$

(b) $\binom{6}{4}$

(c) ${}^6C_3$

(d) $\binom{5}{4}$

(e) ${}^{10}C_8$

(f) $\binom{9}{5}$

 

(Edexcel 2017 Specification, P1 Ch8 Exercise 8B Q2.)

 

Solution.

$$ \begin{align} \textbf{(a)}&&& \binom{4}{2}=\frac{4!}{2!2!}=6 \\ \\ \textbf{(b)}&&& \binom{6}{4}=\frac{6!}{4!2!}=15 \\ \\ \textbf{(c)}&&& {}^6C_3=\frac{6!}{3!3!}=20 \\ \\ \textbf{(d)}&&& \binom{5}{4}=\frac{5!}{4!1!}=5 \\ \\ \textbf{(e)}&&& {}^{10}C_8=\frac{10!}{8!2!}=45 \\ \\ \textbf{(f)}&&& \binom{9}{5}=\frac{9!}{5!4!}=\frac{9 \times 8 \times 7 \times 6}{4 \times 3 \times 2 \times 1}=126 \end{align} $$

 

Question 3. Use a calculator to work out:

(a) $\binom{15}{6}$

(b) ${}^{10}C_7$

(c) $\binom{20}{10}$

(d) $\binom{20}{17}$

(e) ${}^{14}C_9$

(f) ${}^{18}C_5$

 

(Edexcel 2017 Specification, P1 Ch8 Exercise 8B Q3.)

 

Solution.

$$ \begin{align} \textbf{(a)}&&& \binom{15}{6} = \frac{15!}{6!9!} = 5005 \\ \\ \textbf{(b)}&&& {}^{10}C_7 = \frac{10!}{7!3!} = 120 \\ \\ \textbf{(c)}&&& \binom{20}{10} = \frac{20!}{10!10!} = 184\,756 \\ \\ \textbf{(d)}&&& \binom{20}{17} = \frac{20!}{17!3!} = 1140 \\ \\ \textbf{(e)}&&& {}^{14}C_9 = \frac{14!}{9!5!} = 2002 \\ \\ \textbf{(f)}&&& {}^{18}C_5 = \frac{18!}{5!13!} = 8568 \end{align} $$

 

Question 4. Write each value $a$ to $d$ from Pascal's triangle using ${}^nC_r$ notation:

$$ \begin{array}{ccccccccccccccccccccc} &&&&&&&&&& 1 \\ &&&&&&&&& 1 && 1 \\ &&&&&&&& 1 && 2 && 1 \\ &&&&&&& 1 && 3 && 3 && 1 \\ &&&&&& 1 && \underline{\mathbf{a}} && 6 && 4 && 1 \\ &&&&& 1 && 5 && \underline{\mathbf{b}} && 10 && 5 && 1 \\ &&&& 1 && 6 && \underline{\mathbf{c}} && \underline{\mathbf{d}} && 15 && 6 && 1 \\ &&&& && && && \vdots \end{array}$$

 

(Edexcel 2017 Specification, P1 Ch8 Exercise 8B Q4.)

 

Solution.

$$ \begin{align} a &= {}^4C_2 = \frac{4!}{2!2!} = 4 \\ \\ b &= {}^5C_2 = \frac{5!}{2!3!} = 10 \\ \\ c &= {}^6C_2 = \frac{6!}{2!4!} = 15 \\ \\ d &= {}^6C_3 = \frac{6!}{3!3!} = 20 \end{align} $$

 

Question 5. Work out the 5th number on the 12th row from Pascal's triangle.

 

(Edexcel 2017 Specification, P1 Ch8 Exercise 8B Q5.)

 

Solution.

The 12th row is for $n=11$. A row starts with $r=0$, so the 5th number is ${}^{11}C_4$, i.e. $$ \begin{align} {}^{11}C_4 = \frac{11!}{4!7!} = 330 \end{align} $$

 

Question 6. The 11th row of Pascal's triangle is shown below:. $$ \begin{align} 1\qquad 10\qquad 45\qquad \cdots \qquad \cdots \end{align} $$

(a) Find the next two values in the row.

(b) Hence find the coefficient of $x^3$ in the expansion of $(1+2x)^{10}$.

 

(Edexcel 2017 Specification, P1 Ch8 Exercise 8B Q6.)

 

Solution.

(a) The next two values are: $$ \begin{align} {}^{10}C_3 &= \frac{10!}{3!7!} = 120 \\ {}^{10}C_4 &= \frac{10!}{4!6!} = 210 \end{align} $$

 

(b) We find: $$ \begin{align} ( 1 + 2x )^{10} &= {}^{10}C_0 + {}^{10}C_1 (2x) + {}^{10}C_2 (2x)^2 + {}^{10}C_3 (2x)^3 + {}^{10}C_4 (2x)^4 + \cdots + {}^{10}C_9 (2x)^9 + {}^{10}C_{10} (2x)^{10} \\ &= \cdots + \left( 120 \times 2^3 \right) x^3 + \cdots \\ &= \cdots + 960 x^3 + \cdots \end{align} $$

 

Question 7. The 14th row of Pascal's triangle is shown below. $$ \begin{align} 1\qquad 13\qquad 78\qquad \cdots \qquad \cdots \end{align} $$

(a) Find the next two values in the row.

(b) Hence find the coefficient of $x^4$ in the expansion of $(1+3x)^{13}$.

 

(Edexcel 2017 Specification, P1 Ch8 Exercise 8B Q7.)

 

Solution.

(a) The next two values are: $$ \begin{align} {}^{13}C_3 &= \frac{13!}{3!10!} = 286 \\ {}^{13}C_4 &= \frac{13!}{4!9!} = 715 \end{align} $$

 

(b) We find: $$ \begin{align} ( 1 + 3x )^{13} &= {}^{13}C_0 + {}^{13}C_1 (3x) + {}^{13}C_2 (3x)^2 + {}^{13}C_3 (3x)^3 + {}^{13}C_4 (3x)^4 + \cdots + {}^{13}C_{12} (3x)^{12} + {}^{13}C_{13} (3x)^{13} \\ &= \cdots + \left( 715 \times 3^4 \right) x^4 + \cdots \\ &= \cdots + 57915 x^4 + \cdots \end{align} $$

 

Question 8. The probability of throwing exactly 10 heads when a fair coin is tossed 20 times is given by $$ \begin{align} \binom{20}{10}0.5^{20}. \end{align} $$ Calculate the probability and describe the likelihood of this occurring.

 

(Edexcel 2017 Specification, P1 Ch8 Exercise 8B Q8.)

 

Solution.

$$ \begin{align} \binom{20}{10}0.5^{20} &= \frac{20!}{10!10!}\times\frac{1}{ 2^{20} } \\ &= 184\,756 \times \frac1{1 \, 048 \, 576} \\ &= \frac{46189}{262144} \\ &= 0.176197\cdots \end{align} $$ Although it seems to be a low probability, this is more likely than any other number of heads - c.f. S1 §6.2 Binomial distribution, $X \sim B(20,0.5)$.

 

Question 9. (P) Show that $$ \begin{align} {\rm (a)}&& {}^nC_1&=n \\ {\rm (b)}&& {}^nC_2&=\frac{n(n-1)}{2} \end{align} $$

 

(Edexcel 2017 Specification, P1 Ch8 Exercise 8B Q9.)

 

Solution.

(a) $$ \begin{align} {}^nC_1 = \frac{n!}{1!(n-1)!} = \frac{n\times(n-1)!}{(n-1)!} = n \end{align} $$

 

(b) $$ \begin{align} {}^nC_2 = \frac{n!}{2!(n-2)!} = \frac{n(n-1)\times(n-2)!}{2!(n-2)!} = \frac{n(n-1)}{2} \end{align} $$

 

Question 10. (E) (1 mark) Given that $$ \begin{align} \binom{50}{13}=\frac{50!}{13!a!}, \end{align} $$ write down the value of $a$.

 

(Edexcel 2017 Specification, P1 Ch8 Exercise 8B Q10.)

 

Solution.

$$ \begin{align} \binom{50}{13}=\frac{50!}{13!37!} \qquad \Rightarrow \qquad a = 37 \end{align} $$

 

Question 11. (E) (1 mark) Given that $$ \begin{align} \binom{35}{p}=\frac{35!}{p!18!}, \end{align} $$ write down the value of $p$.

 

(Edexcel 2017 Specification, P1 Ch8 Exercise 8B Q11.)

 

Solution.

$$ \begin{align} \binom{35}{p}=\frac{35!}{p!(35-p)!}=\frac{35!}{p!18!} \qquad \Rightarrow \qquad p = 17 \end{align} $$

 

Challenge.

(a) Work out ${}^{10}C_3$ and ${}^{10}C_7$.

(b) Work out ${}^{14}C_5$ and ${}^{14}C_9$.

(c) What do you notice about your answers to parts (a) and (b)?

(d) Prove that ${}^nC_r={}^nC_{n-r}$. (This explains why Pascal's triangle is symmetric about the mid-value.)

 

(Edexcel 2017 Specification, P1 Ch8 Exercise 8B Challenge.)

 

Solution.

(a) $$ \begin{align} {}^{10}C_3 &= \frac{10!}{3!7!} = 120 \\ {}^{10}C_7 &= \frac{10!}{7!3!} = 120 \end{align} $$

 

(b) $$ \begin{align} {}^{14}C_5 &= \frac{14!}{5!9!} = 2002 \\ {}^{14}C_9 &= \frac{14!}{9!5!} = 2002 \end{align} $$

 

(c) The answers are the same.

 

(d) Method 1. Using the formula: $$ \begin{align} {}^nC_r = \frac{n!}{r!(n-r)!} = \frac{n!}{(n-r)![n-(n-r)]!} = {}^nC_{n-r} \qquad \square \end{align} $$

 

Method 2. Combinatorics:

• '$n$ choose $r$' is equivalent to '$n$ not choose $n-r$'.
• Then, '$n$ not choose $n-r$' is equivalent to '$n$ choose $n-r$'.
• Thus, '$n$ choose $r$' is equivalent to '$n$ choose $n-r$'.