Number of permutations with every item out of place

Question

I would like to know how many ways you can arrange the first n numbers so that 1 isn’t the first, 2 isn’t the second etc.

Answer 1

These are known as derangements, and an easy way to enumerate them is via inclusion-exclusion. The number of permutations of $\{1,\ldots,n\}$ that fixes the points in $S \subseteq \{1,\ldots,n\}$ (and possibly more points) is $(n-|S|)!$, and we include-exclude over all subsets $S$, giving $$ \sum_{S \subseteq \{1,\ldots,n\}} (-1)^{|S|} (n-|S|)!. $$ Since the summand only varies with $|S|$, this is equal to \begin{align*} & \sum_{s=0}^n (-1)^s \binom{n}{s} (n-s)! \\ ={} & n!\sum_{s=0}^n \frac{(-1)^s}{s!}. \end{align*} There's many other formulas for this on the Wikipedia page.