[科普中国]-夫妻对入座问题

夫妻对入座问题又叫Menage问题、夫妻问题(problem of mate)，是一种圆排列问题，吕卡(F.-É.-A.Lucas)于1891年提出的一个趣味组合问题，有n个丈夫和他们的妻子围坐在一张圆桌旁，要使男女依次交错入坐，且使没有一个妻子坐在她的丈夫旁边，求这样的入坐方法总数T(n)，这就是夫妻问题。

基本介绍Lucas(鲁卡斯，法国数学家，1842-1891)曾提出如下的“夫妻问题”：今需安排n对夫妻围圆桌(2n个座位已编号)而坐，男女相间，夫妻不相邻，问有多少种不同的安排座位方法?

不妨让妇女先入坐，共有2n!种方式，然后丈夫再入坐。设妇女已入坐并按环形顺序给以1，2，…，n的编号，把第i号妇女的丈夫编号为第i号，把第i号妇女和第i+1号妇女间的位置称为第i号位置 ，第n号和第1号妇女间的位置称为第n号位置.现假定男子也已入坐，坐在第i号位置的丈夫的编号为ai，按要求 和i+1(当 时)， 和1，即要求排列 使得上表中 与同列中前两行之数无一相重，记这样的排列 的总数为Un，Un称为夫妻数，

n≥2，从而 ，易知， 。

相关定理及证明应用容斥原理容易解决这个似乎很困难的问题1。

定理 n对夫妻围圆桌(2n个座位已编号)而坐，男女相间，夫妻不相邻，则不同的坐法数为

Mn称为夫妻数。

证明：以S表示n对夫妻男女相间地围圆桌而坐的全部不同坐法所成之集，则 ，设s∈S，若在坐法s中，第 对夫妻相邻而坐，则称s具有性质ai，对任意 个正整数 ，以 表示S中同时具有性质 的元素个数，下面求 。

先设k