1.1: Enumeration

Last updated
Save as PDF

Page ID: 70850

Joy Morris
University of Lethbridge

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\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]{\| #1 \|}\) \( \newcommand{\inner}[2]{\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]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Enumeration is a big fancy word for counting. If you’ve taken a course in probability and statistics, you’ve already covered some of the techniques and problems we’ll be covering in this course. When a statistician (or other mathematician) is calculating the “probability” of a particular outcome in circumstances where all outcomes are equally likely, what they usually do is enumerate all possible outcomes, and then figure out how many of these include the outcome they are looking for.

Example \(\PageIndex{1}\)

What is the probability of rolling a 3 on a 6-sided die?

Solution

To figure this out, a mathematician would count the sides of the die (there are six) and count how many of those sides display a three (one of them). She would conclude that the probability of rolling a 3 on a 6-sided die is \(\dfrac{1}{6}\) (one in six).

That was an example that you could probably figure out without having studied enumeration or probability, but it nonetheless illustrates the basic principle behind many calculations of probability. The object of enumeration is to enable us to count outcomes in much more complicated situations. This sometimes has natural applications to questions of probability, but our focus will be on the counting, not on the probability.

After studying enumeration in this course, you should be able to solve problems such as:

If you are playing Texas Hold’em poker against a single opponent, and the two cards in your hand are a pair, what is the probability that your opponent has a higher pair?
How many distinct Shidokus (4-by-4 Sudokus) are there?
How many different orders of five items can be made from a bakery that makes three kinds of cookies?
Male honeybees come from a queen bee’s unfertilised eggs, so have only one parent (a female). Female honeybees have two parents (one male, one female). Assuming all ancestors were distinct, how many ancestors does a male honeybee have from 10 generations ago?

Although all of these questions (and many others that arise naturally) may be of interest to you, the reason we begin our study with enumeration is because we’ll be able to use many of the techniques we learn, to count the other structures we’ll be studying.