There are n men and n women. I am unable to understand how stable matching done by simply searching through all the matchings takes n! steps i.e., I cannot figure out why there are n! matchings possible.
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ Try small cases to see what's going on, for example $n = 1,2,3$. $\endgroup$– Yuval FilmusSep 3, 2013 at 19:53
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Suppose that the group of men is $m_1,\ldots,m_n$ and the group of women is $w_1,\ldots,w_n$. Suppose that man $m_i$ is matched to woman $w_{c_i}$. Then the matching can be described by the sequence $c_1,\ldots,c_n$. Each $c_i$ is in $\{1,\ldots,n\}$, and $c_i \neq c_j$ for $i \neq j$. So $c_1,\ldots,c_n$ is a permutation of $\{1,\ldots,n\}$, of which there are $n!$.
answered Sep 3, 2013 at 19:53
$\begingroup$
$\endgroup$
@Yuval Filmus's answer is perfect.
another way to is think of it the as the following problem:
in how many ways can n men sit on n chairs?
(think of chairs analogous to women, the "chairs" do not move.. it's the men who keep shifting here)..
so it's basically just any valid permutations among them... and that's $n!$
