Season 2 Episode 11

OOMC. Season 2 Episode 11. Everything Wrong.

In this episode, James gets everything wrong. On purpose maybe? We look at the number of ways to rearrange things without getting any in their original place, and there's an extension to sets of two with an incredible answer.

 

Further Reading

Inclusion-Exclusion principle

During the add break, we talked about the inclusion-exclusion principle, which gives you a formula for counting the number of things that meet one-or-more of some constraints, if you’re given information about exactly how many things satisfy each subset of those constraints. Let’s state the formula first, and then talk about why it works. I’ll state it first for four sets or constraints, and then for $n$ sets. The notation below uses $\cup$ to mean “or” and uses $\cap$ to mean “and”. Vertical bars around a set mean the size of that set (the number of things in it). Let’s go!

(Inclusion-Exclusion for four sets) Given sets $A$, $B$, $C$, $D$, we have
\begin{align*}
|A \cup B \cup C \cup D| =& |A|+|B|+|C|+|D|\\
&- |A\cap B|-|A\cap C|-|A\cap D|-|B\cap C|-|B\cap D| -|C \cap D|\\
&+|A\cap B \cap C|+|A\cap B \cap D|+|A\cap C \cap D|+|B\cap C \cap D|\\
&- |A\cap B \cap C \cap D|
\end{align*}

Note how this uses information about all the subsets of constraints, with plus or minus signs depending on how many constraints are in that term. Let’s look at the version with $n$ sets. The notation is going to get trickier here, because I need to explain what to do in general.

(Inclusion-Exclusion for $n$ sets) Given sets $A_1$, $A_2$, $A_3$, $\dots$, $A_n$, we have
\begin{equation*}
|A_1\cup A_2 \cup \dots \cup A_n|= \sum_{k=1}^n (-1)^{k+1} \sum _{1\leq i_1<i_2<\dots i_k\leq n} |A_{i_1}\cap A_{i_2}\cap A_{i_3}\cap \dots \cap A_{i_k}|
\end{equation*}

I’ve included this because it’s possibly one of the most complicated sums you’ve ever seen, but also because I think that you stand a good chance of understanding what it all means by comparing it with the statement with four sets above. That’s not the same thing as understanding why it’s true of course, which we’ll talk about in a moment, but first let’s check that we understand what this big mess of notation means.

On the inside sum there are lots of variables – the instruction $1\leq i_1<i_2<\dots<i_k\leq n$ means that we’re supposed to sum over all possible combinations of values of $i_1$ and $i_2$ up to $i_k$ that satisfy those inequalities. These numbers $i_1$, $i_2$, $\dots$, $i_k$ are going to be used inside the sum to describe which sets we’re using for this term out of $A_1$, $A_2$, \dots, $A_n$. So for a given $k$, this sum includes all the possible groups of $k$ of the sets, all $\cap$ together. The outside sum for $k$ from $1$ to $n$ is just increasing the number of sets in the term from one set to all the sets, and it’s keeping track of those alternating plus and minus signs.

So why does this work? We need to check that every item is counted once, no matter how many of the constraints it satisfies (so long as it satisfies at least one constraint).

Consider an item that satisfies $i$ of the constraints with $i\geq 1$ and which does not satisfy the other $n-i$. Then when we count each of the subsets-of-size one, it’s in $i$ of those. We subtract the subsets of size two, and it’s in $\binom{i}{2}$ of those (where $\binom{n}{r}$ is the binomial coefficient $n!/r!(n-r)!$). Then we add $\binom{i}{3}$ times, subtract $\binom{i}{4}$ times, down to $(-1)^{i-1} \binom{i}{i}$. Overall then, we have a sum for how many times this item has been counted, and it’s 
\begin{equation*}
\binom{i}{1}-\binom{i}{2}+\binom{i}{3}-\dots + (-1)^{i-1}\binom{i}{i}=\binom{i}{0}-(1-1)^i=1
\end{equation*}

Therefore, this item is counted exactly once, which is what we wanted!

There’s a little bit more about Inclusion-Exclusion on Wikipedia and on Brilliant and on Art of Problem Solving.

 

Derangements

We can use inclusion-exclusion to get to a nice formula for the number of derangements. Consider the subsets A= {first item is in the right place}, B={second item is in the right place} … and so on.

Now we want to know the number of permutations (n!) minus those that satisfy one-or-more of those constraints. We know that if $i$ of those constraints are satisfied, then $i$ items are in the right places, and anything could be true for the others – so there are $(n-i)!$ arrangements of the other items.

There are $n$ subsets-of-size 1, and each of them contains $(n-1)!$ permutations (with some overlaps, which the Inclusion-Exclusion Principle lets us deal with). Then there are $\binom{n}{2}$ subsets of size 2, and $(n-2)!$ permutations that satisfy those constraints, and so on.

So overall we have $$n! – \sum_{i=1}^n (-1)^{i+1}\binom{n}{r}(n-i)!$$ derangements, which is
$$n!\left(1-\sum_{i=1}^n \frac{(-1)^{i+1}}{i!}\right)$$

 

Exponentials

At some point in A-level Further Maths (or equivalent), I think you learn that
$$
e^x=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+\dots \quad \text{for any real $x$}
$$

That’s got some nice consequences if we plug in particular values of $x$, like $1$ or $-1$;
\begin{align*}
e=& 1+1+\frac{1}{2}+\frac{1}{6}+\frac{1}{24}+\dots\\
e^{-1}=& 1-1+\frac{1}{2}-\frac{1}{6}+\frac{1}{24}-\dots\\
\end{align*}

In the livestream, we briefly mentioned that for large $n$, the proportion of permutations which are derangements is about $e^{-1}$. We can now see why; the sum we worked out above is $n!$ times the sum of the first $n$ terms of the expansion for $e^{-1}$ above. So when $n$ is large, the number of derangements is close to $n!/e$.

 

Curve sketching

Today I’d like you to sketch
$$y=e^{-x}(x^2-4x+2)$$
(make sure to check whether this is negative or positive!)

 

If you want to get in touch with us about any of the mathematics in the video or the further reading, feel free to email us on oomc [at] maths.ox.ac.uk.

Please contact us with feedback and comments about this page. Last updated on 29 Apr 2022 12:07.