Suppose you pick a random order of consecutive numbers from 1 to $n$.  

The order for a series of $n$ numbers would then be:
$$
x\_1, x\_2, ... x\_{n-1} , x\_n
$$


The amount of unique combinations is of course $n!$.  

e.g. for $n=3$ there are $3!$ (or 6) unique combinations, see table below.


We are interested in the combinations where $x\_i \neq i$.





| C | 1 | 2 | 3 |
| --- | --- | --- | --- |
| 1 | 1 | 2 | 3 |
| 2 | 1 | 3 | 2 |
| 3 | 2 | 1 | 3 |
| 4 | 2 | 3 | 1 |
| 5 | 3 | 1 | 2 |
| 6 | 3 | 2 | 1 |




> 
> Note: The 'wrong' combinations have been striked.
> 
> 
> 


We see that there are 2 valid combinations.


We can now continue this list until $n$.  

Eg. for $n=4$, there are 9 valid combinations and so on.





| Magnitude | Total Combinations | Valid Combinations |
| --- | --- | --- |
| 1 | 1 | **0** |
| 2 | 1 | **1** |
| 3 | 6 | **2** |
| 4 | 24 | **9** |
| 5 | 120 | **44** |
| ... | ... | ... |
| $n$ | $n!$ |  |



Obviously we would like a general solution for length $n$.  

Who can help to calculate this?  

Thank you very much.



How many unique orders of length n are there where the index number is different from the number itself?
As @GordonRoyle pointed out: this is a description of derangements...


For a series $n$, the number of derangements are
$$
n!\sum\limits\_{k=0}^{n}\frac{(-1)^k}{k!}
$$


As @JukkaKohonen pointed out, there is a nice entry in the [OEIS database](http://oeis.org/A000166).


Thanks all!


