# The number of ways to divide 5 people into three groups

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.

• Because the groupings $(A),(BC),(DE)$ and $(A),(DE),(BC)$ are the same (for example). – lulu Aug 11 '17 at 12:42
• Is there a way of knowing how many will be repeated without listing them out? – Casper C. Aug 11 '17 at 12:46
• 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. – lulu Aug 11 '17 at 12:48
• Thanks, but how can you tell the amount of symmetry there is? – Casper C. Aug 11 '17 at 12:56
• 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. – lulu Aug 11 '17 at 13:03

• 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*}

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

• Thanks, but how do I tell how much repeat-counting I've done without listing out the combinations? – Casper C. Aug 11 '17 at 12:57
• @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. – Benjamin Dickman Aug 11 '17 at 13:04
• 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. – Casper C. Aug 11 '17 at 13:45
• @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$. – Benjamin Dickman Aug 11 '17 at 13:50