Proof, derangements, permutations

Question

$n! = \binom{n}0 D_n + \binom{n}1 D_{n-1} + \binom{n}2 D_{n-2} + ….. +\binom{n}n D_0 $

$(D_0 = 1)$

Attempt:

The number of permutations of n distinct objects is n factorial.

$\binom{n}0 D_n $ means all the objects aren't in their natural place.

$\binom{n}1 D_{n-1} $ means we fix one object ( choose 1 from n ) then the rest deranged

. . .

$\binom{n}n D_0 $ means all the objects are in place

Answer 1

Since you ask how to write it up as a complete proof, here is one way to do so; it is indeed a combinatorial argument.

Let $P_n$ be the set of permutations of $[n]=\{1,2,\ldots,n\}$, and for each $k\in[n]$ let $P_n(k)=\{\pi\in P_n:\pi\text{ has exactly }k\text{ fixed points}\}$; clearly $|P_n|=\sum_{k=0}^n|P_n(k)|$, and we know that $|P_n|=n!$.

Now consider $P_n(k)$ for some $k\in[n]$. Each $\pi\in P_n(k)$ has exactly $k$ fixed points and is a derangement of the remaining $n-k$ elements of $[n]$. Moreover, given any $k$-element subset $F$ of $[n]$ and any derangement of $[n]\setminus F$, there is clearly a $\pi\in P_n(k)$ that has $F$ as its set of fixed points and agrees with the derangement on $[n]\setminus F$. Thus, there are $\binom{n}k$ possible $k$-element sets of fixed points, and there are $D_{n-k}$ derangements of the remaining $n-k$ elements of $[n]$, and $|P_n(k)|=\binom{n}kD_{n-k}$. Thus, $$n!=|P_n|=\sum_{k=0}^n|P_n(k)|=\sum_{k=0}^n\binom{n}kD_{n-k}\;,$$ as desired.

Answer 2

You're on the right track. $n!$ is the number of ways you can arrange $n$ objects. Fix an arrangement first. We will say objects are correctly ordered in they are placed as object 1 in place 1, object 2 in place 2, and so on.

Now the total number of arrangements can be divided into the following mutually exclusive arrangements.

Step 1. Choose the $k$ objects you want to place correctly. You have $n\choose k$ options.

Step 2. Place them in their positions.

Step 3. Place others in wrong positions.