Combinations

Section 3.4 Combinations

Definition 3.4.1.

Broadly, a combination is a selection of objects where order doesn't matter.

In other words, an unordered selection, where two selections are the same if they consist of the same elements, regardless of the order in which the elements are chosen.

Example 3.4.2.

Consider a group of 5 distinct balls. How many ways can one choose a collection of 3 balls from these 5 balls? This can be framed as a permutation. List the balls from 1-5, and write I if the ball is included in the collection and E if it is excluded. For example, the particular collection of balls 2, 4, and 5 would be represented by \(EIEII\text{.}\) For another example, choosing balls 1, 2, and 3 is represented by \(IIIEE\text{.}\) In general, there is a one-to-one correspondence between the combinations of 5 balls taken 3 at a time, and permutations of this 5-character sequences of E's and I's. From permutations, we know that there are \(\frac{5!}{2! 3!} = 10\) permutations of \(EIEII\text{,}\) and so there are also 10 combinations.

Subsection 3.4.1 Combinations

More generally, if there are \(n\) distinct objects, being chosen \(n\) at a time, then the number of combinations is equal to the number of permutations of an \(n\)-character sequence, where there are \(n\) identical objects of one kind (in the example, the I's), and \(n-r\) identical objects of another kind (the E's). Then,

Theorem 3.4.3. Combinations.

The number of combinations of \(n\) distinct objects taken \(n\) at a time, \(\nCr{n}{k}\) (read as “\(n\) choose \(n\)”), is given by,

\begin{equation*} \nCr{n}{k} = \frac{n!}{(n - k)!k!} \end{equation*}

Sometimes, the alternate notation \(\binom{n}{k}\) is used to represent \(\nCr{n}{k}\text{,}\) especially in more advanced mathematics.

Subsection 3.4.2 Number of Subsets of a Given Size

Another important, more formal interpretation of combinations is as the number of subsets of a set, of a certain size.

Theorem 3.4.4.

Let \(A\) be a set of \(n\) elements, \(A = \set{a_1, \dots, a_n}\text{.}\) Then, the number of \(k\) element subsets of \(A\) is,

\begin{equation*} \nCr{n}{k} = \frac{n!}{k!(n - k)!} \end{equation*}

Note that the numbers of 1 element subsets is \(n\) (as there are \(n\) possible sets). For 2 element subsets, there are \(n\) ways to choose the first element, and \(n-1\) ways to choose the second element, for \(n(n - 1)\) ways to choose both. However, this assumes that order is relevant, that \(\set{s_3, s_4}\) is different than \(\set{s_4, s_3}\text{.}\) There are 2 ways to order each selection of 2 elements, so the total number of 2 element subsets is \(\frac{n(n - 1)}{2}\text{.}\)

For 3 element subsets, in a similar way, there are \(n(n - 1)(n - 2)\) ways to select 3 elements from \(n\) elements where order matters, and \(3 \cdot 2 \cdot 1 = 3! = 6\) ways to order a selection of 3 elements. Thus, the number of 3 element subsets is \(\frac{n(n - 1)(n - 2)}{6}\text{.}\)

In general, the number of \(k\) element subsets of an \(n\) element set is given by,

\begin{equation*} \frac{n(n - 1)(n - 2) \cdots (n - (k - 1))}{k!} \end{equation*}

This can be rewritten as,

\begin{align*} \frac{n(n - 1)(n - 2) \cdots (n - (k - 1))}{k!} \amp = \frac{n(n - 1)(n - 2) \cdots (n - (k - 1))}{k!} \cdot \frac{(n - k)!}{(n - k)!}\\ \amp = \frac{n!}{k!(n - k)!} \end{align*}

Subsection 3.4.3 Other Examples

Example 3.4.5. Diagonals of a regular polygon.

Consider a regular polygon, and its number of diagonals. Recall that a diagonal is a line segment that connects two vertices which are non-adjacent. We want to consider the number of diagonals of a regular polygon with \(n\) sides. The result should be a function of \(n\text{.}\)

First, consider \(n = 3, 4, 5, 6, \dots\text{.}\) It turns out that,

\begin{equation*} \begin{array}{ccc} \text{number of sides } n \amp \text{number of diagonals } d_n \\ 3 \amp 0 \\ 4 \amp 2 \\ 5 \amp 5 \\ 6 \amp 9 \\ 7 \amp 14 \end{array} \end{equation*}

The first observation you may make is that the number of diagonals is not a linear function of \(n\text{.}\)

To form a diagonal, we need to choose 2 vertices. The first vertex we choose can be any of the \(n\) vertices. Then, to select the other vertex, we can choose from any of the vertices except for the vertex we already chose, and the two vertices adjacent to the vertex we chose, which gives \(n-3\) choices. This gives \(n(n-3)\) choices in total. However, the order of the vertex choice doesn't matter, because choosing vertex P and then Q produces the same diagonal as choosing Q and then P. So, we divide by 2 to get the result,

\begin{equation*} \boxed{d_n = \frac{n(n-3)}{2}} \end{equation*}

Using combinations, a diagonal is made up of a pair of vertices. There are \(\nCr{n}{2} = \frac{n(n-1)}{2}\) ways to choose two vertices from \(n\text{.}\) Then, there are \(n\) choices which produce non-diagonals, each corresponding to the \(n\) sides of the polygon. Thus, in total, the number of diagonals is,

\begin{align*} \end{align*}

which is equivalent to the previous result.