How many permutations of the string "000011112222" contain the substring "2020”?

Question

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?

Answer 1

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.

1. 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.
2. 202020111021: Three pairs of 20 are together; Every sequence like this has been counted 2 times.
3. 202011112020: Two pairs of separate 2020; Every sequence like this has been counted 2 times.

How many permutations of each scenario are there?

1. 5 permutations
2. 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$
3. $\binom{5}{2} = 10$

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

Answer 2

@Funaizhang... This is what I am thinking.. But I can't figure out the discrepancy. Start with 2200001111. For this string, consider 2020 as one character. There are 7!/(4!2!)=105 ten character strings that contain 2020. At this stage, we are missing two 2s. Case 1: the two 2s are together. There are 8 spaces, so 8C1105=840. Here, no repetition of 2020 occurs because the two 2s are together. Case 2: The two 2s are separated. (There are double counts here.) We have a total of 8C2105=2940 ways to do so. But creation of new 2020s are possible, so the cases with 202020 are double-counted. So treat 202020 as 1 string, there are then 7!/4!=210 ways of arranging it. But the strings with 20202020
(5 of them) will be double-counted. So for this case, total should be 2940-210+5=2735. Finally, 2735+840=3575.