In my previous note here, I mentioned that a combination is an arrangement of things with no order. To further discuss combinations let us begin with the following example.

Example. How many different ways are there to permute three letters from $A=\{a,b,c,d\}$?

Solution. $P(4.3)=\frac{4!}{(4-3)!}=4!=24$.

Example. How many ways can we select three letters from $A=\{a,b,c,d\}$?

Solution. Note that with this question we are not interested in the order of arranging three letters but are only interested in selecting three letters. For each choice of a group of three letters, there are $3!$ permutations among the letters we won’t distinguish. Hence, the answer is $$\frac{P(4,3)}{3!}=\frac{4!}{3!(4-3)!}=4$$ Those four selections are \begin{array}{c}abc\\abd\\acd\\bcd\end{array}

The number of selecting $r$ elements from a set of $n$ elements, $0\leq r\leq n$ is denoted by $\begin{pmatrix}n\\r\end{pmatrix}$, $C(n,r)$ or ${}_nC_r$ and by using a similar argument to the one we made in the above example, we obtain \begin{equation}\label{eq:comb}\begin{pmatrix}n\\r\end{pmatrix}=\frac{n!}{r!(n-r)!}\end{equation} $\begin{pmatrix}n\\r\end{pmatrix}$ is called binomial coefficient for a good reason which will be mentioned later. The sage command for calculating $\begin{pmatrix}n\\r\end{pmatrix}$ is binomial(n,r).

Note that the formula \eqref{eq:comb} is symmetrical, meaning the number of selecting $r$ elements from $n$ elements or the number of selecting $n-r$ elements from $n$ elements are the same: $$\begin{pmatrix}n\\r\end{pmatrix}=\frac{n!}{r!(n-r)!}=\frac{n!}{(n-r)!r!}=\frac{n!}{(n-r)!(n-(n-r))!}=\begin{pmatrix}n\\n-r\end{pmatrix}$$ This can be easily understood without working through the algebra above: the number of selecting $r$ elements from $n$ elements is the same as the number of not selecting $n-r$ elements from $n$ elements.

Example. A committee of 3 is to be formed from a club of 20 people. How many different committees are possible?

Solution. $\begin{pmatrix}20\\3\end{pmatrix}=\frac{20!}{3!17!}=\frac{20\cdot 19\cdot 18}{3\cdot 2\cdot 1}=1140$.

Example. In the above example, if the treasurer must be on the committee, the answer changes to $\begin{pmatrix}19\\2\end{pmatrix}=171$. If we further require that a chairperson other than the treasurer be selected, then there are $\begin{pmatrix}19\\2\end{pmatrix}\cdot 2=342$ different committees. If the treasure can be a chairperson, there are $\begin{pmatrix}19\\2\end{pmatrix}\cdot 3=513$ different committees.

Example. Assume that a coin is tossed 5 times. In how many ways can three heads be obtained?

Solution. $\begin{pmatrix}5\\3\end{pmatrix}=\frac{5!}{2!3!}=10$.

Example. When a fair coin is tossed 5 times, how many ways can we possibly observe?

Solution. There are 6 different cases: when we observe 5 heads, 4 heads, 3 heads, 2 heads, 1 head, or 0 head (i.e. all 5 tails). Hence there are $$\begin{pmatrix}5\\5\end{pmatrix}+\begin{pmatrix}5\\4\end{pmatrix}+\begin{pmatrix}5\\3\end{pmatrix}+\begin{pmatrix}5\\2\end{pmatrix}+\begin{pmatrix}5\\1\end{pmatrix}+\begin{pmatrix}5\\0\end{pmatrix}=1+5+10+10+5+1=32$$ Or more simply, for each coin toss, there are two possible outcomes (head or tail). So by the basic principle of counting there are $2^5=32$ possible outcomes from 5 coin tosses.

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 2 of the men are feuding and refused to serve on the committee together?

Solution. There can be $\begin{pmatrix}5\\2\end{pmatrix}\begin{pmatrix}7\\3\end{pmatrix}=350$ different committees consisting of 2 women and 3 men. If two men refuse to serve on the committee together, we can either include only one of the two men in the committee or neither of the two men in the committee. Hence, in this case we have $\begin{pmatrix}2\\0\end{pmatrix}\begin{pmatrix}5\\3\end{pmatrix}+\begin{pmatrix}2\\1\end{pmatrix}\begin{pmatrix}5\\2\end{pmatrix}=30$ different groups of men not containing both of the two feuding men. Since there are $\begin{pmatrix}5\\2\end{pmatrix}$ different ways to choose the two women, it follows that there are $30\begin{pmatrix}5\\2\end{pmatrix}=300$ possible committees.

Example. Consider a set of $n$ antennas of which $m$ are defective and $n-m$ are functional. Assume that the functional and the defective antennas are not distinguishable. How many linear orderings are there in which no two defectives are consecutive?

Solution. Imagine that the $n-m$ functional antennas are lined up. Since no two defective antennas are consecutive, the spaces between functional antennas must contains at most one defective antennas. There are $n-m+1$ possible positions for defective antennas. Hence, there are $\begin{pmatrix}n-m+1\\m\end{pmatrix}$ possible linear orderings.

Lemma. \begin{equation}\label{eq:combidentity}\begin{pmatrix}n\\r\end{pmatrix}=\begin{pmatrix}n-1\\r-1\end{pmatrix}+\begin{pmatrix}n-1\\r\end{pmatrix}\end{equation} where $1\leq r\leq n$.

Proof. Consider a group of $n$ objects and fix attention on a particular object. Let us call it object 1. There are then $\begin{pmatrix}n-1\\r-1\end{pmatrix}$ groups of size $r$ that contain object 1. There are also $\begin{pmatrix}n-1\\r\end{pmatrix}$ groups of size $r$ that do not contain object 1. Hence we obtain the identity in \eqref{eq:combidentity}.

Theorem. (The Binomial Theorem) \begin{equation}\label{eq:binomthm}(x+y)^n=\sum_{r=0}^n\begin{pmatrix}n\\r\end{pmatrix}x^ry^{n-r}\end{equation}

The binomial theorem \eqref{eq:binomthm} can be proved by mathematical induction along with the identity in \eqref{eq:combidentity}. I will leave details of proof for readers.

Example. Expand $(x+y)^3$.

Solution. \begin{align*}(x+y)^3&=\begin{pmatrix}3\\0\end{pmatrix}x^0y^3+\begin{pmatrix}3\\1\end{pmatrix}x^1y^2+\begin{pmatrix}3\\2\end{pmatrix}x^2y^1+\begin{pmatrix}3\\3\end{pmatrix}x^3y^0\\&=y^3+3xy^2+3x^2y+x^3\end{align*}

The example below gives an alternative proof to Power Set Cardinality Theorem we discussed here.

Example. How many subsets are there of a set consisting of $n$ elements?

Solution. There are $\begin{pmatrix}n\\r\end{pmatrix}$ subsets of size $r$, so the answer is \begin{equation}\label{eq:binom}\sum_{r=0}^n\begin{pmatrix}n\\r\end{pmatrix}=(1+1)^n=2^n\end{equation}

References: Not in particular order.

[1] Applied Discrete Structures, Al Doerr and Ken Levasseur. This book is available for free under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 United States License.

[2] A First Course in Probability, Sheldon Ross, 5th Edition, Prentice-Hall, 1998

[3] Essential Discrete Mathematics for Computer Science, Harry Lewis and Rachel Zax, Princeton University Press, 2019