1
$\begingroup$

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?

$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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) $\endgroup$
    – kba
    Dec 19, 2020 at 12:31
  • $\begingroup$ @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. $\endgroup$
    – David K
    Dec 19, 2020 at 17:42
  • $\begingroup$ @Funaizhang: Your reasoning is sound. (+1) $\endgroup$
    – Markus Scheuer
    Dec 19, 2020 at 17:52
  • $\begingroup$ @kba edited with more info. It's basically what DavidK wrote too. $\endgroup$
    – Funaizhang
    Dec 20, 2020 at 4:50
  • $\begingroup$ @DavidK, Can u repost your solution again with the inclusion-exclusion formula? $\endgroup$
    – kba
    Dec 20, 2020 at 11:04
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .