Roommates Matching - June 15

[Amit Goyal]

There is a single set of 2n people who can be matched in pairs (to be roommates
in college dormitory, or partners in paddling a canoe). An outcome
is a matching, which is a partition of the people into pairs. (If the set of people
is say {a, b, c, d} then an example of a matching is: ((c,a), (b,d)) i.e c
and a are matched and b and d are matched.)
Find the total number of matchings/outcomes for 2n people.

[anon_econ]

(2n)!/n!*2^n

[Amit Goyal]

Thats right.

[Amit Goyal]

Now do the following:
There is a single set of 4 people who can be matched in pairs. Each
person in the set ranks the 3 others in order of preference. A stable matching is a matching
such that no two persons who are not roommates both prefer each other to
their actual partners.
Consider four people: a, b, c and d, with the following preferences:
P(a) = b, c, d (i.e. a prefers b to c to d)
P(b) = c, a, d
P(c) = a, b, d
P(d) = a, b, c
Answer the following based on above information:
Find the total number of stable matchings for the case of four people
when the preferences are as given above.

[anon_econ]

I'm getting zero

[Amit Goyal]

Well done :-)

[ritu]

hi vasudha:)
could u pls tell me how u got the answer.....i got ekdum galat answer:(2n-1)^2n/2  :(

[anon_econ]

Hello ritu. First suppose the teams were numbered. Then the 1st team can be chosen in (2n)C2 ways. The next one in (2n-2)C2 ways and so on. n teams hv 2 b chosen in all. If u multiple them u'll b left with (2n)!/2^n. Now if u give up the assumption of the teams being numbered u'll hv 2 divide by n! bcoz the teams could be shuffled among themselves in n! ways. For eg if a,b,c,d are the people, then 4C2*2C2 would give u 6. Now u must divide by 2! bcoz u know that team 1=a,b; team 2=c,d is not different from team 1=c,d; team 2=a,b.

[ritu]

hi vasudha...i got it till 2n!/2^n....and also the example but why do we divide by n! and not just 2...??????

[Amit Goyal]

Ritu,

Think about it in this way:
 
First you arrange 1, 2, ... , 2n in a row. And then pair the ones in this way: the first two in the row are paired together, third and forth are paired together, fifth and sixth are together and so on. There are (2n)! arrangements.
So, if 2n = 4, We know how to list out those 2n! orderings.
Now all the orderings listed below represent the same matching so they should be counted as one:
12 - 34      34 - 12
12 - 43      43 - 12
21 - 34      34 - 21
21 - 43      43 - 21
The above list of 8 orderings represent the same matching.
So, the number 2n! needs to be adjusted for two types: First, for a given sequence of pairs, the members of a pair can be ordered in 2 ways and hence with n pairs, the number needs to be divided by 2^n. Second, there are n! ways in which pairs can be arranged. So the number needs to be divided further by n!.
And hence, the number: (2n)!/(n!(2^n)) distinct matchings.

[tim]

cn v also say ..v r dividing it by 2^n bcos  v hv to make pairs and since there r 2n ppl so 2^n pairs wud b formed.

[aditi5000]

Oh so it is similar to the case of combinations of unique items.. If anything is repeating we divide it by the number of times its repeating to avoid double counting - thank you :)