Definition 5.2.1. Permutation.
A permutation is an ordered arrangement of objects.
Section 5.2 Permutations and Combinations
In the previous section, we were counting things that essentially occurred once. For example, we picked one outfit (one shirt, one pair of pants, one hat). In this section we’ll add complexity. Instead of picking an outfit for a day, how many different ways can our bag be packed for a weekend trip? We’ll answer it at the end of the section.
Subsection
Example 5.2.2.
If I want to arrange five books on a shelf, how many possible arrangements of the books are there?
Intuitively, the permutation of the five books is just the multiplication principle. There are five choices for the first, four for the second, ... until there’s only one choice. We found it was \(5\cdot 4 \cdot 3 \cdot 2 \cdot 1 = 5!\text{.}\)
Example 5.2.3.
How many functions \(f: \{1,2,3\} \to \{1, 2, 3\}\) are bijections?
Example 5.2.4.
If I only want to arrange three of the five books on my shelf, how many ways are there to do that?
This is still just the multiplication principle. There are five choices for the first, four for the second, but this time three choices for the third is our last book we take. Here we found it was \(5 \cdot 4 \cdot 3\text{.}\) But this suggests a pattern that is established in the following theorem and its useful corollary.
Theorem 5.2.5.
If \(n\) is a positive integer and \(r\) is an integer such that \(1 \le r \le n\text{,}\) then there are \(P(n,r) = n\cdot (n-1) \cdot (n-2) \cdot \dots \cdot (n-(r-1))\) \(r\)-permutations of a set of \(n\) elements.
Corollary 5.2.6.
If \(n\) and \(r\) are integers with \(0\le r \le n\text{,}\) then:
\begin{equation*}
P(n,r) = \dfrac{n!}{(n-r)!}
\end{equation*}
Example 5.2.7.
How many six-letter vanity license plates are there that have no repeated letters?
Example 5.2.8.
How many functions \(f: \{1,2,3,4\} \to \{1,2,3,4,5,6\}\) are injective? [Recall a function is injective \(\forall a, \forall b ( f(a) = f(b)) \to ( a = b )\)]
Permutations count those situations in which order matters, such as arranging books on a shelf. If the order of items doesn’t matter, we need to account for it as a combination.
Definition 5.2.9. Combination.
A combination is an unordered selection of objects.
Example 5.2.10.
If I want only to select three books from my five books on the bookshelf, in how many ways can I do this?
One way we can think about solving this previous example is that we solved the permutation question, but then we divided out the possible orderings. We started with \(P(n,r)\text{,}\) and divide by \(r!\text{,}\) the number of ways to arrange the \(r\) objects. This gives us a very convenient formula:
Note 5.2.11.
If \(n \and r\) are integers such that \(0 \le r \le n\text{,}\) then the number of \(r\)-combinations from a set of \(n\) elements is
\begin{equation*}
\binom{n}{r} = \dfrac{n!}{r!(n-r)!}
\end{equation*}
Example 5.2.12.
How many ways are there to choose five out of ten friends to invite over for dinner?
Example 5.2.13.
Two of your ten friends, Tim and Tammy just broke up. They can’t stand to be in a room together. How many ways are there to choose five out of ten friends to invite to dinner, ensuring that Tim and Tammy are not both invited?
Example 5.2.14.
How many three element subsets from a set of five elements are there?
Example 5.2.15.
From a standard deck of 52 cards, how many five card hands are possible?
Example 5.2.16.
How many five card cards have exactly the same suit?
Example 5.2.17.
How many five card hands have at least one heart?
Example 5.2.18.
Coming back to our packing for the weekend scenario from the introduction, let’s say, like in Example 5.1.3, that our closet has five ironic t-shirts, three pairs of pants, and three collegiate hats. We want to pack for our weekend trip, picking out three shirts, two pants, and two hats for our suitcase. How many ways can we do this?
Solution.
Just like when I pack, I’ll take one topic at a time:
- Picking shirts -- there are \(3\) shirts I’m picking from 5, so \(\binom{5}{3}\) Although the shirts are all different, the order I put them into the suitcase doesn’t matter, so it’s a combination.
- Picking my pants -- there are \(2\) shirts I’m picking from 3, so \(\binom{3}{2}\text{.}\)
- Picking my hat -- there are \(2\) hats I’m picking from 3, so \(\binom{3}{2}\) also.
In total, then, since the shirts, pants, and hats are all independent of one another, we multiply the results to find there are: there are
\begin{equation*}
\binom53 \binom32 \binom32 = 90
\end{equation*}
So there are ninety different ways to pack for the weekend.
Exercises Exercises
1.
A pizza parlor offers 10 toppings.
- How many 3-topping pizzas could they put on their menu? Assume double toppings are not allowed.
- How many total pizzas are possible, with between zero and ten toppings (but not double toppings) allowed?
- The pizza parlor will list the 10 toppings in two equal-sized columns on their menu. How many ways can they arrange the toppings in the left column?
Solution.
- \({10 \choose 3} = 120\) pizzas. We must choose (in no particular order) 3 out of the 10 toppings.
- \(2^{10} = 1024\) pizzas. Say yes or no to each topping.
- \(P(10,5) = 30240\) ways. Assign each of the 5 spots in the left column to a unique pizza topping.
2.
A combination lock consists of a dial with 40 numbers on it. To open the lock, you turn the dial to the right until you reach a first number, then to the left until you get to second number, then to the right again to the third number. The numbers must be distinct. How many different combinations are possible?
Solution.
Despite its name, we are not looking for a combination here. The order in which the three numbers appears matters. There are \(P(40,3) = 40\cdot 39 \cdot 38\) different possibilities for the “combination”. This is assuming you cannot repeat any of the numbers (if you could, the answer would be \(40^3\)).
3.
An anagram of a word is just a rearrangement of its letters. How many different anagrams of “uncopyrightable” are there? (This happens to be the longest common English word without any repeated letters.)
4.
How many anagrams are there of the word “assesses” that start with the letter “a”?
Solution.
After the first letter (a), we must rearrange the remaining 7 letters. There are only two letters (s and e), so this is really just a bit-string question (think of s as 1 and e as 0). Thus there \({7 \choose 2} = 21\) anagrams starting with “a”.
5.
How many anagrams are there of “anagram”?
6.
On a business retreat, your company of 20 businessmen and businesswomen go golfing.
- You need to divide up into foursomes (groups of 4 people): a first foursome, a second foursome, and so on. How many ways can you do this?
- After all your hard work, you realize that in fact, you want each foursome to include one of the five Board members. How many ways can you do this?
Solution.
- \({20 \choose 4}{16 \choose 4}{12 \choose 4}{8 \choose 4}{4 \choose 4}\) ways. Pick 4 out of 20 people to be in the first foursome, then 4 of the remaining 16 for the second foursome, and so on (use the multiplicative principle to combine).
- \(5!{15 \choose 3}{12 \choose 3}{9 \choose 3}{6 \choose 3}{3 \choose 3}\) ways. First determine the tee time of the 5 board members, then select 3 of the 15 non board members to golf with the first board member, then 3 of the remaining 12 to golf with the second, and so on.
7.
Consider sets \(A\) and \(B\) with \(|A| = 10\) and \(|B| = 17\text{.}\)
- How many functions \(f: A \to B\) are there?
- How many functions \(f: A \to B\) are injective?
Solution.
- \(17^{10}\) functions. There are 17 choices for the image of each element in the domain.
- \(P(17, 10)\) injective functions. There are 17 choices for image of the first element of the domain, then only 16 choices for the second, and so on.
