Overcounting when doing Counting Problems
Problem:
How many ways are there to split a dozen people into 3 teams, where one team has 2 people, and the other two teams have 5 people each?
Attempted Solution:
$$N_\text{Teams} = {12 \choose 2}{10 \choose 5}{ 5 \choose 5} = {12 \choose 2}{10 \choose 5}$$
Arriving at this solution by first picking the team of 2 and then the two teams of 5, however the provided solution requires that my answer be divided by 2 due to "Overcounting" which is briefly mentioned but not explained. How does one gain an intuition for overcounting in this problem and also for counting problems in general?
$\endgroup$ 44 Answers
$\begingroup$Does you see why the overcounting happens? I'll attempt to explain.
Suppose your people are A,B,C,D,E,F,G,H,I,J,K,L. You are picking teams. Let me use your algorithm:
1) You pick two people first, say A and B. So the first group is (A,B).
2) You pick five people next, say C,D,E,F, and G. So the second group is (C,D,E,F,G).
3) the leftovers form a group, so that is (H,I,J,K,L). So the three groups are (A,B), (C,D,E,F,G) and (H,I,J,K,L).
But now, suppose you did the following:
1) You pick two people first, say A and B. So the first group is (A,B).
2) You pick five people next, say H,I,J,K,L. So the second group is (H,I,J,K,L).
3) the leftovers form a group, so that is (C,D,E,F,G). So the three groups are (A,B), (C,D,E,F,G) and (H,I,J,K,L) : AGAIN!
Hence the overcounting happens, because you confuse the two groups of five while picking them in an order. And that's why you divide by $2$, because you know you are only to confuse a group of five with another group of five, so the two get mixed up, and you divide to two to negate the order in which the groups are picked.
In general, it is not wrong to overcount. However, it is important to see where order comes into play, and where simply grouping comes into play. When you are picking objects and arranging them, then you are desiring order. However, when you are picking groups, then neither does the inter group arrangement matter nor does the intra group arrangement matter. What I mean to say is , the arrangements (A,B) and (B,A) is an intra arrangement of the group, which we avoid by taking combinations instead of permutations. However, $(A,B),(C,D,E,F,G),(H,I,J,K,L)$ is an inter arrangement of groups, and one that differs from $(A,B),(H,I,J,K,L),(C,D,E,F,G)$ according to your logic, because this involves the order of picking, which in truth is irrelevant. To avoid this discrepancy, we divide by $2$, because this gets rid of the inter arrangement mess. Thus over counting takes place.
Let me phrase you questions for practice :
Suppose you have 14 people. How many ways are there to divide them into seven groups of two each?
Suppose you have 65 people. How many ways are there to divide them into seven groups of seven and four groups of four?
Either get back with the answer, because if you get it right, you are on the right track. Always devise an algorithm, and then think about avoiding inter and intra grouping.
$\endgroup$ $\begingroup$I would say that the question has not given full details,
as it doesn't mention whether the groups are labelled or unlabelled.
If they are labelled, (say Tigers, Lions, Panthers), your answer is correct !
If they are unlabelled, you have to divide by two (more precisely, 2!)
For a more complex example, if there are $7$ groups of $1,1,2,2,2,$
the answer for labelled groups is $\binom81\binom71\binom62\binom42\binom22$
whereas that for unlabelled groups is $\frac{\binom81\binom71\binom62\binom42\binom22}{2!3!}$
Labelled or unlabelled, exactly or at least are essential details that are often missing in combinatorics questions.
The safe thing to do if you are giving a test is to spell out your assumption, or give answers for both options, whenever permissible.
$\endgroup$ 3 $\begingroup$To follow up to астон вілла олоф мэллбэрг's answer, here's the way I finally understood what was going on. Let's say we have:
- Group 1: AB
- Group 2: CDEFG
- Group 3: HIJKL
But we don't care how we label Group 2 or Group 3 - they just have to be groups of 5. This is considered the same grouping:
- Group 1: AB
- Group 2: HIJKL
- Group 3: CDEFG
So, when we choose Group 2, choosing CDEFG (and leaving HIJKL for Group 3) has the same result as choosing HIJKL (and leaving CDEFG for Group 3), so we overcounted by double.
$\endgroup$ $\begingroup$There's one more (cool, in my opinion) way to look at such problems.
For each possible allocation of people into groups, let's take the same example as in the OP, there are a total of $$ \binom{12}{2}\binom{10}{5}\binom{5}{5} =16632 $$ allocations, such as (letters are people, numbers are groups):
$$ (1)AB|(2)CDEFG|(3)HIJKL $$
Now, $\mathbf{each}$ such allocation $\textbf{enters the list exactly twice}$:
$$ (1)AB|(2)CDEFG|(3)HIJKL\\ (1)AB|(2)HIJKL|(3)CDEFG $$ There are no other $\mathbf{identical}$ allocation, i,e. no other way to produce an identical allocation. Hence, the number must be halved, or remove ecery second entry from the list: $$ \binom{12}{2}\binom{10}{5}\binom{5}{5} - \frac{\binom{12}{2}\binom{10}{5}\binom{5}{5}}{2} = 8316 $$
Here's another example: also 12 people, but 2 groups of 4 and 2 groups of 2. What do we have? The list size is $$ \binom{12}{4}\binom{8}{4}\binom{4}{2}\binom{2}{2} $$ Base allocation is $$ (1)ABCD|(2)EFGH|(3)IJ|(4)KL $$ how many of such identical allocations? $$ (1)ABCD|(2)EFGH|(3)IJ|(4)KL\\ (1)ABCD|(2)EFGH|(3)KL|(4)IJ\\ (1)EFGH|(2)ABCD|(3)IJ|(4)KL\\ (1)ABCD|(2)EFGH|(3)KL|(4)IJ $$ Hence $\frac{3}{4}$ of all allocations are repeated, so you need to multiply $$ \binom{12}{4}\binom{8}{4}\binom{4}{2}\binom{2}{2} - \frac{3}{4} \times \binom{12}{4}\binom{8}{4}\binom{4}{2}\binom{2}{2} = 51975 $$
$\endgroup$
