[Math] Derangement problem!

derangementsdiscrete mathematicsinclusion-exclusion

Is the solution of the problem, in how many ways can the digits $$0, 1, 2, 3, 4, 5, 6, 7, 8, 9$$

be arranged so that no even digit is in its original position, is $5!D_5$.

Where $D_n$ = $n! \left( 1-\dfrac{1}{1!}+\dfrac{1}{2!}+….+(-1)^n\dfrac{1}{n!} \right)$ and denotes derangement number.

Here we find expression of $D_n$ using inclusion exclusion principle.

$P_i$: $i^{th}$ object is at it's place.

$N(P_i)$ Number of object having property $P_i$

so we have to find $N(P_1P_2….P_n)$

Best Answer

This can be done with an inclusion-exclusion argument. There are $10!$ permutations altogether. For each set of $r$ even digits there are $(10-r)!$ permutations that leave that set of digits fixed (and possibly others as well), and there are $\binom5r$ sets of $r$ even digits. Thus, the number of permutations leaving no even digit fixed is

$$\sum_{r=0}^5(-1)^r\binom5r(10-r)!=10!-5\cdot9!+10\cdot8!-10\cdot7!+5\cdot6!-5!=2,170,680\;.$$

Added: In terms of the notation in this answer to your earlier question,

$$s_r=\binom5r(10-r)!\;,$$

so $$S(x)=\sum_{r=0}^5s_rx^r=\sum_{r=0}^5\binom5r(10-r)!x^r$$ and

$$E(x)=S(x-1)=\sum_{r=0}^5s_rx^r=\sum_{r=0}^5\binom5r(10-r)!(x-1)^r\;.$$

We want

$$e_0=E(0)=\sum_{r=0}^5\binom5r(10-r)!(-1)^r\;.$$