There are n people, which all write their name on 1 piece of paper, eventually leading to n papers with n different names.
What is the amount of ways that nobody pulls his own name out of the pile of tickets?
Well, I understand the recurrence relation: D,(n) = !n = n * (D,(n-1) + D,(n-2)) with ,(n-i) an index.
I also understand the fact that !n = n! - {number of ways in which at least 1 person pulls his own name}.
The next step is difficult: How do I mathematically express the number of ways in which at least 1 person pulls his own name?
The first few steps to derive this formula I did understand:
!n = n! - ${n\choose 1}$ * (n-1)! + ...
Here I understand the fact that we substracted 2 times the amount of ways that 2 people pull their own name. So we add ${n\choose 2}$ * (n-2)!, so that we eventually extracted 1 time the amount of ways to let 2 people pull their names. (If my explanation is correct, person a could be part of ${n\choose 1}$ and person b of (n-1)! such that 2 people pull their own names, but also the reverse is true, so that is why we substracted that stuff 2 times).
Now we have: !n = n! - ${n\choose 1}$ * (n-1)! + ${n\choose 2}$ * (n-2)! - ...
Well. Now it seems we did not substract the number of ways 3 people pull their names, since you substracted it 1 times at ${n\choose 1}$ * (n-1)! and added it again at ${n\choose 2}$ * (n-2)!
Now we have: !n = n! - ${n\choose 1}$ * (n-1)! + ${n\choose 2}$ * (n-2)! - ${n\choose 3}$ * (n-3)! + ...
Well, this is where I stop understanding it. The next step would be to add ${n\choose 4}$ * (n-4)!, which means that we substracted the amount of ways that 4 people pull their own name, 1 time too much. But why is that? Lets take 4 persons: A, B, C and D.
${n\choose 1}$ * (n-1)! : There are 4 ways to put these 4 persons in 2 groups of 1 having 1 spot and the other one having 3 spots. We substracted these ways.
${n\choose 2}$ * (n-2)!: There are 6 ways to put 4 person in 2 groups of 2 spots. We added these ways.
${n\choose 3}$ * (n-3)!: There are 4 ways to put these 4 persons in 2 groups of 1 having 1 spot and the other one having 3 spots. We substracted these ways.
So that means we substracted 8 times and added 6 time, which means we have to add 1 more time. That is why we add the factor: ${n\choose 4}$ * (n-4)! and get:
!n = n! - ${n\choose 1}$ * (n-1)! + ${n\choose 2}$ * (n-2)! - ${n\choose 3}$ * (n-3)! + ${n\choose 4}$ * (n-4)! - ...
With this kind of explanation you continue untill the end at which point you can make a summation of it.
Is my explanation correct?