Let us begin with the following example.
Example. In how many ways can 8 horses finish in a race? Here, we assume that there are no ties.
Solution. $8\times 7\times 6\times 5\times 4\times 3\times 2\times 1=40,320$ ways.
The example above shows an ordered arrangement. Such an ordered arrangement is called a permutation.
Definition. $n$ factorial $n!$ is defined by
\begin{align*} n!&=n(n-1)(n-2)\cdots 3\cdot 2\cdot 1,\ n\geq 1\\ 0!&=1 \end{align*}
The number of permutation of $n$ objects is $n!$.
Example. There are $6!$ permutations of the six letters of the word “square”. In how may of them is $r$ the second letter?
Solution. $5\times 1\times 4!=5!=120$.
Example. Five different books are on a shelf. In how many different ways can you arrange them?
Solution. $5!=120$.
We now consider the permutation of a set of objects taken from a larger set. Suppose we have $n$ items. The number of ordered arrangements of $k$ items from the $n$ items can be then found by
$$n(n-1)(n-2)\cdots (n-k+1)=\frac{n!}{(n-k)!}$$
Denote this by ${}_nP_k$.
Example. How many license plates are there that starts with three letters followed by 4 digits (no repetitions)?
Solution. \begin{align*} {}_{26}P_3\times {}_{10}P_4&=\frac{26!}{23!}\times\frac{10!}{6!}\\
&=26\cdot 25\cdot 24\cdot 10\cdot 9\cdot 8\cdot 7\\
&=78,624,000
\end{align*}
Example. How many five-digit zip codes can be made where all digits are different? The possible digits are 0-9.
Solution. ${}_{10}P_5=\frac{10!}{5!}=30,240$.
Circular permutations are ordered arrangements of objects in a circle. Suppose that circular permutations such as
are considered as different. Under this assumption, let us consider seating $n$ different objects in a circle. There are $n!$ ways to arrange $n$ seats in a circle depending on where we start and there are $n$ different ways to start seating, so there are $\frac{n!}{n}=(n-1)!$ circular permutations. If the orientation does not matter, i.e. if we consider clockwise and counterclockwise directions are the same, there are $\frac{(n-1)!}{2}$ circular permutations.
Example. In how many ways can you seat 6 persons at a circular dinner table?
Solution. $(6-1)!=5!=120$.
Suppose that we are interested in counting the number of ways to choose $k$ objects from $n$ distinct objects without regard to order. It can be calculated as
$$\frac{{}_nP_k}{k!}=\frac{n!}{k!(n-k)!}$$
This is denoted by ${}_nC_k$ or $\begin{pmatrix}n\\k\end{pmatrix}$ and is read “$n$ choose $k$”.
Example. From a group of 5 women and 7 men, how many different committees consisting of 2 women and 3 men can be formed? What if two of the men are feuding and refuse to serve on the committee together?
Solution. For the first question, there are
\begin{align*} {}_5C_2\times {}_7C_3&=\frac{5!}{2!3!}\times\frac{7!}{3!4!}\\ &=350 \end{align*}
such committees. For the second question, the number of ways to two feuding men and another man is ${}_2C_2\times {}_5C_1=5$. So, the number of selecting male committee members that do not include the two feuding men together is ${}_7C_3-5=30$. Consequently, the number of possible committees in this case is ${}_5C_2\times 30=300$.
Theorem. Suppose that $n$ and $k$ are integers such that $0\leq k\leq n$. Then
- ${}_nC_0={}_nC_n=1$ and ${}_nC_1={}_nC_{n-1}=n$.
- ${}_nC_k={}_nC_{n-k}$.
- Pascal’s identity: ${}_{n+1}C_k={}_nC_{k-1}+{}_nC_k$.
Proof. 2. $${}_nC_{n-k}=\frac{n!}{(n-k)!(n-(n-k))!}=\frac{n!}{(n-k)!k!}={}_nC_k$$
- \begin{align*} {}_nC_{k-1}+{}_nC_k&=\frac{n!}{(k-1)!(n-k+1)!}+\frac{n!}{k!(n-k)!}\\ &=\frac{n!k}{k!(n+1-k)!}+\frac{n!(n+1-k)}{k!(n+1-k)!}\\ &=\frac{(n+1)!}{k!(n+1-k)!}\\ &={}_{n+1}C_k
\end{align*}
The Pascal’s identity allows us to construct the Pascal’s triangle.
$$\begin{array}{cccccccccc}
n & & & & & & & & &\\
0 & & & & & 1 & & & &\\
1 & & & & 1 & & 1 & & &\\
2 & & & 1 & & 2 & & 1 & &\\
3 & & 1 & & 3 & & 3 & & 1 &\\
4 & 1 & & 4 & & 6 & & 4 & & 1
\end{array}$$
Example. The chess club has six members. In how many ways
- can all six members line up for a picture?
- can they choose a president and a secretary?
- can they choose three members to attend a regional tournament with no regard to order?
Solution.
- ${}_6P_6=6!=720$.
- ${}_6P_2=\frac{6!}{4!}=30$.
- ${}_6C_3=\frac{6!}{3!3!}=20$.
Theorem. (Binomial Theorem) Let $n$ be a nonnegative integer. Then
$$(x+y)^n=\sum_{k=0}^n{}_nC_k x^{n-k}y^k$$
Proof. We prove it by induction on $n$. For $n=0$,
$$(x+y)^0=1=\sum_{k=0}^0 {}_0C_k x^{-k}y^k$$ For $n=1$, $$\sum_{k=0}^1 {}_1C_k x^{1-k}y^k=x+y$$ Suppose the statement is true up to $n$, i.e. $$(x+y)^n=\sum_{k=0}^n{}_nC_k x^{n-k}y^k$$ \begin{align*} (x+y)^{n+1}&=(x+y)^n(x+y)\\ &=\sum_{k=0}^n {}_nC_k x^{n-k}y^k\\ &=\sum_{k=0}^n {}_nC_kx^{n+1-k}y^k+\sum_{k=0}^n {}nC_k x^{n-k}y^{k+1}\\ &=\sum_{k=0}^n {}_nC_kx^{n+1-k}y^k+\sum_{k=1}^{n+1} {}_nC{k-1} x^{n+1-k}y^k\ (\mbox{replaing $k$ by $k-1$ in the second sum})\\ &={}_nC_0x^{n+1}+\sum_{k=1}^n[{}_nC_k+{}_nC{k-1}]x^{n+1-k}y^k+{}_nC_n y^{n+1}\\ &={}_{n+1}C_0 x^{n+1}+\sum_{k=1}^n {}_{n+1}C_k x^{n+1-k}y^k+{}_{n+1}C_{n+1} y^{n+1}\ (\mbox{Pascal’s identity})\\
&=\sum_{k=0}^{n+1}{}_{n+1}C_k x^{n+1-k}y^k
\end{align*}
This completes the proof.
Example. Expand $(x+y)^6$ using the Binomial Theorem.
Solution.
$$(x+y)^6=x^6+6x^5y+15x^4y^2+20x^3y^3+15x^2y^4+6xy^5+y^6$$
Example. How many subsets are there of a set with $n$ elements?
Solution. There are ${}nC_k$ subsets of $k$ elements, $0\leq k\leq n$. Hence, the total number of subsets of a set of $n$ elements is $$\sum_{k=0}^n {}_nC_k=(1+1)^n=2^n$$
References:
Marcel B. Finan, A Probability Course for the Actuaries
Sheldon Ross, A First Course in Probability, Fifth Edition, Prentice Hall, 1997