Here’s a summary of what we’ve learned:
- If there are p ways to do one thing, and q ways to do another independent thing, then there are p * q ways to do both things.
- If there are p ways to do one thing and, distinct from them, q ways to do another thing, then the number of ways to do p or q is p + q.
- When m different events can occur in n independent ways, there are mn possible ways for all of them to occur.
- We can compute the number of elements that satisfy at least one of several properties. For two sets A and B, |A ∪ B| = |A| + |B| − |A ⋂ B|
- One interesting pattern in Pascal’s triangle is that the sum of entries in row n equals 2n
- Another interesting pattern in Pascal’s triangle is that when you descend diagonally at first, then slant to form the shape of a hockey stick, the number in the slanted portion is the sum of the numbers that descended diagonally (hockey stick pattern)
- Counting theory has many applications in computer science. It can be applied to count bitstrings, or to find valid passwords based on password rules.