Section 9.1 Combinatorics
Combinatorics is the mathematical science of counting. You are likely thinking, to the dismay of those of us who specialized in this branch of mathematics, “Counting is easy. Why is it its own branch of mathematics?”
Counting is easy when the set of objects is finite and small. You could tell me that the number of subsets of \(\{1,2,3\}\) is 8 by simply listing them all out. This process of counting by enumeration is often useful to spot broad patterns, but you can quickly see it must be augmented when we ask: how many subsets are there of the set \(\{1,2,\ldots, n\}\text{?}\)
Very well, you now agree that counting can be difficult, but maybe you don't believe it's of any practical interest beyond the problems that can be solved via enumeration. Therefore it is one of the goals of this chapter to convince you that counting techniques are useful in both the applied and theoretical senses.