# In how many ways can a teacher divide a group of seven students into two teams each containing at least one student?

In how many ways can a teacher divide a group of seven students into two teams each containing at least one student? two students? What about when seven is replaced with a positive integer n≥4?

I thought about using combinations.But not sure how to go from there.

Assuming the students are not interchangeable, for $n$ students there are $2^n$ subsets to make a team. Two of these are not allowed: the null set and the whole set, as both result in a team with no members. Then we have counted each team twice, once selecting it and once selecting all the rest. So there are $\frac 12(2^n-2)$ ways to make two teams each with at least one student. If you need at least two students per team, start from the last. There are $n$ single student teams that are no longer allowed, so the answer here is $\frac 12(2^n-2)-n$

• It is nice to see that the properties of the power of a set can be used to solve a problem in combinatoric. – Mick Mar 16 '14 at 9:46

I'd look at a generating function. We have $a + b = 7$, with $a$ and $b$ representing our groups. So if $a, b \geq 1$, we have $f_{a}(x) = \sum_{i=1}^{7} x^{i}$. $f_{b}(x)$ is the same function. So we let our generating function, $g(x) = f_{a}(x) * f_{b}(x) = x^{2} * (\frac{1-x^{7}}{1-x})^{2}$. Then simply expand out using binomial identities to get your answer.

So expanding out $(1-x^{7})^{2}$, we get $num(x) = \binom{2}{0} - 2x^{6}$. Expanding out the denominator gives us $denom(x) = \sum_{i=0}^{7} \binom{i + 2 - 1}{i} x^{i}$. Now multiply $num(x) * denom(x)$, and take the coefficient of the $x^{7}$ term. That's your answer.

More reading on generating functions: http://www.dreamincode.net/forums/topic/304589-a-look-at-the-knapsack-problem-with-generating-functions/

Best of luck!

• Note: This solution assumes that students are indistinguishable. – ml0105 Mar 15 '14 at 1:17

at least $1 : 3$ ways at least $2 : 2$ ways

if seven replaced by positive integer $n≥4$:

at least 1 :
if $n$ is even number so the number of ways = $\frac{n}{2}$
if $n$ is odd number so the number of ways = $(n-1)$

at least 2 :
if $n$ is even number so the number of ways = $\frac{n}{2}-1$
if $n$ is odd number so the number of ways = $\frac{n-1}{2}-1$

• Using MathJax/Latex will make it easier for everyone else to read. Please review some tutorials. – homegrown Mar 15 '14 at 1:41
• I don't think "at least 1:3 ways" is correct. (A)+(remaining), (AB)+(remaining), (ABC)+(remaining), (ABCD)+(remaining) are 4 ways already. Not to mention other combinations. – Mick Mar 15 '14 at 3:33

well, the basic breakdown goes:

1-6, 2-5, 3-4

For the 1-6, there are 7 choices for the student that is by himself, and the other 6 are dictated by the one by himself, so there are 7 ways to break them up into 2 groups with one student in one and 6 in the other.

For 2-5, you have 7 options for the first person in the group of 2, and then 6 options for the second person, and again -- the other 5 people are the other team. 7*6 means there are 42 ways to break it up into 2 and 5.

For 3-4, you have 7 options, then 6 options, then 5 options for the group of 3, the other 4 people are automatically on the other team. 7*6*5=210 ways to to break it up into 3 and 4.

Hope that helps.

Edit: What I did above has repeats that I did not consider, so adding a a different, hopefully more useful explanation.

Consider A,B,C,D,E,F,G as the seven people in your group. If you break the group into to a group of 1 and a group of six, you have seven possibilities (any one of the seven people could be in the group all by themselves.

If you break the group into 2 and 5, as shown above, there are 42 ways to pick 2 people out of a group of 7, but some of those ways are repeats. Specifically, (A,B) = (B,A). In fact, every pair of students has a repeat (just picking them in reverse order), so really only half of the 42 methods are different from each other. So, we only get 21 different ways to break them up into a group of 2 and a group of 5.

If you break them up into a group 3 and 4, there are 210 ways to do this, but again, we get repeats. Consider picking (A,B,C). This is the same as picking (A,C,B), (B,A,C), (B,C,A), (C,A,B), (C,B,A) (this is arranging 3 objects, so we have 3 choices for first place, 2 for the second, and one choice for the last object). So there are six ways to pick the same group. In other words, only $\dfrac{1}{6}$ of the groups are unique. 210/6 = 35 different ways to break them up into a group of 3 and a group of 4.

• Ah good call, I was leaving order in. Thanks for pointing that out. Will edit it. – Cyllindra Mar 15 '14 at 17:29