help with inclusion-exclusion question

Question

How many permutations of the $10$ digits either begin with $987$, or contain $45$ in positions five and six, or end with $123$?

Answer: $7! + 8! + 7! – 5! – 4! – 5! + 2! = 50138$.

Now I understand how we get $7! + 8! + 7!$. However, I do not understand how you get $– 5! – 4! – 5! + 2!$. If some could just show me how you get $5!$ for $987$ I think I can do the rest. Thanks!

Answer 1

The entire idea of PIE is to systematically overcount and undercount until we arrive at the exact count. Let us examine how we may apply this to your case.

First, let us compute each of the three cases separately. Indeed, $7!$ numbers have the first property, $8!$ have the second, and $7!$ have the third. But what you have to realize is that some numbers fall into more than one of these categories. Thus, we have overcounted and need to correct for that by subtracting.

We now consider the pairwise intersections between the sets. What I mean by that is, consider how many numbers have at least two of the three given properties. For example, consider numbers of the form $987X45XXXX.$ Each was counted twice in our first count above. So subtract one times of this number. It's the same for the other pairs, so we end up subtracting $5! + 4! + 5!.$

Finally, we consider numbers that satisfy all three properties. Notice that these numbers are in the form $987X45X123,$ so there are $2!$ of these. In the first count, both of these were each counted $3$ times. In the second count (which was negative for correction), both were undercounted $3$ times (one for each pairwise correction). So we have to add one times this count, or $2!.$

The final answer is thus $(7! + 8! + 7!) - (5! + 4! + 5!) + 2!.$

And we are done! Hope this helped clear things up!

Answer 2

You have three sets $A,B,C$ and $$n(A \cup B \cup C) = n(A) + n(B) + n(C) -n(A \cap B) -n(A \cap C) - n(B \cap C) + n(A \cap B \cap C)$$.
You need to compute the pairwise intersections of the sets, and the intersection of all three sets. The intersection of "begins with 987" with "contains 45 in positions five and six" is "begins with 987 with 45 at positions 5 and 6" leaving 5 slots to put the other 5 numbers, so 5! is the size of that intersection.