For the ménage problem, we proceed just as before, only now we
restrict the set of seatings to those where men and women
alternate. The number of these seatings is
: two ways to
choose which seats are for men and which for women;
ways to
seat the men in the men's seats;
ways to seat the women in the
women's seats. Just as before, we have
where denotes the number of alternating seatings under which a
specified set of
couples all end up sitting together. This time we
have
(Decide which are men's seats and which women's, where the
couples go, which couple goes where, and where the
men and
women go.) Plugging in for
yields
Plugging this expression for into the formula for
above, we
get
By symmetry, we know that must be divisible by
. Pulling
this factor out
in front, we can write
The first few values of are shown in Table 2.