proof of recurrences for derangement numbers
The exponential generating function for the derangement numbers is
To derive the formulas algebraically, start with (2):
and (2) follows. To derive (1), use (2) twice:
Combinatorially, we can see (1) as follows. Write for . Let be any derangement of , i.e. a permutation containing no -cycles. Adding before any of the elements of produces a derangement of . For fixed , these are clearly all distinct, since has a different successor in each case; for distinct , these are equally obviously distinct. Thus each derangement of corresponds to exactly derangements of . Note also that since had no -cycles that is not a member of a transposition (a -cycle).
Now let be a derangement of any elements chosen from . There are clearly such derangements. If the omitted element in is , then adding the transposition to produces a derangement of , and all such derangements again are distinct from one another. Finally, since in this case is a member of a transposition, these derangements are distinct from those in the first group. This proves (1).
|Title||proof of recurrences for derangement numbers|
|Date of creation||2013-03-22 19:05:56|
|Last modified on||2013-03-22 19:05:56|
|Last modified by||rm50 (10146)|