## Number of Derangements

**Point of post: **In this post we will do a simple, but classic counting exercise to figure out how many derangements there are on .

*Motivation*

A *derangement *of the set is an element of (click the symbol if you’re unsure what it means) such that for all . In this post we will prove, in two ways, how many derangements there are of objects. This is interesting combinatorially as it answers the question “Suppose that a class of students takes a quiz and the teacher collects them. How many ways can the teacher redistribute the quizzes for peer grading, with the obvious proviso that no student get’s his/her own paper?” So, with this in mind, let’s begin.

*Remark: *I shall use and interchangeably for cardinality throughout this post.

**Theorem: ***Let be the set of derangements of . Then, *

**Proof: **Clearly we have that

and thus

where , and thus

Thus, by the inclusion-exclusion principle it follows that

where . Note though that

and evidently this is equipotent to and thus

but, this was true for all . Thus,

but, clearly since it follows that

as desired.

The second method uses techinques outlined in Herbert Wilf’s *Generatingfunctionology*

**Proof: **Let and let $G(x)$ be the generating function for . Note that evidently the number of with exactly fixed points is evidently from where it easily follows that

so that

taking the (convoluting) of both sides gives that

so that

Thus, recalling that in general if then . And thus,

as required.

**References:**

1. Wilf, Herbert S. *Generatingfunctionology*. Boston: Academic, 1994. Print.

No comments yet.

## Leave a Reply