4
$\begingroup$

You have 11 students and are creating two groups. At least one student must be in a group. How many different combinations exist.

My Solution:

We know that no group can be empty, so we put $1$ student in every group. This gives us $9$ renaming students.

Lets say that we only want to add $1$ more student in group $A$, the amount of choices we have is $ 9 \choose 1 $ while all the renaming students are sent to the other group. If we wanted to place an extra two students in the group we would have $ 9\choose2 $ choice, this continues until $ 9 \choose 9 $.

So the total number of combinations is the sum of the individual options:

$$ {9\choose1}+{9\choose2}+{9\choose3}+\cdots+{9\choose9}$$

I was wondering if my solutions is correct and if there is a better way.

$\endgroup$
1
  • $\begingroup$ You begin by putting one student in each group... but which students? It matters because putting Bill and Ben on different teams leads to distinct combinations from putting them on the same team. $\endgroup$ Feb 14, 2020 at 0:52

2 Answers 2

7
$\begingroup$

Suppose one of the students is Fred. Each of the other students must be placed in his group or the other group. That gives us $2^{10}$ choices. However, we cannot place all ten of the other students in Fred's group, otherwise the other group would be empty, so there are $2^{10} - 1$ ways to distribute the students to two non-empty groups.

We could correct your solution. Start with Fred. We must place either one, two, three, four, five, six, seven, eight, nine, or ten of the other ten students in the other group, giving $$\sum_{k = 1}^{10} \binom{10}{k} = \sum_{k = 0}^{10} \binom{10}{k} - 1 = 2^{10} - 1$$ ways to distribute the students to two non-empty groups.

$\endgroup$
6
  • $\begingroup$ I don't follow the inference in this sentence "However, we cannot place all ten of the other students in Fred's group, otherwise the other group would be empty, so there are 2^10−1 ways to distribute the students to two non-empty groups."... it seems a bit of jump. $\endgroup$ Feb 14, 2020 at 0:42
  • $\begingroup$ You subtract that one combination to account for the case where all the students are in Fred's group as this cannot happen. $\endgroup$
    – Marcy
    Feb 14, 2020 at 0:43
  • $\begingroup$ Why can you not assign a person to each group ahead of time? $\endgroup$
    – WaterDrop
    Feb 14, 2020 at 1:06
  • $\begingroup$ If you assign a person to each group at the beginning, you run the risk of counting each group with more than one person multiple times, once for each way you could assign one of the people in that group as the first person in that group. $\endgroup$ Feb 14, 2020 at 1:41
  • $\begingroup$ If you had to place three people in two non-empty groups, you can do it in three ways: $\{A, B\}, \{C\}; \{A, C\}, \{B\}; \{A\}, \{B, C\}$. Consider the case $\{A, B\}, \{C\}$. You count this once when you designate $A$ as the person in the first group, $C$ as the person in the second group, and $B$ as the additional person in the first group, and once when you designate $B$ as the person in the first group, $C$ as the person in the second group, and $A$ as the additional person in the first group. $\endgroup$ Feb 14, 2020 at 1:42
1
$\begingroup$

Your solution is a bit wrong. if you replace the $9$ with $10$ then you will get the right answer, recall from the binomial theorem that
\begin{eqnarray*} \sum_{n=1}^{10} \binom{10}{n} = 2^{10}-1. \end{eqnarray*} So an easier way to this solution would be to say ...

Put the first person into a group & then the other $10$ can be put in either group with the exclusion of putting all $10$ into the first group.

$\endgroup$
0

You must log in to answer this question.

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