TIFR CSE 2012 | Part A | Question: 7

Question

It is required to divide the $2n$ members of a club into $n$ disjoint teams of $2$ members each. The teams are not labelled. The number of ways in which this can be done is:

• A. $\frac{\left ( 2n \right )!}{2^{n}}$
• B. $\frac{\left ( 2n \right )!}{n!}$
• C. $\frac{\left ( 2n \right )!}{2^n . n!}$
• D. $\frac{n!}{2}$
• E. None of the above

Comments

Choose n out of 2n members = 2nCn ways.
Remaining n members can be divided into n teams in n! ways.
So total = (2nCn)n! ways
But in each team, (m1,m2) = (m2,m1), so we have to divide by 2 'n' times i.e 2^n.
Final answer = ((2nCn)n!)/(2^n) ways.

This way of reasoning is correct?

---

The correct answer is (C) (2n)! / n!⨉2n

---

I think that is formula for number of perfect Matching for Complete Graph not complete bipartite graph.

Correct me if I am wrong.

---

Difference bet. labelled and unlabelled teams:

Lets take n=2 , then we have 4 members (2n members) named as A,B,C,D.

CASE 1: No. of ways 2 teams can be formed(When teams are labelled ) is :(t1 and t2 are two teams)

[t1= AB and t2= CD]  or [t2= AB and t1= CD] or

[t1= AC and t2= BD] or [t2= AC and t1= BD] or

[t1= AD and t2= BC]  or [t2= AD and t1= BC]

Total no. of ways teams of two people can be made is = (2n)!/(2^n)

                                                                                       = (2*2)!/ (2^2)

                                                                                        = 4!/4

                                                                                        = 3*2 = 6 ways

 

CASE 2: No. of ways 2 teams can be formed(When teams are unlabelled ) is :

[ AB and CD]  or (here we can't swap team1 and team2 as they don't have any name)

[ AC and BD] or 

[ AD and BC]  or 

Total no. of ways teams of two people can be made is = (2n)!/((2^n)*n!)

                                                                                       = (2*2)!/ ((2^2)*2!)

                                                                                        = 4!/(4*2)

                                                                                        = 3 ways

 

 

Answer 1

${2n}$ member to be n teams with $2$ member each and teams are unordered so we can exchange $n$ team member among them.
 
     =$\dfrac{(2n)!}{\underbrace{2!.2!.2! \dots 2!}_{n \text{ times }} \times n!}$
     =$\dfrac{(2n)!}{2^n \times n!}$

Option $C.$

Comments

let n=2 (teams)
no of members = 4 {1,2,3,4}
combinations satisfied
(1,2) (3,4)
(1,3) (2,4)
(1,4) (2,3)
6 combinations possible we can do it by option elimination.

---

6 combinations of team but only 3 ways to do it..

In option C) n=2 we get 4!/(2^2x2!)=3 ways.

Best possible way when nothing is cleared from the question itself.

---

For more questions of this kind, see Sheldon Ross book on Probability, chapter 1. They describe a term of the kind $\frac{n!}{n_{1}!n_{2}!...n_{r}!}$ as a multiomial coefficient where $n_{1} + n_{2} + ... = n$ and there are $n_{1}$ objects of the first kind, $n_{2}$ of the second kind and so on.

Here, I can say there are 2 objects of first kind, 2 objects of second kind and so on until 2 objects of nth kind. The multinomial coefficient is applied in problems where you divide these objects into groups or teams.

Additionally, as already described above, if the divisions are unlabelled, you must divide the whole thing by $n!$ where $n$ is the number of divisions. This is because you don't want to count one unlabelled division multiple times.

Answer 2

there are 2n members in the club so we can select n members in $^{2n}C_n$ ways

while selecting the n members will come in a particular order and arrangement among them is not there

Now we can place the remaining n members with the already selected n members in $n!$ ways

so here we get $^{2n}C_n \times n!$

Now (member 1, member 2) = (member 2, member 1) so we can divide the above equation by 2 n times

final answer is $\frac {^{2n}C_n \times n!}{2\times 2\times 2 \times...n\ times} = \frac{(2n)!}{2^n \times n!} $

 

Answer is $C$

Answer 3

Take example for 2n = 4

From 4 members select any 2 = 4C2

Remaining 2 members select 2 = 2C2

