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

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

• Is it ok to ask for clarifications on the overcounting? In 1) How is the sequence been overcounted by 3 times? 2) This I didn't quite get it.. 3) There are 5 spaces in between the 1s to insert the 2 2020s.. so this is 5C2... (This is get it)
– kba
Dec 19, 2020 at 12:31
• @kba The example in case 1 comes up by putting $2020$ at the start of the string and then filling in the rest; by putting $2020$ two places away from the start; and by putting $2020$ four places away from the start. The example in case 2 can come up by putting $2020$ at the start or two places from the start. Dec 19, 2020 at 17:42
• @Funaizhang: Your reasoning is sound. (+1) Dec 19, 2020 at 17:52
• @kba edited with more info. It's basically what DavidK wrote too. Dec 20, 2020 at 4:50
• @DavidK, Can u repost your solution again with the inclusion-exclusion formula?
– kba
Dec 20, 2020 at 11:04

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