How many ways are there of splitting the two groups?

Question

Question A) 12 people need to be split up into teams for a quiz. How many ways are there of splitting them into two groups of any size (but there must be at least one person in each group)?

I thought that you should do the summation of 12Cn where n goes from 1 to 11, as if you include 12 then there will not be at least 1 person in a group. Also, 12C6 should be halved to avoid double counting. I have got this answer wrong.

The answer is the summation of 12Cn, where n goes from 1 to 6, and 12C6 is halved. Why does n only go till 6? Is it because 12C5 and 12C7 are the same so we're trying to avoid double counting? If so can you explain the logic?

Thanks for the help:)

Answer 1

The total number of people is $12$, if we split the people into two no empty groups, we are essentially partitioning the set of the $12$ people into two disjoint subsets whose union is the whole set. This way, if we look at all of the possible subsets of the $12$ people set, we can pair two subsets together if they are

1) Disjoint

2) Their union is the whole set

We were only considering subsets that are no-empty, We can therefore discard the empty set and the whole set from all subsets of the 12-people set when trying to do the pairing of subsets. The subsets with k people will be paired with the subsets of $12-k$ people. The number of people in the two subsets that partition the $12$ people set would be therefore categorized in term of their size as one of the possibilities: $\{(1,11), (2,10),(3,9),(4,8),(5,7),(6,6)\}$. The number of subsets of size 1 in the 12-people set is $_{12}C_{1}$ which is equals to the number subsets of size 11 in the 12-people set. So the number of partition in the category of two disjoint subsets with $(1,11)$ people is $_{12}C_1$. Same reasoning show that we have $_{12}C_2$ possibilities to partition the set of $12$ people into $(2,10)$ subsets, $_{12}C_3$ possibilities to partition the set of $12$ people into $(3,9)$ subsets, $_{12}C_4$ possibilities to partition the set of $12$ people into $(4,8)$ subsets, $_{12}C_5$ possibilities to partition the set of $12$ people into $(5,7)$ subsets.

But for the $(6,6)$ category of partitioning the 12-people set into two disjoint subset, are are pairing elements in the 6-people subset of the 12-people set. The number of pairing is $\frac{_{12}C_6}{2}$.

Ok now that we have the number of pairing for all possible category of number of people in the subsets, we can sum them up to get the total number of ways to partition the 12-people set into two no empty subsets by doing $_{12}C_1+_{12}C_2+_{12}C_3+_{12}C_4+_{12}C_5+\frac{_{12}C_6}{2}$.

Answer 2

As for a faster approach, although the groups themselves aren't treated as being labeled, we can tell them apart based on which group person $1$ is in.

Let person $1$ sit at one of the group tables... it matters not which.

Now, for the remaining $11$ people, decide whether to send them to the table person $1$ is at or to the other table. Keep in mind that it is permissible to send everyone to the other table but it is not permissible to send them all to person $1$'s table as that would leave the second table empty.

We see then that there are $2^{11}-1$ ways in which we can distribute them into two nonempty unlabeled groups.