Number of way $5$ people can be divided into $3$ groups

Question

The question asks the number of ways to divide $5$ people into $3$ groups with no conditions attached. (In case people think this is a duplicate).
I have studied both grouping and distribution in combinatorics but I often get confused where to apply what. Anyway, I digress.
My First Approach:
The first thing I did was to assign variables. Let the first, second and third groups be $x_a, x_b $ and $x_c$. Now $$x_a + x_b + x_c = 5$$ I solved this by partitioning $5$ in $3$ ways, that is $\binom {n+r-1}{r-1} $ where $n = 5, r=3$ giving us, $$\binom{7}{2}= 21$$ The answer, however, is given as $25$.

Please tell me where I'm going wrong and also could someone advise me on when to use partitioning and when to make groups if the group size is not given.

Answer 1

Assume that the groups are interchangeable, so that the division $(A,B),(C,D),(E)$ is the same as the division $(C,D),(A,B),(E)$ and assume that you don't allow empty groups.

The maximal group has to have either $2$ or $3$ members.

Case I: (maximal group has $3$ members). Then the counts must be $\{3,1,1\}$ and the division is determined by the members in the group of $3$. Hence there are $$\binom 53=10$$ divisions of this type.

Case II: (maximal group has $2$ members). Then the counts must be $\{2,2,1\}$. Then there are $\binom 52=10$ ways to populate one group of two, and then $\binom 32=3$ to populate the other. As switching the two groups of two does not change the division we see that there are $$\frac {10\times 3}2=15$$ divisions of this type.

Combining we see that there are $$10+15=25$$ possible divisions.

Answer 2

First Approach: Note that these people are distinguishable. You cannot treat them like stars and bars.
Thinking about it, there must be one person in each group. Now, we have some casework.
We have two cases. WLOG first number $\ge$ second number $\ge$ third number.
Our cases are 3-1-1 and 2-2-1.
3-1-1: The first leads to $\frac{5!}{3!2!}=10$ solutions.
2-2-1: This leads to $\frac{5!}{2!2!2!}=15$ solutions. This is a total of 10+15=25 solutions.
Partitions are all the addition of positive integers that are equal to a number.
For example, partitions of $4$ are $4,3+1,1+3,2+2,1+1+2,1+2+1,2+1+1,1+1+1+1.$
Correct me if I'm wrong, but I believe you mean distribution.
Use them when there are items to be handed out and items that can receive them.

Answer 3

The formula you've applied is for labelled groups of unlabelled things (i.e. all that matters is the numbers of things in each group, but having groups of size $3,1,1$ is different to $1,3,1$.

This is exactly the opposite of what you want, which is unlabelled groups of labelled things. (If you have groups of size $3,1,1$ it matters which people go in the same group, but not what order you put the groups in.)

I think for your problem there is also another restriction: no group is allowed to be empty.

One way to do this is to first consider labelled people in labelled groups, then divide by the number of ways to label the groups. Since there are three groups, there are $3!=6$ ways to label them.

Now the number of ways to put $5$ labelled people into $3$ labelled groups is $3^5$ - for every person you can choose group A, B or C, and these choices are independent. However, this counts some divisions that aren't allowed (where some group is empty), so you have to allow for this. The best way to do that is the inclusion-exclusion formula.

In this case, inclusion-exclusion is relatively simple as there are only three teams. You start from all ways to assign A, B or C to each person ($243$ ways). Then for each team you subtract off the ways that don't use that team. So there are $2^5=32$ ways that don't use A, and the same for B and C. So this gives $243-3\times 32=147$. However, there is one way to assign the teams that doesn't use A or B (all C), and you subtracted it twice (once because it doesn't use A, and once because it doesn't use B), so you need to add it back on. The same applies to the other two possibilities with two empty teams, so in total you have $243-3\times 32+3=150$ assignments.

Now every way to split the people into three teams is counted $6$ times (because there are $6$ ways to label the teams), so the final answer is $150/6=25$.

If there were $n$ people the same approach would give $\frac{3^n-3\times 2^n+3}{6}$ possibilities.