Subsection
Definition 5.2.1. Permutation.
A permutation is an ordered arrangement of objects.
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:
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.