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

This problem counts the number of perfect matchings in complete graph on 2n vertices. You can list down the numbers (vertices) as follows and " - " between the numbers indicate edges. The following arrangement represents one of the perfect matchings in complete graph on 2n vertices. If we permute the following matching edges in n! ways the matching doesnt change. Also, the matching remains unchanged if the vertices of a matching edge are permuted. Hence, there are (2n)! / 2^n * n! distinct perfect matchings.

1-2  3-4 ............................................. (2n-1) - (2n)

Answer 2

It is similar to number of ways you can do maximum matching in a complete bipartite graph

Shall I need to further say anything?
;)

Comments

It is similar to number of ways you can do maximum matching in a complete bipartite graph

Not Maximum matching  , Perfect matching instead.

Moreover it is not complete Bipartite graph , just Simple complete graph (with even number of vertices).

Number of perfect matching in a complete Bipartite graph is N!.