# 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:

- Describe what the finite set of possibilities are and the object of interest you are looking for.
- Give a combinatorial description of the number of possibilities that a brute force algorithm would search through.
- From the combinatorial description, give the (temporal) computational complexity in Big-O notation of the associated brute force algorithm for that problem.

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

- Finding the smallest element among \(n\) elements of an array.
- Finding a path between points \(u\) and \(v\) in a simple graph \(G = (V, E)\).
- Determining whether the \(n\) elements of an array are in sorted order.
- 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. - 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. - Given a simple \(G = (V, E)\), determine whether \(G\) has a \(k\)-coloring.