No. of ways to divide 6 pairs into 3 teams so that no pairs are in the same team

Dec 2016
6
2
Aberdeen, Scotland
There are 6 pairs (12 people) and they must be divided into 3 teams. All teams must have 1 or more occupants. Both people from a pair must not be in the same team.

I already answered a similar question, the only difference was that there were two teams instead of three. If x is the number of pairs, I found the no. of ways to divide the pairs into 2 teams such that no pairs are in the same team, f(x), to be equal to the sum of (x-1) choose n from n=0 and n=(x-1). Another way of writing f(x) is f(x)=2^(x-1).

Please correct me if I made a mistake, because chances are I did! I'm new to combinatorics and don't know a whole lot, but I really need an answer to this question
 

romsek

MHF Helper
Nov 2013
6,725
3,030
California
must the teams be of equal size?
 

romsek

MHF Helper
Nov 2013
6,725
3,030
California
maybe you've found some incredible shortcut but I'm seeing the problem as fairly complex.

First off I'll assume that the teams do not have to be the same size. You didn't say they had to be.

Clearly teams are of size 2-6, given that a pair cannot be on a team together and there are only 6 pairs.

Also clearly the number of team members of the 3 teams must sum to 12.

Given this there are a few combinations of team sizes that are valid

$\left(
\begin{array}{ccc}
2 & 4 & 6 \\
2 & 5 & 5 \\
3 & 3 & 6 \\
3 & 4 & 5 \\
4 & 4 & 4 \\
\end{array}
\right)$

Let's look at each of these.

$(2,4,6)$ - a team of 6 must use one member of each pair.

There are $2^6=64$ ways of selecting the 6 member team.

We don't have to worry about pairs overlapping when choosing the 4 member team so there are ${_6C}_4 = 15$ ways of selecting this.

Thus there are $N_{(2,4,6)} = 64\cdot 15=960$ ways of selecting this arrangement

$(2,5,5)$ - When selecting the first 5 person team there are ${_6C}_5=6$ ways to select pairs and 2 ways to select a member from each pair so there are

$6 \cdot 2^5 = 192$ possible combinations for the 5 person team.

This leaves 5 pairs with 1 member, and 1 pair with 2 remaining.

When selecting the 2nd 5 member team one has to include the pair with two remaining. Both pair members cannot be left for the final team.

Thus we select that pair, and there are 2 ways of selecting that pair, then we have ${_5C}_4 = 5$ ways of choosing the other 4 members. So there are $2\cdot 5 = 10$ ways of selecting the 2nd 5 member team. The 2 member team is then fixed.

Thus there is a total of $N_{(2,5,5)}=192 \cdot 10 =1920$ valid combinations of this arrangement

$(3,3,6)$ - Again there are $2^6$ ways to select the 6 member team. Then there are ${_6C}_3 = 20$ ways to select the 3 member team

so there are $N_{(3,3,6)}=64\cdot 20 = 1280$

$(3,4,5)$ - As before there are $192$ ways to select the 5 member team.

We must select the unused pair when selecting the 4 member team and can do that in 2 ways. Then there are ${_5C}_3 = 10$ ways to select the rest so there are

$N_{(3,4,5)}=192 \cdot 2 \cdot 10 = 3840$ ways of selecting this arrangement

$(4,4,4)$- there are ${_6C}_4 = 15$ ways to select 4 pairs and then 2 ways per pair to select members so there are

$15\cdot 2^4 = 240$ ways to choose the first team

Then two pairs are left which must be used for the 2nd team. There are 4 ways of selecting these 2 members and then ${_4C}_2=6$ ways to select the remaining 2 members. Thus there are $N_{(4,4,4)} = 240 \cdot 4 \cdot 6 = 5760$ valid combinations for this arrangement.


Summing all these up we get

$960 + 1920 +1280 + 3840+ 5760= 13760$ valid arrangements
 
Dec 2016
6
2
Aberdeen, Scotland
Wow, that is incredibly helpful. For some reason i was trying to find a general formula to answer the question for any number of pairs, I'm sure you can imagine how far I got trying that...
Thanks
 
Last edited: