How many permutations of the string "000011112222" contain the substring "2020”? So far, this is what I know. There are 9 ways to place 2020 and $\frac{8!}{4!2!2!}$ ways to arrange the remaining numbers. Im having a problem tackling the overcounting case.. If there are 2 seprate 2020s then i need to subtract $6C4$? Thanks in advance!
Is there a solution using PIE or recursion?

Unfortunately, the solution is not so straight-forward. There's no problem with the first step:
Total number of permutations including all over-counts = $\frac{9!}{4! 2! 2!} = 3780$
Next, we consider where we can get over-counts, so as to get rid of them from the total number of permutations. Over-counts arise from the following scenarios.

*

*202020201111: All four pairs of 20 are together; Every sequence like this has been counted 3 times. For e.g. 202020201111, 202020201111 and 202020201111 are all considered different permutations in the initial step. So each is over-counted by 2 times.

*202020111021: Three pairs of 20 are together; Every sequence like this has been counted 2 times.

*202011112020: Two pairs of separate 2020; Every sequence like this has been counted 2 times.

How many permutations of each scenario are there?

*

*5 permutations

*We are permutating 7 elements, 4 of which are 1s, so $\frac{7!}{4!}$. But note that we need to exclude from these cases of 4 pairs of 20 being together (already accounted for in scenario 1), of which there are 10. So in total $\frac{7!}{4!} - 10 = 200$

*$\binom{5}{2} = 10$
The final answer is then $3780 - 5 \times 2 - 200 - 10 = 3560$.
