DeArrangement theory

Let's say there are 'n' people: P1, P2 ... Pn.
And there are 'n' chairs: C1,C2....Cn.
And we have to seat the people so that none of them gets the chair with same number.

For e.g. for 2 people, there is only 1 way:
P2,P1

For 3 people there are 2 ways:
P2,P3,P1
P3,P1,P2

And so on..

These are called DeArrangements.

For n  = 1 it's D1, for n = 2 it's D2 and in general it's Dn.

How to compute Dn?
There is a recursive formula:
Dn = (n-1)(Dn-1 + Dn-2), D0 = 1, D1 = 0
Using this let's compute:
D2 = (2-1)(D0 + D1) = 1.1 = 1
D3 = (3-1)(D1 + D2) = 2.(0+1) = 2
D4 = 3.(2+1) = 9
D5 = 4.(9+2) = 44
......

There is non recursive formula also:
Dn = (n!){1 -1/1! + 1/2! - 1/3! ....(-1)^n.1/n!}
D1 = 1!(1-1) = 0
D2 = 2!(0+1/2) = 1
D3 = 3!(1/2-1/6) = 2
....

How do we derive the recursive formula?
Let's P1 receives a chair Ci where i != 1.
Now the person Pi can receive a chair in 2 ways:
1. Pi receives C1, i.e. P1 and Pi exchange their chairs. Now the remaining (n-2) people have to de-arrange (n-2) chairs among themselves = Dn-2.
2. Pi does not receive C1. Now we can rename Pi as P1(since P1 is already gone), and compute Dn-1 for remaining people.
So when there P1 receives Ci, there are Dn-1 + Dn-2 ways to distribute chairs.
Now P1 can receive chair of n-1 people.
So there are (n-1)*(Dn-1 + Dn-2) ways.