Chapter 3
Permutations, Combinations, and the Binomial Theorem
The examples we looked at in Chapter 2 involved drawing things from an effectively infinite population — they couldn't run out. When you are making up a password, there is no way you're going to “use up” the letter b by including it several times in your password. In Example 2.1.4, Chloë's suppliers weren't going to run out of blue t-shirts after printing some of her order, and be unable to complete the remaining blue t-shirts she'd requested. The fact that someone has already flipped a coin once with a result of heads doesn't mean they've used up that side of the coin so won't be able to flip heads again.
In this chapter, we'll look at situations where we are choosing more than one item from a finite population in which every item is uniquely identified — for example, choosing people from a family, or cards from a deck.
The study of permutations and combinations has a very long history, particularly in India and China. Much of the older historical context that will be provided in this book comes from handouts that were developed by Prof. Randy Schwartz of Schoolcraft College in the U.S. He has made a study of the history of mathematics in a non-eurocentric context, for incorporation into his own classes, and his handouts on “Combinations and Their Sums” and “Binomial Coefficients and Subsets” are particularly relevant to this course.
Summary.
The number of \(r\)-permutations of \(n\) objects is \(n!/(n-r)!\text{.}\)
The number of \(r\)-combinations of \(n\) objects is \(\binom{n}{r}=\frac{n!}{r!(n-r)!}\text{.}\)
The Binomial Theorem
-
Important definitions:
permutation, \(r\)-permutation
\(n\) factorial
\(r\)-combination
\(n\) choose \(r\)
binomial coefficients
-
Notation:
\(\displaystyle n!\)
\(\displaystyle \binom{n}{r}\)