夫妻對入座問題

夫妻對入座問題又叫Menage問題、夫妻問題(problem of mate)，是一種圓排列問題，呂卡(F.-É.-A.Lucas)於1891年提出的一個趣味組合問題，有n個丈夫和他們的妻子圍坐在一張圓桌旁，要使男女依次交錯入坐，且使沒有一個妻子坐在她的丈夫旁邊，求這樣的入坐方法總數T(n)，這就是夫妻問題。

基本介紹

• 中文名：夫妻對入座問題
• 外文名：problem of mate
• 別名：Menage問題、夫妻問題
• 簡介：一種圓排列問題
• 提出者：呂卡(F.-É.-A.Lucas)

基本介紹

Lucas(魯卡斯，法國數學家，1842-1891)曾提出如下的“夫妻問題”：今需安排n對夫妻圍圓桌(2n個座位已編號)而坐，男女相間，夫妻不相鄰，問有多少種不同的安排座位方法?

安排座點陣圖

不妨讓婦女先入坐，共有2n!種方式，然後丈夫再入坐。設婦女已入坐並按環形順序給以1，2，…，n的編號，把第i號婦女的丈夫編號為第i號，把第i號婦女和第i+1號婦女間的位置稱為第i號位置 ，第n號和第1號婦女間的位置稱為第n號位置.現假定男子也已入坐，坐在第i號位置的丈夫的編號為a_i，按要求 和i+1(當 時)， 和1，即要求排列 使得上表中 與同列中前兩行之數無一相重，記這樣的排列 的總數為U_n，U_n稱為夫妻數，

n≥2，從而 ，易知， 。

相關定理及證明

套用容斥原理容易解決這個似乎很困難的問題。

定理 n對夫妻圍圓桌(2n個座位已編號)而坐，男女相間，夫妻不相鄰，則不同的坐法數為

M_n稱為夫妻數。

證明：以S表示n對夫妻男女相間地圍圓桌而坐的全部不同坐法所成之集，則 ，設s∈S，若在坐法s中，第 對夫妻相鄰而坐，則稱s具有性質a_i，對任意 個正整數 ，以 表示S中同時具有性質 的元素個數，下面求 。

先設k<n，可依如下4個步驟去作出具有性質 的坐法。

步驟1：設不在集合 中的最小正整數為j，安排第j對夫妻的丈夫A_j入座(這樣男女座位編號的奇偶性就確定了)，有2n種方法。

步驟2：安排第 對夫妻入座，使得每對夫妻相鄰而坐，因為男女座位編號的奇偶性已確定了，所以每對夫妻可看成一個人，他們坐的兩個座位可看成一個座位，故完成步驟2的方法數等於從 個座位中選取k個座位，再把k個人安排在這k個座位上的方法數，為 。

步驟3：安排餘下的n-k-1個男人入座，有種方法。

步驟4：安排餘下的n-k個女人入座，有種方法。

由乘法原則，

因為 ，故當k=n時上式仍成立，於是由容斥原理，S中不具有 中任一個性質的元素個數，即所求的夫妻數為