De bruijn Graph for Married Couples

If you find our commentaries useful, please feel free to press the donate button on the right sidebar, and your generous contribution will be acknowledged in the table at the bottom of the page.

You can follow us on twitter – @homolog_us.



We address the problemof enumeration of seating arrangements ofmarried couples around a circular table such that no spouses seat next to each other and no k consecutive persons are of the same gender. While the case of k = 2 corresponds to the classical probl`eme des m´enages with a well-studied solution, no closed-form expression for number of arrangements is known when k=3.

We propose a novel approach to this type of problems based on enumeration of circuits in certain algebraically weighted de Bruijn graphs. Our approach leads to a new expression for the menage numbers and their exponential generating function, and allows one to efficiently compute the number of seating arrangements in general cases. We work out all the details for k = 3.

Heroes and Heroines of New Media--2015

Our blog is deeply honored by the generous contribution of the following readers. Without their patronage, this site would go away.

Outstandingly Generous:   
Amemiya C. Schnable J. ... Osipowski P.
Shen M. Furness M. Graur D. Diesh C.
Amemiya C.      

We are also looking for subscribers to get help to finish the tutorials. Please see this post for details.

Leave a Reply




You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Web Analytics