6.2. Permutations and Combinations#

In this section we will extend the idea of counting to permutations and their closely related sibling, combinations.

Both of these concepts extend the idea of choosing items from a set (product rule and sum rule) to consider additional replacement or, rather, lack thereof.

6.2.1. Permutations#

Definition (permutation)

A permutation of a set of objects is an ordered arrangement of those objects. An ordered arrangement of \(r\) objects is a called an \(r\)-permutation.

For a set \(A\) of size \(n\), an \(n\)-permutation of \(A\) is simply some ordering of the elements of \(A\).

Permutations of a set

Let \(A = \{a,b,c\}\).

A \(3\)-permutation of \(A\) is \(a, b, c\).

Another \(3\)-permutation of \(A\) is \(c, a, b\).

Another \(3\)-permutation of \(A\) is \(b, a, c\).

A \(2\)-permutation of \(A\) is \(a,b\), another is \(b,a\).

A fundamental consideration of permutations is the number of possible permutations. For a set of size \(n\), there is a precise number of possible \(r\)-permutations. This number is denoted \(P(n,r)\).

Theorem

For positive integers \(n,r\) with \(n \geq r\), the number of \(r\)-permutations on a set of \(n\) elements is:

\[ P(n,r) = n \cdot (n-1) \cdot (n-2) \cdots (n - r + 1) \]

Proof: Use the product rule. From a set of size \(n\), we have \(n\) possible choices. After that choice, there are \(n-1\) remaining elements of the set to choose from. After that choice, there are \(n-2\) remaining elements to chose from. Continue in this way for \(r\) choices. By the product rule, this results in:

\[ P(n,r) = n \cdot (n-1) \cdot (n-2) \cdots (n - r + 1) \qquad\qquad \blacksquare \]

Note: \(P(n,0) = 1\) by definition since there is only \(1\) way to arrange nothing… no arrangement at all.

Corollary

For positive integers \(n,r\) with \(n \geq r\), we have:

\[ P(n,r) = \frac{n!}{(n-r)!} \]

Counting contest winners

Consider a contest with \(56\) participants. Assuming there are no ties, how many ways can first, second, and third place be awarded?

To choose first place, there are \(56\) choices. To choose second, there are then \(55\) choices. To choose third, there are \(54\) choices. By the product rule, there are \(56 \cdot 55 \cdot 54 = 166320\) different ways to award first through third place.

Alternatively, we could use the formula for \(P(56,3) = \frac{56!}{53!} = 166320\).

Counting permutations

You are tasked with designing a new bus route for the London Transit Commission. This route must start and stop at Oxford and Richmond. After that, it must visit \(8\) other stops. Assuming Oxford and Richmond is the only stop visited twice (the start point and the end point) How many possible routes are there covering all stops?

Counting permutations

The start and end points of the route are determined for us. After that, we have \(8\) possible stops on which to choose an order. This leaves \(P(8,8) = 8! = 40320\) possible routes!

If we want to find the shortest route, we should check all 40,320 routes… that’s a lot. (This alludes to Section 7).

6.2.2. Combinations#

Combinations are simply permutations where order does not matter.

Definition (combination)

An \(r-\)combination is an unordered arrangement of \(r\) elements of a set. An \(r\)-combination of a set is a subset with \(r\) elements.

For a set \(A\) of size \(n\), an \(n\)-combination of \(A\) is just \(A\) itself! Since both sets and combinations do not care about ordering, they are the same thing if they have the same number of elements.

Combinations of a set

Let \(A = \{a,b,c\}\).

The only \(3\)-combination of \(A\) is \(a, b, c\).

The \(2\)-combinations of \(A\) are \(a,b\); \(a,c\); and \(b,c\).

Of course, we are interested in counting the number of possible combinations. The number of \(r\)-combinations of a set of size \(n\) is denoted by \(C(n,r)\). Its value is given by the following theorem.

Theorem

For non-negative integers \(n,r\) with \(n \geq r\), the number of \(r\)-combinations of a set of \(n\) elements is:

\[ C(n,r) = \frac{n!}{(n-r)!\,\cdot\ r!} \]

Proof:

Combinations are just permutations which do not care about order. Given an \(r\)-permutation, there are \(P(r,r)\) possible orderings of that permutation. Therefore, for each \(r\)-combination there are \(P(r,r)\) different possible permutations. Thus, \(C(n,r) = P(n,r) / P(r,r) = \frac{n!}{(n-r)!} \,/\, r!\). \(\blacksquare\)

Counting soccer teams

In an grade 4 gym class, there are \(28\) students. How ways can these students be separated into \(2\) soccer teams?

The order in which students are assigned to each team does not matter, only the composition of the teams. Thus, this is a question about combinations.

\[ C(28,14) = \frac{28!}{14! \cdot 14!} = 40,116,600 \]

Here’s a neat identity about combinations.

Corollary

Let \(n,r\) be non-negative integers with \(n \geq r\).

\[ C(n,r) = C(n, n-r) \]

Proof:

From the previous theorem, we have:

\[ C(n,r) = \frac{n!}{(n-r)!\ \cdot\ r!} \]

and

\[\begin{split} C(n,n-r) &= \frac{n!}{(n - (n-r))!\ \cdot\ (n-r)!} \\[1em] &= \frac{n!}{(n-r)!\ \cdot\ r!} \qquad \qquad \blacksquare \end{split}\]

This corollary tells us that there are the same number of \(r\)-combinations as there are \((n-r)\)-combinations.

