How Many Marriages in a Bipartite Graphs? Given two disjoint sets, say $M$ and $W$, both of size $n$, I want to compute how many possibilities of marriage exist.
For example, when $n=1$, there are two marriages only: either $m_1-w_1$ or $\emptyset$, denoting no marriage.
When $n=2$, there are 7: ($m_1-w_1,m_2-w_2$), ($m_1-w_2,m_2-w_1$), $m_1-w_1$, $m_1-w_2$, $m_2-w_1$, $m_2-w_2$, and $\emptyset$.
When $n=3$, there are 61 (6 with 3 couples, 36 with 2 couples only, 18 with 1 couple only, and 1 with no couple).
Which is the answer for an arbitrary $n$? I have been thinking about it. If I get an answer soon I will post it but yet I see no pattern. Please answer only if you have given the question some thought, it is by no means a trivial question, at least in my humble opinion.
Thanks for intuitive answers,

To form exactly $k$ couples, select $\binom nk$ partners on either side and marry them in $k!$ different ways. Thus the total is
$$
\sum_{k=0}^n\binom nk^2k!\;.
$$
This is OEIS sequence A002720 (lots of information in that entry). According to Wolfram|Alpha, it's also $U(-n,1,-1)$, where $U$ is the confluent hypergeometric function of the second kind.
Some of your counts are wrong. For $n=3$, there are only $18$ options with $2$ couples and $9$ with $1$ couple; the total is $34$.
