How can the total number of permutations equal the number of permutations with each element in it's original space

Question

I am going through the inclusion-exclusion proof for the number of derangements, and the first step is to take all permutations and subtract all arrangements in which each element (individually) appears in its original location: (https://artofproblemsolving.com/wiki/index.php?title=Derangement)

$n! - {n\choose1}{(n-1)!}$

This comes out to $0$.

I am having a hard time wrapping my head around the idea that the set of permutations in which each element (individually) appears in its original location can equal the total number of permutations which includes the set where none of the elements appear in the original location AND the ones in which each element (individually) appears in its original location.

I understand that doing the math proves it, but how does it make sense?

Answer 1

Your first term counts the total number of permutations. Your second counts the -sum- of the terms leaving each spot fixed, where the sum is taken over every possible spot. In this sum, certain permutations are counted more than once, which is why you get such a large number.

Answer 2

${n \choose 1}(n-1)!$ is not the number of permutations with one fixed element. It is the number of ways you can count permutations with at least on e fixed element.

To for example if $n$ is $4$ there are $4! = 24$ permutations. If you count the number of permutations where $1$ is fixed you get $6$ permutations:

$(2,3,4),(2,4,3),(3,4),(2,4),(2,3), i$. (Note: the first two have only 1 fixed; the next, $(3,4)$ has both $1$ and $2$ fixed and $i$ has all fixed).

If you count the number permutations where $2$ is fixed you get $6$ permutations:

$(1,3,4),(1,4,3), (3,4), (1,4),(1,3), i$ but note $(3,4)$ and $i$ were all ready counted. So you have only counted $10$ distinct permutations, but $12$ including repetitions.

If you count the number of permutations where $3$ is fixed you get $6$ permutations:

$(1,2,4),(1,4,2),(2,4),(1,4),(1,2),i$. But only $3$ of these are new. We've counted $18$ but only $13$ of them are distinct.

If we count the permutations where $4$ is fixed we get:

$(1,2,3),(1,3,2),(3,4),(1,3),(2,3),i$ but only two of these are new. So we've counted $24$ but have only actually counted $15$ new ones. We counted $i$ four times instead of just one, so our count is $3$ too high. We counted each if $(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)$ twice so our count is $9$ too high.

We counted $24$ when the actual count is $15$. We overcounted.

So we must subtract those with at least two fixed points because those were counted at least two times:

If we count those with $1,2$ fixed there are $(3,4),i$ that's two.

If we count those with $1,3$ fixed there are $(2,4),i$ that's two.

If we count those with $1,4$ fixed there are $(2,3),i$ that's two.

If we count those with $2,3$ fixed there are $(1,4),i$ that's two.

If we count those with $2,4$ fixed there are $(1,3),i$ that's two.

If we count those with $3,4$ fixed there are $(1,2),i$ that's two.

So subtracting those $12$ our count goes back down to $24 - 12 = 12$. That's three too low. We have adjusted so that we have only counted each $(m,n)$ once instead of twice, but we have over adjusted how many times we have counted $i$. We counted it $4$ times but we subtracted it $6$ times for a total of $-2$ times. It should be $1$ so we are too low by $3$.

So we must add back the permutations with at least $3$ fixed points (because they were over subtracted multiple times when we subtracted those with at least $2$ fixed points).

Those with $1,2,3$ fixed are $i$. That's $1$.

Those with $1,2,4$ fixed are $i$. That's $1$.

Those with $1,3,4$ fixed are $i$. That's $1$.

Those with $2,3, 4$ fixed are $i$. That's $1$.

So we add those back and we get $12 + 4 = 16$ which is $1$ too many. This because we've counted $i$, $4$ times as a permutation with at least $1$ fixed point, we subtracted it $6$ times as a permutation with at least $2$ fixed point. We readded it $4$ times as a permutation with at least $3$ fixed points. That's counting it a total of $4-6+4 = 2$ which is $1$ too many.

We must now subtract the permutations with $4$ fixed points as they've been over subtracted when we subtracted those with $3$ fixed points.

$i$ is the only one with $4$ fixed points. So $16 - 1 = 15$. We have now counted each permutation with at least one fixed point exactly once.