After reading problem # 712716, I would like to ask the following slightly different question:-

From a group of seven students, in how many ways can a teacher set up two teams each containing at least one student?

Let me use a simple example to illustrate the difference between the two.

We assumed that there are only 3 students, namely A, B, C.

Possible (and allowable) ways of dividing them into two groups are {A}+{B, C}, {B}+{C, A}, {C}+{A, B}; i.e. 3 ways.

Possible (and allowable) ways of setting up two groups are {A}+{B, C}, {B}+{C, A}, {C}+{A, B}, {A}+{B}, {B} +{C}, {C}+{A}; i.e. 6 ways.

  • $\begingroup$ Is "setting up" into two groups different than dividing them into 3 groups (where the third group contains people not in any group), plus the number of ways to divide them into 2 groups (for the case where everyone is in a group)? $\endgroup$ – George V. Williams Mar 15 '14 at 18:23
  • $\begingroup$ Yes. You can treat it that way but the counting may not be the same as the original post. I think. $\endgroup$ – Mick Mar 15 '14 at 18:59

For the time being ignore the restrictions.
When you are setting up two teams, you are essentially dividing into three teams say A, B and C, where A and B play and C doesn't play.
So the total no. of ways of doing this is $3^n$.

Considering the restrictions:
Now out of $3^n$,
No. of ways in where A is empty : $2^n$ (This is same as dividing n students into 2 teams B and C)
Similarly no. of ways in which B is empty : $2^n$.
One case is common in both where both A and B are empty and we have counted it twice.

Thus no. of ways in which we divide into 3 teams A, B, C where A, B have atleast one student = $3^n - 2^n -2^n +1 = 3^n - 2^{n+1} + 1$.

(We can see that the above number is even)

Here we have double counted Teams A and B for same sizes. So divide by two.
Thus your answer is $(3^n - 2^{n+1} + 1)/2$.

For n=3, this is $(27-16+1)/2 = 6$.
For n=7, it is 966.

| cite | improve this answer | |

Another way of taking this: The teacher can set up two teams such that nobody gets left out (ways of partitioning into two) or leave out some (partition into three, and select one of the partitions to be left out). This uses Stirling numbers of the second kind: $$ \newcommand{\classes}[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}} \classes{7}{2} + \binom{3}{1} \classes{7}{3} = 63 + 3 \cdot 301 = 966 $$

| cite | improve this answer | |
  • $\begingroup$ Thanx. Have just learnt sth new - Stirling numbers. $\endgroup$ – Mick Mar 16 '14 at 5:42

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.