discordant permutation | Lucas' married couples problem | ménage number | ménage problem

Also called the ménage problem. In how many ways can n married couples be seated around a circular table in such a manner than there is always one man between two women and none of the men is next to his own wife? The solution uses discordant permutations and was solved by Laisant, Moreau, and Taylor. The solution for n>1 can be given in terms of Laisant's recurrence formula (n - 1) A_(n + 1) = (n^2 - 1) A_n + (n + 1) A_(n - 1) + 4(-1)^n, with A_2 = 0 and A_3 = 1.

Laisant's recurrence formula | rooks problem