Combinations possible are :-

1. (1 2)(3 4)
2. (1 3)(2 4)
3. (1 4)(2 3)
4. (2 3)(1 4)
5. (2 4)(1 3)
6. (3 4)(1 2)

In each case there are 2 teams each having 2 members.

As teams are unlabelled; arrangements does not matter.

Therefore in above example team1 = team6 , team2 = team5, team3 = team4. 

Number of teams = 2

Number of arrangements for 2 teams = 2!

Therefore number of ways = (4C2 × 2C2)/2! = 3

So answer is 3 ways when 2n = 4.

Put n = 2 in options and option (c) is satisfied.

Derivation =>

2n members; n teams are possible.

Firstly from 2n select any 2 members = 2nC2 

From remaining 2n-2 select any 2 members = (2n-2)C2 

Similarly go on and and at last select 2 members from 2 = 2C2 

Number of teams = n

Number of arrangements for n teams = n!

So number of ways = (2nC2 × (2n-2)C2 × ........ × 2C2)/n!

 = (2n!) / (2^n × n!)

= option (c)

Comments

Good explanation!!

Answer 4

We need to divide $2n$ members of the club into $n$ disjoint teams of $2$ members each means, $i \ne j \Longrightarrow \text{Team}_i \cap \text{Team}_j = \phi$ and $|\text{Team}_k| = 2$. 

Let $A = \{a_1,a_2, \dots, a_{2n}\}$ be the members of the club. 

Let $\pi(A)$ be the permutation of $A$, such that total possible permutation be $(2n)!$. Each permutation can be represented as $\pi_i(A)$ for $1 \le i \le 2n$. 

For example, $n=3$

One such $\pi_k(A) = a_3a_6a_1a_4a_5a_2$, then we select first two $a_i$'s and make a team of them, then we select next two $a_i$'s and make a team of them and so on. 

$$\begin{array}{|c|c|c|}
\hline
a_3a_6 & a_1a_4 & a_5a_2\\
\hline
\text{Team}_1 & \text{Team}_2 & \text{Team}_3 \\
\hline
\end{array}$$ 

Now $\pi_j(A) = a_6a_3a_1a_4a_5a_2$,

$$\begin{array}{|c|c|c|}
\hline
a_6a_3 & a_1a_4 & a_5a_2\\
\hline
\text{Team}_1 & \text{Team}_2 & \text{Team}_3 \\
\hline
\end{array}$$ 

Though $\pi_k(A) \neq \pi_j(A)$, yet the teams formed using $\pi_k(A)$ and $\pi_j(A)$ are same!! Since, order of members in the team doesn't matter. Hence, we should divide by $2$ for every $\text{Team}_i$. 

In total there are going to be $(2n)!$ such sequences of $2n$ members and $n$ such teams made on every such sequence, and for every such team we are dividing the total ways by $2$. 

$$(2n)!\frac{1}{2^n}$$

We are also given one more condition to satisfy, i.e. "The teams are not labelled". Until now, we have a working solution for labelled teams, so now lets take $\pi_p(A), \pi_q(A)$ for the above mentioned example to understand this condition.

$\pi_p(A) = a_1a_4a_3a_6a_5a_2$

$\pi_q(A) = a_5a_2a_1a_4a_3a_6$

$$\begin{array}{|c|c|c|c|}
\hline
\pi_k(A) & a_3a_6 & a_1a_4 & a_5a_2\\
\hline
\pi_p(A) & a_1a_4 & a_3a_6 & a_5a_2\\
\hline
\pi_q(A) & a_5a_2 & a_1a_4 & a_3a_6\\
\hline
\vdots & a_5a_2 & a_3a_6 & a_1a_4\\
\hline
\vdots & a_1a_4 & a_5a_2 & a_3a_6\\
\hline
\vdots & a_3a_6 & a_5a_2 & a_1a_4\\
\hline
& \text{Team}_1 & \text{Team}_2 & \text{Team}_3 \\
\hline
\end{array}$$ 

This shows that members partition into team matters and not the team order itself. Above $6$ ways are effectively $1$ way only, hence we need to divide total ways with $n!$ since there are $n$ teams.

Final answer would be 
$$\dfrac{(2n)!}{2^n (n)!}$$ 

 $\textbf{Option (C) is correct}$.