Why does stable matching without Gale-Shapely takes n! steps

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.

• Try small cases to see what's going on, for example $n = 1,2,3$. – Yuval Filmus Sep 3 '13 at 19:53

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!$.
so it's basically just any valid permutations among them... and that's $n!$