3
$\begingroup$

How many ways can 5 people be divided into three teams where each team must have at least one member?

Assumably they can either be put in one group of 3 people then two groups with 1 person, or two groups with 2 people then one group of 1 person. Hence my answer was $$ ^5C_3 +\, (^5C_2) \cdot (^3C_2)$$ However the provided answer was $$ ^5C_3 +\, (^5C_2) \cdot (^3C_2) \cdot (1/2)$$ Where did the 1/2 come from?

Thanks.

$\endgroup$
  • 2
    $\begingroup$ Because the groupings $(A),(BC),(DE)$ and $(A),(DE),(BC)$ are the same (for example). $\endgroup$ – lulu Aug 11 '17 at 12:42
  • $\begingroup$ Is there a way of knowing how many will be repeated without listing them out? $\endgroup$ – Casper C. Aug 11 '17 at 12:46
  • $\begingroup$ Sure, there's a symmetry. the two $2-$member teams can be interchanged. You have the same problem with the other term, though you short-circuited it. You could have written the first term as $\binom 53\times \binom 21 \times \binom 11$ but then you'd have had to divide by $2$ again to cancel the symmetry between the $1-$ member teams. $\endgroup$ – lulu Aug 11 '17 at 12:48
  • $\begingroup$ Thanks, but how can you tell the amount of symmetry there is? $\endgroup$ – Casper C. Aug 11 '17 at 12:56
  • $\begingroup$ Not following. the symmetry is that every pair of $2$ member teams is counted twice (switching the order). There are situations in which this can get tricky...for example, in counting rolls of a pair of dice you have to distinguish the cases in which you get two of a kind. But there is no problem here. $\endgroup$ – lulu Aug 11 '17 at 13:03
3
$\begingroup$

Two add-ons to the information already given.

  • The factor $\frac{1}{2!}$ occurs in fact twice in your example, since we have \begin{align*} &(^5C_3) (^2C_\color{blue}{1})(^1C_{\color{blue}{1}})\color{blue}{\frac{1}{2!}} +\, (^5C_\color{blue}{2})(^3C_\color{blue}{2})(^1C_1)\color{blue}{\frac{1}{2!}}\\ &\quad=10\cdot2\cdot1\cdot\frac{1}{2}+10\cdot 3\cdot 1\cdot \frac{1}{2}+\\ &\quad=25 \end{align*}

  • We can reformulate the problem and ask for the number of ways to partition a set consisting of $5$ elements into $3$ non-empty subsets. These numbers are known as Stirling numbers of the second kind ${n\brace k}$.

    Here we are looking for \begin{align*} {5\brace 3}=25 \end{align*}

$\endgroup$
1
$\begingroup$

When you pick the team as two players, another two, and then just the final one is left over, consider the following: if the five players are named $A, B, C, D, E$, then you might start by picking the duo $\{A, B\}$ and then $\{C, D\}$, which results in the breakdown of $\{\{A, B\}, \{C, D\}, \{E\}\}$ or you might have first picked the duo $\{C, D\}$ and then picked $\{A, B\}$, which would result in the same grouping of $\{\{A, B\}, \{C, D\}, \{E\}\}$.

To avoid this double-counting, you divide in this scenario by $2$. (Or, equivalently, multiply by $1/2$.)

$\endgroup$
  • $\begingroup$ Thanks, but how do I tell how much repeat-counting I've done without listing out the combinations? $\endgroup$ – Casper C. Aug 11 '17 at 12:57
  • $\begingroup$ @CasperC. Yes, this is the difficult part of combinatorics. You may wish to return to the definition of, e.g., $^5 C_3$ to see how and why it was defined; its definition, too, involves a bit of division to avoid overcounting, and the scenario here involves a similar bit of reasoning. $\endgroup$ – Benjamin Dickman Aug 11 '17 at 13:04
  • $\begingroup$ May I rephase that? How do we know there are only two repetitions of $\{\{A, B\}, \{C, D\}, \{E\}\}$ ? How would we know how many repetitions of groups there would be if there were 7 people instead of 5? Thanks for helping. $\endgroup$ – Casper C. Aug 11 '17 at 13:45
  • $\begingroup$ @CasperC. This relies on the observation that $n$ objects can be arranged in $n!$ ways. Here, you have the $2$ groups overcounting by a factor of $2! = 2$. $\endgroup$ – Benjamin Dickman Aug 11 '17 at 13:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.