0

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?

Salim
  • 41
  • 1
    It is a very long and tedious way of explaining something which should already be well understood. Just cite the Inclusion-Exclusion Principle and be done with it rather than taking ten lines to say the same thing in an imprecise manner. – JMoravitz Jun 02 '18 at 18:37
  • For each $i$, let $X_i$ be the set of permutations where $i$ is fixed. Let $[n]={1,2,3,\dots,n}$. We have by inclusion-exclusion that $|\bigcup\limits_{i=1}^n X_i| = \sum\limits_{\emptyset\subsetneq A\subseteq [n]} (-1)^{|A|+1}|\bigcap\limits_{i\in A}X_i|$ which by symmetry and noting that $|X_1\cap X_2\cap\dots\cap X_k|=(n-k)!$ expands as you showed above as $\binom{n}{1}(n-1)!-\binom{n}{2}(n-2)!+\binom{n}{3}(n-3)!-\dots = \sum\limits_{i=1}^n (-1)^{i+1}\binom{n}{i}(n-i)!$ – JMoravitz Jun 02 '18 at 18:43
  • I saw similar explanations like these, but I lack the knowledge to understand them, since we did not have these theorems in our courses. Might be in the future though. – Salim Jun 02 '18 at 18:48
  • You have seen $|A\cup B|=|A|+|B|-|A\cap B|$ I'd imagine, yes? Going from that to $|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$ is just a repeated application of the first noting that $|A\cup B\cup C|=|A\cup (B\cup C)|$. Continuing further to the generalized statement $|\bigcup\limits_{i=1}^n X_i| = \sum\limits_{\emptyset\subsetneq A\subseteq [n]} (-1)^{|A|+1}|\bigcap\limits_{i\in A}X_i|$ is again just repeated applications of the first which can be proven via induction. The generalized statement is far too useful to ignore the existence of and should be learned – JMoravitz Jun 02 '18 at 18:54
  • In case the notation is what is throwing you off, putting the above into words, $|X_1\cup X_2\cup X_3\cup\dots\cup X_n|$ is the union of $n$ sets, which can be broken up via inclusion-exclusion as the sum of the cardinalities of each individual set, minus the cardinalities of each intersection of two sets, plus the cardinalities of each intersection of three sets, minus the cardinalities of each intersection of four sets, so on and so fourth, alternating between adding and subtracting, going through each possible intersection of the sets, up until having add/subtracted the intersection of all. – JMoravitz Jun 02 '18 at 18:58
  • I see. We had that kind of stuff yes. Thanks I understand it now. This way costs way less time than mine. – Salim Jun 02 '18 at 22:44

0 Answers0