Skip to main content

Section 6.2 Permutations and combinations*

We begin with the idea of permutations - that is arrangements of objects. We'll use python to see if we can find a pattern. The package that we need is called itertools, which we will need to import to use the command permutations.

If we keep this going, the lists will get very long. We aren't going to be working directly with the arrangements typically-- we're counting. So what we really need to know is how many arrangements are in each list.

These numbers may be familiar to you: they are the factorials. Recall that \(n! = 1\cdot 2 \cdot 3 \cdot \ldots \cdot (n-1) \cdot n\text{.}\)

We can change the problem slightly. Imagine that from a pool of \(n\)objects, we select \(r\) of them and make arrangements. For example, I might want to know how many ways I can choose a class president, vice president, and secretary from a group of 30 students. One way of looking at this is in terms of choice: I have 30 possible choices for president, 29 for vice-president after I've selected the president, and 28 for the secretary. By the fundamental principle of counting, I have \(30 \cdot 29 \cdot 28\) possible choices. This is a perfectly valid way of counting permutations of a subset, but we're looking for something that can be generalized and not treated case by case. A simple computational trick (essentially cleverly unsimplifying a fraction) will let us write this in a more useful form:

\begin{equation*} 30 \cdot 29 \cdot 28 = \frac{30 \cdot 29 \cdot 28 \cdot (27 \cdot \ldots \cdot 1)}{(27 \cdot \ldots \cdot 1)} = \frac{30!}{27!} = \frac{30!}{(30 - 3)!} \end{equation*}

This motivates the observation that the number of permutations of \(n\) objects taken \(r\) at a time is

\begin{equation*} n P r = \frac{n!}{(n-r)!}\text{.} \end{equation*}

In many cases, we want to know how many ways to choose \(r\) objects from a collection of \(n\) total objects, but we aren't concerned with the order of the choosing. For example, playing a card game, typically the cards in the players hand can be ordered in the hand any way the player wishes. This type of unordered selection is called a combination of \(n\) objects taken \(r\) at a time.