[seqfan] Ménage problem with a fixed couple
shevelev at bgu.ac.il
Wed Jul 1 13:23:26 CEST 2015
According to Lucas' ménage problem (1891), we need to find the
number of ways of seating n married couples at 2*n chairs around
a circular table, men and women in alternate positions, so that no
husband is next to his wife.
Consider this problem with a fixed couple M&W, such that M takes
a place that there are d seats clockwise from W's chair. By rules of
the ménage problem, d cannot equal 1 or 2*n-1. It is clear that M&W
can take their places in 2*n ways. After that, the other n-1 women
can take their places in (n-1)! ways. Thus the number of seating
all n married couples is 2*n!*N_d(n), where N_d(n) means the
number of ways to seat the other men.
I and Peter submitted in OEIS 5 new sequences for N_d(n) when
d=3,5,7,9 and 11. They are A258664-A258667 and A258673. In the
last one, I give also a general formula for any d ( the proof of which,
using a rook technique, one can find in our link). See also A259212
and new comments in A000179, A000271 and A000904.
More information about the SeqFan