[seqfan] Re: Ménage problem with a fixed couple

Vladimir Shevelev shevelev at bgu.ac.il
Sun Nov 13 11:52:20 CET 2016

Dear SeqFans,

I am very pleased to inform you that our with Peter 
Moses paper, including sequences A258664- A258667,
A258673 and A259212, has been published in
http://www.integers-ejcnt.org/vol16.html, paper A72

Best regards,

From: SeqFan [seqfan-bounces at list.seqfan.eu] on behalf of Vladimir Shevelev [shevelev at exchange.bgu.ac.il]
Sent: 01 July 2015 14:23
To: seqfan at list.seqfan.eu
Subject: [seqfan] Ménage problem with a fixed couple

Dear SeqFans,

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.

Best regards,


Seqfan Mailing list - http://list.seqfan.eu/

More information about the SeqFan mailing list