Why does stable matching without Gale-Shapely takes n! steps
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!$.