How many ways are there to place 7 people into three groups of any size?
I know for this question I would have to find all the possible combinations. I've got to $\frac{7!}{3!3!3!}$ but I don't know what the numerator would be because it says it can be of any size.
$\endgroup$4 Answers
$\begingroup$Let's try something a little different: we'll generate the groups without regard to their size.
How many ways are there to fill in three groups with seven people, assuming that the groups are labeled and it is allowed for a group to be empty? Each person must be able to enter any group without concern for anyone else, so the result is $3^7 = 2187$.
But, of course, some of these have only two groups with people in them. We must exclude these. There's $\binom{3}{2} = 3$ ways we can pick two groups to have people in them, and $2^7=128$ ways for that to happen.
But in those we're excluding too many: we've excluded the situation where only one group gets all the people twice! So we have to include it again. There's $\binom{3}{1} = 3$ ways we can pick one group to have people in it, and $1^7=1$ way for that to happen.
So we have $\binom{3}{3}3^7 - \binom{3}{2}2^7 + \binom{3}{1}1^7$ ways to build 3 labeled, non-empty groups. But the groups aren't labeled, so we have to divide this result by the number of ways we can rearrange the groups. Our final answer is... $$\frac{\binom{3}{3}3^7 - \binom{3}{2}2^7 + \binom{3}{1}1^7}{3!}=\frac{1\cdot2187-3\cdot128+3\cdot1}{6}=\frac{2187-384+3}{6}=\frac{1806}{6}=301$$ which agrees with the other answers given.
This process of alternately including and excluding progressively more restrictive possible outcomes is called the Inclusion-Exclusion Principle.
Let us now generalize this.
For $n$ people into $k$ unlabeled, nonempty groups, we have
$$S(n, k)=\frac{1}{k!}\sum_{j=1}^k(-1)^{k-j}\binom{k}{j}j^n$$
These are called the Stirling Numbers of the Second Kind.
$\endgroup$ $\begingroup$First of all we need to know how many ways we can partition 7 into three non-zero parts, and the answer is four. For each case we count the number of ways to divide the people into these group sizes:
- 5,1,1 There are $\binom75=21$ ways to assign the people in the group of 5, after which the compositions of the remaining two groups are forced. Hence there are $21$ possibilities with this grouping.
- 4,2,1 The quartet can be assigned in $\binom74=35$ ways. Then we can choose any of the remaining three people to be all alone. This yields $35×3=105$ possibilities.
- 3,3,1 As before we can choose any of the seven people to go solo. A trio can be chosen from the other six in $\binom63=20$ ways, but we must divide this by two since choosing a trio and its complementary trio yield the same groupings. Hence we have $7×20/2=70$ ways for this case.
- 3,2,2 The trio here can be chosen in $\binom73=35$ ways. By the same reasoning as the 3,3,1 case, we have $\binom42/2=3$ ways to make two pairs from the leftovers and $35×3=105$ ways overall.
Summing up we have 301 ways to group seven people into three groups of any size.
$\endgroup$ $\begingroup$You can form three groups of any size from 7 by forming groups of size
- 5,1,1 in $\binom 7{5,1,1}/\color{silver}{1!}2!$ ways.
- 4,2,1 in $\binom 7{4,2,1}/\color{silver}{1!}\color{silver}{1!}\color{silver}{1!}$ ways
- 3,3,1 in some ways
- 3,2,2 in some ways
Can you see why and complete?
Addendum
$\binom 7{5,1,1}$ is a multinomial coefficient, equal to ${^7\mathsf C_5}{^2\mathsf C_1}{^1\mathsf C_1} ~=~ \frac{7!}{5!~2!}\frac{2!}{1!~1!}\frac{1!}{1!~0!} ~=~\frac{7!}{5!~1!~1!}$
$\endgroup$ 2 $\begingroup$Make possible cases ie
331
223
421
511
and the use formula of grouping to comput the no. of ways for each of the cases and add to get final answer....
The answer is 105 + 70+ 105 + 21=301.
