Combinatorics, The Marriage Problem

The Marriage Problem

The marriage problem asks how many ways n couples can sit at a round table, such that sexes alternate, and nobody sits by his/her mate. Although recursive solutions exist, deriving a simple formula is notoriously difficult.

Sometimes the alternating restriction is dropped in order to simplify the problem. In this case we can compute the number of permutations using inclusion exclusion. To seat at least i couples together, select i couples out of n, order them male-female or female-male, and place them at the table along with the other 2n-2i people. This yields a formula:

(n:i) × 2ⁱ × (2n-i-1)!

Take the alternating sum of this expression, as i runs from 1 to n, to find the number of permutations with at least one couple seated together. Subtract this from (n-1)! to get the no-couple permutations.