myNBC Home

Counting the number of ways that certain patterns can be formed is the central problem of enumerative combinatorics. Two examples of this type of problem are counting combinations and counting permutations (as discussed in the previous section). More generally, given an infinite collection of finite sets {Si} indexed by the natural numbers, enumerative combinatorics seeks to describe a counting function which counts the number of objects in Sn for each n. Although counting the number of elements in a set is a rather broad mathematical problem, many of the problems that arise in applications have a relatively simple combinatorial description.

The simplest such functions are closed formulas, which can be expressed as a composition of elementary functions such as factorials, powers, and so on. For instance, as noted above, the number of different possible orderings of a deck of n cards is f(n) = n!. Often, no closed form is initially available. In these cases, we frequently first derive a recurrence relation, then solve the recurrence to arrive at the desired closed form. We demonstrate this method below.

For example, let f(n) be the number of distinct subsets of the set $S(n)=\{1,2,3, \ldots ,n \}$ that do not contain two consecutive integers. When n = 4, we have the sets {}, {1}, {2}, {3}, {4}, {1,3}, {1,4}, {2,4}, so f(4) = 8. We count the desired subsets of $S (n)$ by separately counting those subsets that contain element $n$ and those that do not. If a subset contains $n$ , then it does not contain element $n$