Derangement problem!

6k Views Asked by At

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)$

2

There are 2 best solutions below

0
On BEST ANSWER

We count the permutations in which no even number ends up in its original position (good permutations) by dividing into cases.

There are $5$ odd numbers. Perhaps $0$ end up their original positions, or perhaps exactly $1$, or perhaps exactly $2$, and so on up to $5$.

There are $D_{10}$ good permutations in which $0$ odds end up in their original position.

For good permutations with exactly $1$ odd in its original position, the odd can be chosen in $\binom{5}{1}$ ways. Everybody else must move, giving a total of $\binom{5}{1}D_9$.

For exactly $2$ odd in their original positions, the odds can be chosen in $\binom{5}{2}$ ways. Everybody else must move, giving a total of $\binom{5}{2}D_8$.

And so on (three more cases). The total count is $$\sum_{k=0}^5 \binom{5}{k}D_{10-k}.$$

4
On

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\;.$$