Why do we use inclusion and exclusion here?

Question

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

Answer 1

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.

Answer 2

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