Strangely enough, a couple of days after I made my last post on a way to prove the derangements formula that I had never seen before, I came across another new (to me) way to prove the derangements formula in an article  by P. Mark Kayll in Mathematics Magazine from earlier this year. It involves an an integral representation for the number of derangements on elements:
(Kayll gives this as a special case of a more general result that says that the number of permutations with a specified set of fixed points can be represented by , where is the complement of in the complete bipartite graph on elements, and is the associated rook polynomial for .)
I’m going to prove this by showing that the integral representation satisfies the derangements recurrence . Let .
Proving the integral formula for :
Integration by parts yields
which gives us a recurrence for . Applying this recurrence again with yields
Since and , the integral representation is established.
Proving the derangements formula from the integral representation:
(I added this argument to my answer to “I have a problem understanding the proof of Rencontres numbers.”)
- P. Mark Kayll, “Integrals Don’t Have Anything to Do with Discrete Math, Do They?” Mathematics Magazine 84(2): 2011, 108-119.