We begin with an apparently simpler problem, called the relaxed
ménage problem, which asks for the number of ways of seating
couples around a circular table, so that no one sits next to his or her
partner. This is nearly the same as the ménage problem, only now we
have relaxed the requirement that men and women alternate.
To determine , we begin with the set
of all
ways of
seating the
individuals around the table, and use inclusion-exclusion
on the set of couples who end up sitting together. Let us
call the elements of
seatings, and let us denote by
the number
of seatings under which some specified set of
couples (and
possibly some other couples) end up sitting together. Clearly,
does not depend on the particular set of
couples we choose, and so,
by the principle of inclusion and exclusion, we have
To finish the enumeration, we must compute . Assume
. Let
denote the number of ways of placing
non-overlapping unlabeled
dominos on
vertices arranged in a circle.
(See Figure 1.)
Figure 1: Non-overlapping dominos
Then
(Decide where the couples go, and which couple goes where, and
which partner
takes which seat, and where the
individuals go.) So now we
have only to
compute the
's. This is a routine combinatorial problem. The
answer is
(See Ryser [11], pp. 33-34, or Exercise 1 below). This 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 1.