# 3: Permutations, Combinations, and the Binomial Theorem

• • Joy Morris
• University of Lethbridge
$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

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.3, Chlöe’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 had one daughter doesn’t mean they’ve used up their supply of X chromosomes so won’t have another daughter.

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.

• 3.1: Permutations
We begin by looking at permutations, because these are a straightforward application of the product rule. The word “permutation” means a rearrangement, and this is exactly what a permutation is: an ordering of a number of distinct items in a line. Sometimes even though we have a large number of distinct items, we want to single out a smaller number and arrange those into a line; this is also a sort of permutation.
• 3.2: Combinations
Sometimes the order in which individuals are chosen doesn’t matter; all that matters is whether or not they were chosen. An example of this is choosing a set of problems for an exam. Although the order in which the questions are arranged may make the exam more or less intimidating, what really matters is which questions are on the exam, and which are not.
• 3.3: The Binomial Theorem