Counting
Adding
Definition — Addition Principle
The sum \(a+b\) counts the total number of things in a collection formed by adding a collection of \(b\) things to a collection of \(a\) things.
For example, suppose we wish to count the number of two-digit positive integers that end in either \(0\) or \(1\). We can first count those that end in \(0\): there are \(9\) of them, one for each possible tens digit. There are also, similarly, \(9\) of them that end in \(1\). So there are \(9+9=18\) such numbers in total.
It is helpful to think about this as the union of two disjoint sets.
It is improtant that these sets are disjoint, otherwise we would be double-counting elements.
Consider counting people who like baseball or hockey when some people like both. If it is the case that our sets are not disjoint, we can account for the overlap by subtracting one of everything we double-counted.
The above is the principle of inclusion-exclusion for two sets, which is fun to visualize:
| \(=\) | \(+\) | \(-\) |
Exercise
In a group of \(30\) people, \(18\) like baseball and \(12\) like hockey. If \(5\) people like both, then how many people like at least one of baseball or hockey?
Let \(B\) be the set of people who like baseball. Similarly, \(H\) for those who like hockey. We are given: \[ |B| = 18 \] \[ |H| = 12 \] \[ |B \cap H| = 5 \] We can apply the principle of inclusion-exclusion to get: \[ |B \cup H| = |B| + |H| - |B \cap H| \] \[ |B \cup H| = 18 + 12 - 5 = 25 \]
Multiplying
Definition — Multiplication Principle
The product \(a \cdot b\) counts the number of ways to choose one thing in \(a\) ways followed by another in \(b\) ways.
For example, we want to count the number of ways we can flip a coin and roll a die. There are \(2\) possible outcomes from our coin, and \(6\) from our die. This gives us \(2 \cdot 6 = 12\) possible outcomes.
A tree is a useful way of visualizing the multiplication principle.
There are \(2\) outcomes from the coin flip, each with \(6\) subsequent flips. Notice that there are 12 vertices at the bottom of this tree. Rolling a \(5\), for example, could have happend two different ways: \[ \text{Heads} \to 5 \] \[ \text{Tails} \to 5 \]Permutation
A permutation is an ordered arrangment. Consider the letters \(\text{CAT}\). We can arrange these letters in six unique ways: \[\text{ACT}\] \[\text{ATC}\] \[\text{CAT}\] \[\text{CTA}\] \[\text{TAC}\] \[\text{TCA}\] which we can visualize as a tree:
There are three letters to choose for the first item in the arrangement. After the first letter is "used", there are two remaining letters to choose from. After the first two letters, there is one remaining letter. This leads to a number of permutations given by: \[3 \cdot 2 \cdot 1 = 6\]
Generally, given \(n\) unique items, we can arrange them in \(n \cdot(n-1) \cdot (n-2) \cdot ... \cdot 1 = n!\) ways.
Arranging \(n\) items, we may write \[P(n) = n! \] to represent the number of permutations for \(n\) items. If we are arranging \(r\) items from a collection of size \(n\), we have \[P(n,r) = \frac{n!}{(n-r)!} \] permutations.
Combination
A combination is a collection of items (order does not matter). All of the examples of \(\text{CAT}\) from above are the same collection: They all contain \(\text{C}\), \(\text{A}\), and \(\text{T}\).
From the collection of letters \(\text{CAT}\), we can choose combinations of size 0, 1, 2, or 3.
- There is \(1\) ways to choose \(0\) items:
- There are \(3\) ways to choose \(1\) item: \(\text{C}\), \(\text{A}\), and \(\text{T}\)
- There are \(3\) ways to choose \(2\) items: \(\text{AC}\), \(\text{AT}\), and \(\text{CT}\)
- There is \(1\) way to choose \(3\) items: \(\text{CAT}\)
Given \(n\) items, the number of combinations of \(r\) items is stated "\(n\) choose \(r\)" and given by: \[C(n,r) = {n \choose r} = \frac{n!}{r!(n-r)!} \] Note how similar this formula is to that for permutations. The only difference is the factor \(r!\text{,}\) the number of arrangements of \(r\), in the denominator. The number of combinations is the subset of permutations where we do not count equal sets of items, i.e., order does not matter, and dividing combinations by \(r!\) cancels out the extra equivalent sets.
Pascal's Triangle
One method of constructing Pascal's triangle is to form two diagonals of \(1\)s, then every number is the sum of the two numbers above it. This construction is exactly equivalent to the triangle of \(n \choose r\) where we count down \(n\) rows on the left and then over \(r\) spaces.
This seemingly simple triangle contains infinitely many patterns and is fundamental to combinatorics.