Intuitively, this makes some sense. There are the same number of ways to choose \(r\) items as there are ways to not choose \(r\) items. Where there are \(n\) items to choose from, not choosing \(r\) items is the same as choosing \(n-r\) items.

\(C(n,r)\) appears in many places throughout mathematics. Thus, we give it some special names and notations.

\(C(n,r) = \binom{n}{r}\) and is read “\(n\) choose \(r\)”. This notation explicitly refers to how choosing \(r\) objects from a set of \(n\) things can be done in \(C(n,r)\) different ways.

\(\binom{n}{r}\) is also called a binomial coefficient.

6.2.3. Binomial Coefficients#

A binomial is a polynomial with 2 terms. We are familiar with binomials and “FOIL”. We all know that:

\[ (a + b)(c + d) = ac + ad + bc + bd. \]

When \(a=c\) and \(b =d\), we get some simplifications:

\[ (a+b)^2 = a^2 + 2ab + b^2. \]

Can we generalize this idea of FOIL to any power \(n\)? What is \((x+y)^n\)? We can use the principles of counting to compute \((x+y)^n\) without doing any algebra.

Let us illustrate this idea with \((x+y)^3\).

Binomial coefficients of a cubic

What is the expansion of \((x+y)^3\)?

In this product we have \(3\) copies of \(x+y\). In the expansion, we choose between multiplying by \(x\) and multiplying by \(y\) \(3\) times.

  1. To get \(x^3\) we must choose \(x\) 3 times.

  2. To get \(y^3\) we must choose \(y\) 3 times.

  3. To get \(x^2y\) we must choose \(x\) twice and \(y\) once.

  4. To get \(xy^2\) we must choose \(x\) once and \(y\) twice.

Thus, the final expansion will have \(x^3, y^3, x^2y, xy^2\). But, how many copies of each?

Since multiplication is commutative, \(x\cdot y \cdot x = y \cdot x \cdot x = x^2y\). Thus, this is a question of combinations rather than permutations.

  1. To get \(x^3\) we much choose \(x\) 3 out of 3 times. \(C(3,3) = 1\)

  2. To get \(y^3\) we much choose \(y\) 3 out of 3 times. \(C(3,3) = 1\)

  3. To get \(x^2y\) we much choose \(x\) 2 out of 3 times (and thus \(y\) is chosen 1 of 3 times). \(C(3,2) = 3\)

  4. To get \(xy^2\) we much choose \(x\) 1 out of 3 times. \(C(3,1) = 3\)

Therefore, \((x+y)^3 = x^3 + 3x^2y + 3xy^2 + y^3\).

Generalizing this construction to a power of \(n\) results in the binomial theorem.

Binomial Theorem

\[ (x+y)^n = \sum_{r=0}^n \binom{n}{r} x^{n-r}y^r \]

Expanding the binomial theorem for \(n= 3\), we get the same result as our previous example.

\[\begin{split} (x+y)^3 &= \binom{3}{0} x^{3}y^0 + \binom{3}{1} x^{2}y^1 + \binom{3}{2} x^{1}y^2 + \binom{3}{3} x^{0}y^3 \\[1.5em] &= \binom{3}{3} x^{3}y^0 + \binom{3}{2} x^{2}y^1 + \binom{3}{1} x^{1}y^2 + \binom{3}{0} x^{0}y^3 \\[1.5em] &= x^3 + 3x^2y + 3xy^2 + y^3 \end{split}\]

Using the binomial theorem

What is the coefficient of \(x^{13}y^{11}\) in \((x+y)^{24}\)?

We have \(x^{24-11}y^{11}\). By the binomial theorem, its coefficient is

\[ \binom{24}{11} = \frac{24!}{(24-11)!(11!)} = 2496144. \]

Recall that combinations are really just subsets and \(C(n,r) = \binom{n}{r}\). Thus, the following corollary follows naturally.

Corollary

For a non-negative integer \(n\)

\[ \sum_{r=0}^n \binom{n}{r} = 2^n \]

Proof: Apply the binomial theorem to \(2^n = (1 + 1)^n\). \(\blacksquare\)

Since an \(r\)-combination is a subset of size \(r\), the set of all possible subsets counts \(2^n\) for a set with \(n\) elements. We have already seen this several times as the identity involving the power set: \(|\mathcal{P}(A)| = 2^{|A|}\).

Pascal’s Identity and Pascal’s Triangle

Pascal and his famous triangle give the following recurrence relation.

\[ \binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k} \]

In Pascal’s Triangle the \(n\)-th row of the triangle gives the coefficients of the binomial expansion \((x+y)^n\). The triangle is constructed recursively using the above recurrence.

../_images/PascalTri.png

Fig. 6.3 Pascal’s triangle for \(0 \leq n \leq 8\).#

The left and right edges of a triangle are always \(1\) since \(\binom{n}{0} = \binom{n}{n} = 1\). Then, the interior points of the triangle are constructed using the recurrence relation, looking “up” to the previous row and adding together the “up-left” and “up-right” elements.

6.2.4. Exercises#

Exercise 6.8

Suppose you are interviewing \(25\) people in order to fill \(5\) job vacancies. How many possible choices of \(5\) people are there to fill those vacancies?

Exercise 6.9

Given a standard \(52\)-deck of playing cards, how many different 5-hand flushes are there. That is how many different sets of \(5\) cards all have the same suit?

Exercise 6.10

What is the coefficient of \(x^{9}y^{12}\) in \((4x - 9y)^{21}\)?