Arranging numbers $1,2,3,\dots,n$ In how many ways numbers $1,2,3,\dots,n$ can be arranged in a row such that $1$ cannot be on the first place, $2$ cannot be on the second place, $3$ cannot be on the third place, etc?
I tried this way: on the first place can be $n-1$ numbers. Now, I used one number, so there are $n-1$ numbers left. If on the first place is $2$, then on second place can be again $n-1$ numbers, else there can be $n-2$ numbers and so on. It take a very long time to find all cases for all places if $n$ is a big number. What is the easiest way to solve this?
 A: There is an inclusion-exclusion formula for counting derangements of $n$ elements:
$$n! \sum_{i=0}^{n} \frac{(-1)^{i}}{i!}$$
So we start by permuting the $n$ elements, which can be done in $n!$ ways. Then we count the number of ways that element $i$ goes to slot $i$. So we fix a single element at its slot and permute the remaining elements in $(n-1)!$ ways. There are $n$ such elements we can fix (ie., fix $1$ then permute the other elements, then fix $2$ and permute the other $n-1$ elements, etc.), so we subtract out $n * (n-1)! = n!$ from the original quantity.
However, we have overcounted, as we could have $1 \mapsto 1, 2 \mapsto 2$ (for example) in our permutations fixing a single element. So we have to add back in quantities where $2$ elements are fixed. So we fix those two elements and permute the remaining $n-2$ elements. Notice that $\frac{n!}{2!}$ counts the permutations of $n-2$ elements. 
We continue this inclusion-exclusion process, which gives us the above summation.
A: Let's find the set $A$ of all the configurations that are not acceptable. If we denote the set of all permutations with $i$ at $i^{th}$ place by $A_i$, then $A = \cup_{i = 1} ^n A_i$. Using the inclusion-exclusion principle you can find that 
$$|A| = \binom{n}{1}(n-1)! - \binom{n}{2}(n-2)! + \binom{n}{3}(n-3)! - \dots + (-1)^{n+1}\binom {n}{n}0! = \sum_{i = 1}^{n} (-1)^{i+1}\binom{n}{i}(n-i)!$$
And your final answer should be
$$n! - |A| = \sum_{i = 2}^n (-1)^i \binom{n}{i} (n-i)!$$
