Problem

How many ways are there to arrange a set of $n$ distinct elements such that no element is in it’s original position?

Solution

The way to arrange the set without consideration for position is:

n!

Now accounting for the values that have one element in it’s original position:

n! - (1 n) (n - 1)!

However, we subtracted arrangements with two elements in their original position twice:

n! - (1 n) (n - 1)! + (2 n) (n - 2)!

Now, we readded arrangements with three elements in their original position:

n! - (1 n) (n - 1)! + (2 n) (n - 2)! - (3 n) (n - 3)!

This pattern continues by PIE, giving us:

n! - (1 n) (n - 1)! + (2 n) (n - 2)! - (3 n) (n - 3)! ... + (- 1)^{n} (n n) (n - n)!

Since $(k n) (n - k)! = \frac{n !}{k !}$ , we can rewrite as:

\frac{n !}{0 !} - \frac{n !}{1 !} + \frac{n !}{2 !} ... + (- 1)^{n} \frac{n !}{n !} = k = 0 \sum n (- 1)^{k} \frac{n !}{k !} = n! k = 0 \sum n \frac{( - 1 ) ^{k}}{k !}