3
$\begingroup$

Determine the number of permutations of $\{1,2,...,9\}$ in which at least one odd integer is in its natural position.

__ __ __ __ __ __ __ __ __ There are nine numbers to permute in the $9$ different position. There are $5$ odd numbers and $4$ even numbers.

This is my idea- I'm not sure if it's right though.

1) First I have to choose the odd number that will be in its natural position: $$\binom{5}{1}=5$$ 2) Next I have to derange the other odd numbers: $$D_{4}$$ 3) Lastly I have to permute the remaining numbers: $P(4,4)=24$

Total number of permutations: $$=5D_{4}P(4,4)$$

$\endgroup$
  • $\begingroup$ You are restricting yourself too much I think. In 2) why are you deranging the other odd numbers? You're allowed to have more than one odd number in its natural position. Moreover, an odd number is allowed to be placed into an even position. You might want to try counting the permutations with 1 in the first position, then the permutations with 1 not in the first position but 3 in the third position, etc. $\endgroup$ – Casteels Nov 17 '13 at 20:23
  • $\begingroup$ By the way, in a question like this you could check your method by trying it on a smaller example. E.g., for $\{1,2,3\}$ you can check by hand that there are exactly $3$ such permutations but applying your method would give $0$ (Since $D_1=0$.) $\endgroup$ – Casteels Nov 17 '13 at 20:35
5
$\begingroup$

The number of objects of $S$ which have at least one of the properties $P_1,P_2,...,P_m$ is given by $$|A_1\cup A_2\cup \cdots \cup A_m|=\sum|A_i|-\sum|A_i \cap A_j|+\sum|A_i\cap A_j\cap A_k|-\cdots +(-1)^{m+1}|A_1\cap A_2 \cap \cdots \cap A_m|.$$

If we select one of the odd integers to be in its natural position we can do so in ${5\choose 1}=5$ ways and then permute the remaining $8$ numbers in $8!$ ways for a total of $5\times 8!$ ways. If we select two odd integers to be in their natural positions we can do so in ${5\choose 2}=10$ ways and then permute the remaining $7$ integers in $7!$ ways for a total of $10\times 7!$ ways. If we select three odd integers to be in their natural positions we can do so in ${5\choose 3}=10$ ways and then permute the remaining $6$ integers in $6!$ ways for a total of $10\times 6!$ ways. If we select four odd integers to be in their natural position we can do so in ${5\choose 4}=5$ ways and permute the remaining $5$ integers in $5!$ ways for a total of $5\times 5!$ ways. If we select five odd integers to be in their natural position we can do so in ${5\choose 5}=1$ ways and then permute the remaining $4$ integers in $4!$ ways for a total of $4!$ ways. Thus there are $$5\times 8!-10\times 7!+10\times 6!-5\times 5! +4!=157824$$ ways for their to be at least one odd integer in its natural position.

$\endgroup$
  • $\begingroup$ Why do you subtract every second group? Does this "formulation" have a name? $\endgroup$ – user2340939 Aug 13 '17 at 19:04
3
$\begingroup$

You could also use rook polynomials to count the number of permutations where no odd integer is in its natural position. Setting $N=9$ and $R(x)=(1+x)^5$, the answer is $$\int_0^\infty x^N R(-1/x) \exp(-x)\,dx =205056.$$ Subtracting this from 9! gives 157824, the same as Ross's answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.