CMSC-27100

Discrete Math

Winter Quarter, 2019

Home Lectures Policies

---

Piazza

Lecture 11: Permutations and Combinations

\( \newcommand{\set}[1]{\{#1\}} \newcommand{\comprehension}[2]{\{#1\,\vert\,#2\}} \newcommand{\size}[1]{\left\vert#1\right\vert} \newcommand{\true}{\top} \newcommand{\false}{\bot} \newcommand{\limplies}{\rightarrow} \newcommand{\divides}{\mathbin{\vert}} \newcommand{\mult}{\mathbin{\cdot}} \newcommand{\xor}{\oplus} \newcommand{\union}{\cup} \newcommand{\intersect}{\cap} \newcommand{\complement}[1]{\overline#1} \newcommand{\powerset}{\mathcal{P}} \newcommand{\ixUnion}{\bigcup} \newcommand{\ixIntersect}{\bigcap} \newcommand{\Div}{\mathrm{div}} \newcommand{\gcd}{\mathrm{gcd}} \newcommand{\divmod}{\mathop{\mathbf{divmod}}} \newcommand{\div}{\mathop{\mathbf{div}}} \newcommand{\mod}{\mathop{\mathbf{mod}}} \newcommand{\ceiling}[1]{\lceil#1\rceil} \newcommand{\floor}[1]{\lfloor#1\rfloor} \)

Permutations

Example 11.1 Imagine a race, with $8$ contestants, and $3$ medals, gold, silver, and bronze. How many different medal outcomes are possible?

This is a calculation we've done before: there are $8$ different runners who could have won the gold medal, leaving $7$ possibilities for the silver, and $6$ for the bronze, i.e., $8 \mult 7 \mult 6 = 336$.

Definition 11.2 A permutation of a set is an ordered arrangement of its elements (i.e., a list with the same elements as the set). An $r$-permutation is an ordered arrangement of $r$ distinct elements of a set $S$.

Example 11.3 If we consider the set $\set{1,2,3}$, we can easily see has $6$ permutations:

• $[1,2,3]$,
• $[1,3,2]$,
• $[2,1,3]$,
• $[2,3,1]$,
• $[3,1,2]$, and
• $[3,2,1]$.

If we consider $2$-permutations of the same set, we can easily see that there are also $6$ such:

• $[1,2]$,
• $[1,3]$,
• $[2,1]$,
• $[2,3]$,
• $[3,1]$, and
• $[3,2]$.

The fact that we got the same number both times is not a coincidence.

Consider now the problem in general.

Theorem 11.4 If $P(n,r)$ denotes the number of $r$-permutations of an $n$ element set, then

\begin{equation*} P(n,r) = n \mult (n-1) \mult \cdots \mult (n-r+1). \end{equation*}

Proof There are $n$ ways to choose the first element, $n-1$ ways to chose the second, and in general $n-i+1$ ways to chose the $i$-th element. The equation follows from the (iterated) product rule.

$\Box$

We can state this somewhat differently, as follows:

Corollary 11.5 If $n$ is positive, and $0 \leq r \leq n$, then

\begin{equation*} P(n,r) = {n! \over (n-r)!} \end{equation*}

This equation isn't necessarily a useful one for computing, but the closed form is useful for intermediate calculations, and the derivation of many identities.

A cute observation, and one that confirms the validity of this form, is to start with the special case of (full) permutations: the number of ways to order an $n$ element set is $n!$. But we can do the count slightly differently: first choosing $r$ items from the set in $P(n,r)$ different ways, and then choosing the remaining $n-r$ items in $(n-r)!$ different ways. Thus,

\begin{align*} n! &= P(n,r) \cdot (n-r)!\tag{Product rule} \\ P(n,r) &= {n! \over (n-r)!} \end{align*}

Example 11.6 A condo association has 20 owners, and a board of directors that consists of a President, Vice-President, Treasurer, Secretary, and Director at-large. How many possible different boards can exist? Because we're concerned about offices, this amounts to an ordered selection: first the President, then the Vice-President, etc. So the answer is $P(20,5) = 20 \mult 19 \mult 18 \mult 17 \mult 16 = 1,860,480$.

Example 11.7 How many permutations of the letters ABCDEFGH contain the letters ABC consecutively? This is a problem with a trick. We view the underlying set as consisting of 6 elements: ABC, D, E, F, G, and H. Any permutation that has the character we want amounts to a permutation of these six, so the answer is $P(6,6) = 6! = 720$.

Combinations

A closely related problem is trying to figure out how many distinct $r$ elements subsets can be formed from an $n$ element set. Notice the subtle but important change, before we were concerned about ordered arrangements of elements, now we are concerned with sets, which are intrinsically unordered. The contrast is clear if we replay Example 11.3 but with subsets rather than ordered collections. In particular, while there were (by abuse of nominclature) $6$ ordered subsets of $\set{1,2,3}$ of size $3$, there's only one subset of $\set{1,2,3}$ of size $3$, $\set{1,2,3}$ itself. Likewise, while there are $6$ ordered subsets of size $2$, there are only $3$ unordered subsets:

• $\set{1,2}$,
• $\set{1,3}$, and
• $\set{2,3}$.

Definition 11.8 An $r$-combination of a set with $n$ elements is a subset of size $r$. The number of $r$-combinations of a set with $n$ elements is $C(n,r)$.

Note: Many a beginner has struggled with keeping permutations and combinations straight. Which is the ordered one? Which the unordered one? Many a struggling beginner has been helped with an observation that doubles as a mnemonic: “Combination locks ought to be called permutation locks.”

Rather than give an example, let's first give a formula for $C(n,r)$:

Theorem 11.9 If $n$ is positive, and $0 \leq r \leq n$, then

\begin{equation*} C(n,r) = {n! \over r!(n-r)!} \end{equation*}

Proof We've already seen that $P(n,r) = {n!\over (n-r)!}$ for these choices of $n$ and $r$. Let's give another way to count the number of $r$-permutations of an $n$ element set. First, we chose an $r$ element subset (which we can do in $C(n,r)$ many ways); then we chose an ordering of that subset (which we can do in $P(r,r) = r!$ many ways). Putting this together, we have:

\begin{align*} P(n,r) &= C(n,r) \cdot P(r,r)\\ C(n,r) &= {P(n,r) \over P(r,r)}\\ C(n,r) &= {n! \over r!\cdot (n-r)!} \end{align*}

$\Box$ Theorem 11.9

The book notes that this characterization of $C(n,r)$ isn't all that useful, because the factorial function grows very quickly. This is so, but evidently he hasn't worked with language that provide support for infinite precision integer arithmetic. If the only languages that did so were functional languages like Scheme and Haskell, it would be one thing. But Python?! Still, there usually are better ways to compute $C(n,r)$, but the brute force way isn't entirely infeasible, so long as you have the right tools.

Example 11.10 How many distinct poker hands exist?

The answer is clearly $C(52,5) = 2,598,960$.

Example 11.11 How many distinct full houses exist?

Recall, a full house is a three-of-a-kind together with a pair. We can think about this in several ways. Here's a slick one. We pick two denominations, in order (because the three-of-a-kind and pair are distinct), $P(13,2)$. We can then choose the three-of-a-kind in $C(4,3)$ many distinct ways, and the pair in $C(4,2)$ many ways. By the product rule, the count is

\begin{align*} n &= P(13,2) \mult C(4,3) \mult C(4,2)\\ &= (13 \mult 12) \mult {4 \mult 3\ \mult 2 \over 1 \mult 2 \mult 3} \mult {4 \mult 3 \over 1 \mult 2}\\ &= 156 \mult 4 \mult 6\\ &= 3,744 \end{align*}

Example 11.12 How many flushes exist?

We first choose one of four suits ($C(4,1)$), and then from that suit, we choose $5$ of the $13$ cards of that suit ($C(13,5)$):

\begin{align*} n &= C(4,1) \mult C(13,5) \\ &= {4 \over 1} \mult {13 \mult 12 \mult 11 \mult 10 \mult 9\over 1 \mult 2 \mult 3 \mult 4 \mult 5}\\ &= 4 \mult 13 \mult 11 \mult 9\\ &= 5,148 \end{align*}

Note that this calculation includes straight and royal flushes. If we wanted to exclude them, we'd need to count the number of straight and royal flushes. We can easily calculate both. There are only four royal flushes -- one for each suit. Any other straight-flush must begin with an ace through $9$ (the ace can occur at the top or bottom of a straight), and there are $9$ such numbers, and $4$ suits. So, $9\mult 4 = 36$ non-royal straight flushes, leaving $5148-40 = 5108$ ordinary flushes.

Definition 11.13 A combinatorial proof is a proof based on a counting argument. Often, it involves counting the same thing two different ways to achieve a combinatorial identity.

The nice thing about combinatorial proofs is that they often facilitate discovery, and allow very direct proofs, c.f.,

Theorem 11.14 For all $n>0$ and $0\leq r \leq n$, $C(n,r) = C(n,n-r)$.

Proof Given a set $S$ with $n$ elements, we can either enumerate its $r$ element subsets directly ($C(n,r)$), or we can enumerate their complements ($C(n,n-r)$). Thus, $C(n,r) = C(n,n-r)$.

$\Box$ Theorem 11.14

Example 11.15 Assume we do an in-order shuffle of the list of the consonants $b, c, d, f, g\ldots$ with the list of vowels $a, e, i, o, u, y$. How many possibilities are there?

This involves a bit of insight, but it's a common and important idea. We end up building a list of $26$ elements, exactly $6$ of which are occupied by vowels. Knowing the spots occupied by vowels completely determines the in-order shuffle, so the answer must be $C(26,6) = 177,100$.

---

© 2016–2019 Stuart A. Kurtz
Last modified: March 13, 2019