Enumeration

Introduced in Chapter 1 of MATH239.

Suppose I pay $5 for a lottery ticket – what is the chance that I win a share of the top prize?

There are a certain number of ways to win, and a certain number of ways to lose. Enumeration is the art and science of figuring out this kind of thing.

2 broad principles of the subject:

1. Combinatorial approach is to construct explicit one-to-one correspondences between sets to show that they have the same size.
   • use Combinatorial Proof
2. The algebraic approach is to translate the information about the problem from combinatorics into algebra, and then to use algebraic techniques to determine the sizes of the sets.

Basic Principles of Enumeration

Example 1.1. On a table before you are 7 apples, 8 oranges, and 5 bananas.

• Choose an apple and a banana. There are 7 choices for an apple AND 5 choices for a banana: 7⇥5 = 35 choices in all. • Choose an apple or an orange. There are 7 choices for an apple OR 8 choices for an orange: 7+8 = 15 choices in all. • Choose an apple and either an orange or a banana. There are 7 ⇥ (8 + 5) = 91 possible choices.
• Choose either an apple and an orange, or a banana. There are (7 ⇥ 8) + 5 = 61 possible choices.

Rule of Thumb

Generally, “AND” corresponds to multiplication and “OR” corresponds to addition.

From a math standpoint,

• “AND” corresponds to the Cartesian product of sets $A\times B=\{(a,b):a\in A\text{ and }b\in B\}$

• “OR” corresponds to the union of sets. $A\cup B=\{c:c\in A\text{ or }c\in B\}$