Problem 1: A Combinatorial Walkthrough
In this lab, we will collaboratively work together through a difficult counting problem: counting the number of derangements of a sequence. A derangement of a sequence of elements is a permutation of the sequence where no element is placed in its original position. Below is an outline of our discussion.
To begin with, let’s first understand what a derangement is. Consider a group of \(n\) students in a writing class with papers to be peer-reviewed. A derangement of this group of people corresponds to an assignment of peer-reviewed papers to students such that no student receive their own paper.
Problem (A Small Example). First let’s explore a concrete example to gain a feel for what calculating derangements entails. Suppose we have a sequence \(S = a, b, c, d\). Here are the \(4! = 24\) permutations of this sequence for your reference:
\[\begin{gather} a,b,c,d \quad b,a,c,d \quad c,a,b,d \quad a,c,b,d \\ b,c,a,d \quad c,b,a,d \quad c,b,d,a \quad b,c,d,a \\ d,c,b,a \quad c,d,b,a \quad b,d,c,a \quad d,b,c,a \\ d,a,c,b \quad a,d,c,b \quad c,d,a,b \quad d,c,a,b \\ a,c,d,b \quad c,a,d,b \quad b,a,d,c \quad a,b,d,c \\ d,b,a,c \quad b,d,a,c \quad a,d,b,c \quad d,a,b,c \end{gather}\]
Use this list to identify the 9 derangements of \(S\).
Note that the number of derangements is closely related to the number of permutations. In this problem, we’re going to count the number of derangements twice: once using recursion to obtain a recurrence relation and another time using inclusion-exclusion to obtain an explicit formula. By our double counting principle, we will therefore know that the two formula are equal!
First let’s start with the recursive formula. Let’s denote the number of derangements of \(n\) elements as \(!n\). Note that this similar but not the same notation for factorial: \(n!\). Let’s use our real-life scenario of peer-reviewed papers to illustrate the choices each student can make in picking a paper to review.
First, let’s imagine a line of \(n\) students that will choose papers to peer review and consider the choices for the first student:
Problem (Choices For First Student). How many choices of papers are there for the first student to review among the \(n\) students given that they are not allowed to review their own paper?
Suppose that the first student has chosen student \(i\)’s paper (\(i \neq 1\)). Now let’s consider student \(i\)’s choices. Note that there’s an asymmetry in our choices here! While the first student chose paper \(i\), student \(i\) could not have chosen that paper since it is their own paper! Our successive choices now depend on whether student \(i\) chooses the first student’s paper.
Problem (Second Student: Chooses First Student’s Paper). Suppose that student \(i\) chooses the first student’s paper. In this situation, the first student and student \(i\) have mutually paired up. What is a recursive formula for the number of derangements of the rest of the students in this case?
Now consider the case where student \(i\) chooses a paper that is not the first person’s paper. Because the first student choose student \(i\)’s paper, there are now \(n - 1\) papers left.
Problem (Second Student: Chooses Another Paper) To count the number of possibilities, we note that while student \(i\)’s paper has been taken, student \(i\) can’t take the first student’s paper. If we put student \(i\) back in line, what is a recursive formula for the number of derangements for the remaining students.
Finally let’s put all this together into a final recursive formula for the number of derangements of a sequence of \(n\) elements.
Exercise (Putting It All Together).
Give a recursive formula for \(!n\), the number of derangements of \(n\) elements in terms of the three formula you derived above.
(Hint: Think about the quantities in terms of the numbers of ways the first student and student \(i\) can choose a paper.)
Now let’s come up with an explicit formula for the number of derangements using inclusion-exclusion. Our approach will start with \(n!\), the number of permutations and then subtract out permutations that are not derangements. We’ll do this in a systematic way: we’ll consider all the permutations where one element is in original position, then two elements, and then three, all the way up to \(n\).
Exercise (Increasing Non-Derangements). Consider the artificial sequence \(S = a, b, c, d\) from before. Define the set \(S_k\) to be the set of permutations of \(1, 2, 3, 4\) where element \(k\) is in its original position. List the contents of \(S_a\), \(S_b\), \(S_c\), and \(S_d\).
From this, derive an formula using set operations over \(S_a, \ldots S_d\) that describes the set of sequences with at least one element in its correct position.
Once you are done, you should note substantial overlap between the four sets. While we want to subtract all of these bad sequences from the total number of permutations \(n!\), we don’t want to “over-over-count” and subtract too much! The principle of inclusion-exclusion comes to the rescue here!
Exercise (A Concrete Formula). Give a formula for \(!4\) (since \(|S| = 4\)) in terms of the concrete size of the buckets you calculated above using the principle of inclusion-exclusion. Verify that your formula results in 9, the number of derangements of this particular set.
Once you have this concrete formula, what is left is coming up with a general formula for the size of an arbitrary bucket.
Exercise (An Abstract Formula). Consider a sequence of \(n\) elements. Give a formula for the number of permutations of the \(n\) elements where at least \(k\) elements are in their own positions. To do this, frame this as two choices:
- The number of ways to choose the \(k\) elements that are in their own positions.
- The number of ways to arrange the remaining elements of the sequence.
Finally, we can now come up with an overall count for the number of derangements and equate it to our recurrence. Note in developing this explicit formula, we have been counting the number of permutations with at least one element in its original position. In coming up with this final formula, note that the number of derangements is precisely the permutations where no such element is in its original position.
Exercise (The Punchline)
Put everything together to write down two formula for the number of derangements \(!n\) of \(n\) elements, a recursive formula and an explicit formula.