28

A hundred years ago, if you had $k$ men and $k$ women and wanted to marry them all off in pairs, it was easy to see that there are exactly $k!$ ways to do that.

Today, however, societal standards have evolved, and many countries now recognize same-sex marriages. Mathematically we can model that by saying that men can now be brides and women can now be grooms. Each wedding still needs one bride and one groom, however, if only because one of the spouses needs to be listed in the left rubric on the marriage certificate and the other on the right.

How many ways are there now to marry off our $2k$ persons in pairs? A bit of elementary combinatorics and algebra shows that we have $$ \tag{$\dagger$} \frac{(2k)!}{k!} = (k+1)\cdot(k+2)\cdot(k+3)\cdots(2k-2)\cdot (2k-1) \cdot 2k $$ possibilities, when we want to remember who's the bride and who's the groom in each couple.

However, every way I can think of to justify this formula depends on first counting a larger number of somethings, and then dividing out some factors to account for overcounting. (If we justify $(2k)!/k!$ as $\binom{2k}{k}k!$ the division is hidden inside the argument that $\binom nk=\frac{n}{k!(n-k)!}$).

Question: Is there an intuitive way to explain the result $\text{($\dagger$)}$ where each of the $k$ factors have a discrete meaning? Or, in other words, an explicit description of a bijection from the set $$ \{1,2,\ldots,k,k+1\}\times\{1,2,\ldots,k,k+1,k+2\}\times\cdots\times\{1,2,\ldots,2k\} $$ to the set of possible matchings?

hmakholm left over Monica
  • 286,031
  • 3
    There's a very clean description as $2^k\cdot(2k-1)!!$ that counts a smaller number of somethings (unordered pairings) and then multiplies by the $2^k$ ways of assigning a preferred partner per couple... – Steven Stadnicki Aug 27 '15 at 21:17
  • 2
    Line up the people in order of student number. The first person in the list chooses a mate, and they flip a coin to decide who will be the bride. The first person not so far chosen does the same, and so on. So we get $(2k-1)(2)(2k-3)(2)\dots$. – André Nicolas Aug 27 '15 at 21:23
  • @StevenStadnicki That's what I was thinking, but how do you show that $2^k\cdot(2k-1)!!=(k+1)(k+1)\cdots(2k)$? I'd just multiply both sides by $k!$ but then we're back to "counting something larger and dividing out some factors". – bof Aug 27 '15 at 21:24
  • @HenningMakholm: No, you need to multiply some of them by several factors of $2$. It's rather non-obvious that you end up with $(2k)!/k!$. – joriki Aug 27 '15 at 21:26
  • @joriki: Hmm, you're right. Good thing I didn't accept that as an answer yet. :P – hmakholm left over Monica Aug 27 '15 at 21:27

3 Answers3

27

Put everyone in a row, choose the $k$ brides (with order) and then marry the $j$-th bride chosen to the $j$-th groom left standing.

joriki
  • 238,052
6

Let's assume the individuals are named by natural numbers between $1$ and $2k$. Order the happy couples as $(b_1, g_1), (b_2, g_2), \ldots (b_k, g_k)$ with $b_1 < b_2 < \ldots < b_k$. Then you have $2k$ choices for $g_1$, $2k-1$ choices for $g_2$ and so on giving $2k(2k-1)\ldots (k+2)(k+1)$ possibilities for the $g_i$. When you know the $g_i$ the $b_i$ are determined by the ordering.

Rob Arthan
  • 48,577
  • 4
    My hat goes off to joriki for coming up with such a neat way of describing the same solution while I was busy typing up lists of pairs of subscripted variables. – Rob Arthan Aug 27 '15 at 21:52
  • 5
    The solutions may be the same, but I found yours a little easier to understand. – user84413 Aug 27 '15 at 23:12
4

To flesh out my comment a bit: we can count the $(2k-1)!!$ unordered pairings simply: line the $2k$ people up and number them. Now, there are $(2k-1)$ people that person 1 can be married to; there are $(2k-3)$ people that the next-smallest unmarried person can be married to; etc. Once we have our couples, we can assign a 'preferred partner' to each one independently, giving $2^k$ choices (this can be expressed easily in boolean form as 'is the smaller or larger of our pair the preferred?'). Of course from here, showing that $2^k(2k-1)!!=\frac{(2k)!}{k!}$ is a little trickier - one can pair off factors, but that's a surprisingly painful process.

Steven Stadnicki
  • 51,746