
# 9: Some Important Recursively-Defined Sequences


• 9.1: Derangements
A derangement of a list of objects is a permutation of the objects, in which no object is left in its original position. A classic example of this is a situation in which you write letters to ten people, address envelopes to each of them, and then put them in the envelopes, but accidentally end up with none of the letters in the correct envelope.
• 9.2: Catalan Numbers
The Catalan numbers are a sequence that can be defined in a variety of ways, because they arise in a number of different circumstances. These numbers have something in common with Example 6.3.2, in which Shawna was building towers from lego. If we’d asked in how many different orders she could combine the blocks to build her tower, assuming that the final order for the blocks was decided in advance, we would have been asking for the Catalan number.
• 9.3: Bell Numbers and Exponential Generating Functions
Sometimes a recurrence relation involves factorials, or binomial coefficients. When this happens, it becomes difficult if not impossible to use ordinary generating functions to find an explicit formula for the nth term of the sequence. In some cases, a different kind of generating function, the exponential generating function, may succeed where an ordinary generating function fails.
• 9.4: Summary
This page contains the summary of the topics covered in Chapter 9.