0
$\begingroup$

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

I know this question has been asked before. But nobody really had a fulfilling answer as to why we use inclusion and exclusion.

Here is my understanding

Now there are $5$ odd integers in $\{1,2,....,9 \}$ and we can select one of those $5$ odd integers in ${5 \choose 1}$ ways and we can then permute the other $8$ integers and so we have${5 \choose 1} 8!$

But the problem is that ${5 \choose 1} 8!$ include permutations that have $2,3,4,5$ odd integers in their natural position right ?

So why don't we just stop here and call it an answer !!

Then we go to select two odd integers ${5 \choose 2} 7!$ but this also have permutations where there are $3,4,5$ odd integers are in their natural position.

Now there is an overlap between ${5 \choose 1} 8!$ and ${5 \choose 2} 7!$ so that's why we use inclusion and exclusion.

So we can't just add, because we will be over counting permutations that have $2,3,4,5$ odd integers in their natural position right !!

That's why the final answer is $${5 \choose 1} 8! - {5 \choose 2} 7! + {5 \choose 3} 6! - {5 \choose 4} 5! + {5 \choose 5} 4!$$

But my question still remains , why is it not just ${5 \choose 1} 8!$ because here we select one of the odd integers and permute the others , but by permuting the others we still have arrangements where there are $2,3,4,5$ odd integers in their natural position ?

And also don't we have to subtract this answer from $9!$ to be become

$$9! - \big({5 \choose 1} 8! - {5 \choose 2} 7! + {5 \choose 3} 6! - {5 \choose 4} 5! + {5 \choose 5} 4! \big)$$

$\endgroup$
5
$\begingroup$

If I'm understanding your question:

Using your method, let's say one of the arrangements is when the odd number in its correct position is $1$ and the rest of the numbers are arranged in numerical order $${1,2,3,4,5,6,7,8,9}$$ Now, your method also spits out the case where $9$ is in its correct position and the other numbers are arranged in numerical order. $${1,2,3,4,5,6,7,8,9}$$ This is just one example of how your method will over count many arrangements because there will be multiple ways to arrive at that arrangement.

Edited to add:Consider a simpler case of the set $\{1,2,3\}$. So, if we were to use ${2\choose1}2!$ to get the answer we would get 4 solutions. $$\{\Large{1},\normalsize 2,3\}$$ $$\{\Large{1},\normalsize 3,2\}$$ $$\{\normalsize 1,2,\Large{3}\normalsize\}$$ $$\{\normalsize 2,1,\Large{3}\normalsize\}$$

You can see how this over-counted by one.

$\endgroup$
1
$\begingroup$

turkeyhundt's answer explains what goes wrong, but the following may help in thinking about problems of this type.

The term $\binom{5}{1}8!$ is equal to $8!+8!+8!+8!+8!$, which is what you get if you add the sizes of the five sets $P_1$, $P_3$, $P_5$, $P_7$, $P_9$ together. Here $P_j$ is defined to be the set of permutations in which element $j$ is in its natural position. The size of each of these sets is $8!$ since eight elements are free to move, while one is fixed. Thought of this way, it should be clear that, for example, $P_1$ contains permutations that are also in $P_3$, namely the permutations in which both $1$ and $3$ are in their natural positions. So this addition certainly counts some permutations multiple times. This is why inclusion-exclusion must be used, not because of any overlap between $\binom{5}{1}8!$ and $\binom{5}{2}7!$.

The set whose size you need to find is $P_1\cup P_3\cup P_5\cup P_7\cup P_9$. Inclusion-exclusion is a general method for finding the size of a union of sets with overlaps. In brief, to get the correct count, you need to subtract from the sum above the sizes of all intersections $P_j\cap P_k$, then to add the sizes of all intersections like $P_j\cap P_k\cap P_l$, and so on. The factors $\binom{5}{2}$, $\binom{5}{3}$, and so on, tell you how many intersections there are of a given type, all of which have the same size.

You would not subtract the final expression from $9!$. To do so would be to answer a different question, namely "how many permutations of $\{1,2,\ldots,9\}$ are there in which no odd number is in its natural position?" In that case you would be looking for the size of $P'_1\cap P'_3\cap P'_5\cap P'_7\cap P'_9$ rather than $P_1\cup P_3\cup P_5\cup P_7\cup P_9$.

$\endgroup$
  • $\begingroup$ Rereading the original question, I see the following remark: "But the problem is that $\binom{5}{1}8!$ include permutations that have $2,3,4,5$ odd integers in their natural position right ?" I believe there's a misconception here, which I should have addressed in my answer. The problem is not that we are including permutations with 2, 3, 4, or 5 integers in their natural positions. As the OP points out, that's what we want to do! The problem is counting those permutations more than once. $\endgroup$ – Will Orrick Oct 14 '15 at 19:02
  • $\begingroup$ My answer already addresses another misconception: "Now there is an overlap between ${5 \choose 1}8!$ and ${5 \choose 2}7!$ so that's why we use inclusion and exclusion." There seems to be one final misconception: "So we can't just add, because we will be over counting permutations that have $2,3,4,5$ odd integers in their natural position right !!" The idea was never to add permutations with two odd numbers in their natural positions. We know that these are already included, in fact, included more than once. The idea from the beginning was to subtract these, to eliminate double counting. $\endgroup$ – Will Orrick Oct 14 '15 at 19:03

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.