Remove a perfect matching from a complete bipartite graph \( K_{n,n} \) (forming a crown graph), and count the number of (directed) Hamiltonian cycles in the remaining graph. Alternatively, remove a Hamiltonian cycle from the same complete bipartite graph, and count the number of perfect matchings in the remaining graph. The two sequences of numbers generated in this way are almost the same! (They differ by a factor of \( (n-1)! \) from each other.) Perhaps this will be more surprising if I list the smaller of the two sequences of numbers (the number of matchings in the graph with the cycle removed) to show that they're not something familiar like powers of two or factorials. They are (starting at \( n=3 \)):

\[ 1, 2, 13, 80, 579, 4738, 43387, 439792, 4890741, 59216642, 775596313, \dots \]

Both sets of numbers come up in the problème des ménages concerning seating plans for n couples so that men and women alternate and nobody sits next to his or her partner. The numbers of matchings are the ménage numbers describing ways of arranging the men once the women have already been seated, while the larger numbers of Hamiltonian cycles count seating plans in which everyone is free to move but only the cyclic order of the participants, and not their precise placement into chairs, is significant.

I'm not sure at this point whether the symmetry between the two graph-theoretic ways of describing these numbers is a coincidence or a piece of some sort of deeper duality.




Comments:

None:
2009-01-14T18:39:39Z

I'm not sure if this is the explanation you're looking for, but in \( K_{n,n} \), there are \( n! \) perfect matchings and \( n!(n-1)! \) directed Hamiltonian cycles, and the incidence relation between matchings and cycles is preserved by a symmetry group that acts transitively on both (though not at the same time).

None:
2009-01-14T18:50:47Z

(insert rest of double counting argument here)

11011110:
2009-01-14T19:07:45Z

Yes, that sounds like a good way of explaining it.