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 .
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
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
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
taking the (convoluting) of both sides gives that
Thus, recalling that in general if then . And thus,
1. Wilf, Herbert S. Generatingfunctionology. Boston: Academic, 1994. Print.
No comments yet.