How many ways can $10$ digits be written down so that no even digit is in its original position

Question

If I have the numbers $0,1,2,3,4,5,6,7,8,9$ written down in that order, how many ways can the $10$ digits be written down so that no even digit is in its original position?

It would seem that I can move rewrite it starting from $0$ in $9!$ ways, and same with $2,4,6,8$, hence the answer is $5*9!=1814400$ is this correct?

Answer 1

Let $r(m,n)$ be the number of ways of placing $m$ objects, with $n$ of them constrained not to go in a particular position, where the $n$ particular positions are all different. Then we have $r(m,0)=m!$ (obviously), $r(m,1)=(m-1)(m-1)!$ (because we may place the constrained object in $m-1$ ways, and then the remainder unconstrained), and $$r(m,n)=(n-1)r(m-1,n-2)+(m-n)r(m-1,n-1)$$ We may place a constrained object in a place blocked to another object ($n-1$ possibilities), then the remainder in $r(m-1,n-2)$ ways, or we can place it in one of the places where any object may go and the remainder can then be placed in $r(m-1,n-1)$ ways. Calculating, we get $r(10,5)=2170680$.

Answer 2

Hint: Inclusion-exclusion principle. For a set of $k$ even digits, how many permutations are there where those digits are in their original positions?

Answer 3

As suggested by Robert Israel, here is a solution using Inclusion-Exclusion:

Let S be the set of all arrangements of the digits, and for $1\le i\le5$

let $A_i$ be the set of arrangements with the $i$th even digit in its original position.

Then $|{A_1}^{c}\cap \cdots \cap {A_5}^{c}|=|S|-\sum|A_i|+\sum|A_i\cap A_j|-\sum|A_i\cap A_j\cap A_k|+\cdots$

$=10!-\binom{5}{1}9!+\binom{5}{2}8!-\binom{5}{3}7!+\binom{5}{4}6!-\binom{5}{5}5!=2,170,680.$

Answer 4

We can also solve with this problem based on "Probability that exactly k of N people matched their hats" where "(hat,person)" is here "(position,digit)" although it takes some time to understand the calculation of this probability.

Then we can split into cases where exactly $5+k,0\le k\le 10-5$ digits including even digits are not in theirs original positions.

So the equation is $$ \sum_{k=0}^{m=N-5=10-5=5}N!\binom{m}{k}\frac{P_{N-k}}{P_{k}^N} $$ Here $k$ is the number of digits which are in theirs original positions , $N!$ is due to that we are to calculate permutation number instead of probability and $\binom{m}{k}$ is due to that we are caring about all possible non-matching cases instead of only one specific non-matching case.

After some calculation, the result is same as other answers.