CSC 208-01 (Spring 2023)

Lab: Combinatorial Walkthrough

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.

Problem 2: Brute-force

Many algorithms in computing can be classified as combinatorial algorithms. To develop a combinatorial problem for a problem, we must cast that problem as a search for an object of interest from among a finite set of possibilities. Thus, we can think of the algorithm as a search procedure that moves through the space of possibilities in as efficient of a manner as possible.

If there are a finite number of possibilities, then one simple class of combinatorial algorithms are brute-force algorithms where we ignore efficiency and simply try all possible possibilities in some systematic fashion. While seemingly inelegant, sometimes brute-force solutions are the more pragmatic approach—and sometimes even more efficient in real-world settings! However, in many other cases, it is precisely avoiding brute-force search that is the purpose of the algorithm we develop for a task at hand.

Each of the following situations describes a problem that can be recast as a combinatorial algorithm. For each situation:

Note that some of the situations described below come from our previous lab on graph problems

  1. Finding the smallest element among \(n\) elements of an array.
  2. Finding a path between points \(u\) and \(v\) in a simple graph \(G = (V, E)\).
  3. Determining whether the \(n\) elements of an array are in sorted order.
  4. Given a bipartite graph \(G = (V, E)\) with \(V_1, V_2 \subseteq V\) forming a partition of \(V\) and a matching \(M \subseteq E\), determining whether \(M\) is a perfect matching.
  5. Given a bipartite graph \(G = (V, E)\) with \(V_1, V_2 \subseteq V\) forming a partition of \(V\) and a matching \(M \subseteq E\), determine whether \(G\) has a perfect matching.
  6. Given a simple \(G = (V, E)\), determine whether \(G\) has a \(k\)-coloring.