基本介紹
- 中文名：圍坐問題
- 外文名：menage problem
- 提出者：盧卡斯
- 提出時間：1891年
- 適用領域：組合數學
- 套用學科：數學
具體表述,問題意義,圖夏爾等式,證明過程,理論解釋,
具體表述
在這之後，Peter Guthrie Tait使用扭結理論初步解決了這一問題。
問題結果被記錄在A059375（OEIS）中。（依次為12, 96, 3120, 115200, 5836320, 382072320, 31488549120, ..）
該問題的具體表述如下：
（1）N對夫妻圍圓桌而坐且夫妻相鄰的方案數。
（2）N對夫妻圍圓桌而坐且夫妻不相鄰的方案數。
（3）N對夫妻圍圈而坐，男女相間，且夫妻不相鄰的方案數。
問題意義
這個問題的提出，不僅僅是與禮節套用有關，而且和扭結理論有著很強的相關性。
除此之外，這個問題和圖理論有著密切的關係：在特定圖的族中計算出匹配數和哈密頓圈。
圖夏爾等式
圖夏爾（Touchard (1934)）給出了一個等式：設Mn表示n對夫妻圍坐的方案數，那么
當然，Wyman & Moser在1958年給出了另一個包含切比雪夫多項式的Mn表達形式，在這裡不再贅述。
證明過程
Bogart和Doyle在1986的工作採用首先尋找所有女士的排座方式之後再計數的方法解決了Menage數的問題。這樣問題就轉化為，讓所有男士都不與自己搭檔相鄰的坐法。不過，Bogart和Doyle同樣也表示，圖夏爾的等式可能是最能直接表達出所有排座方式的辦法。
首先，對於女士來說總計有2×n! 中坐法，因為每個座位都有能坐男士或者女士，並且n個人的坐法是n!種。因此對於女士來說，共有：
種方案。這一等式和圖夏爾的等式僅僅相差了一個2×n!。這個方案的序列與圖夏爾的序列相比明顯偏小，從n=3時序列為：1, 2, 13, 80, 579, 4738, 43387, 439792, ... (A000179inOEIS)。這個序列被成為Menage數序列。
這一等式滿足如下的遞推關係：
更簡單的4階遞推關係如下：
這樣，序列的每個數都很容易被計算出來。
（1）N對夫妻圍圓桌而坐且夫妻相鄰的方案數。
首先將n對夫妻視為一個單位，考慮其圓排列，之後再考慮n對夫妻之間的排列。
根據乘法法則，方案數為：
。
（2）N對夫妻圍圓桌而坐且夫妻不相鄰的方案數。
n對夫妻圍圓桌，沒有約束的方案數為
,
由容斥原理，設
表示第i對夫妻相鄰而坐的集合：
這種情況總計有：
個。
此外還有：
，這種情況總計有
.
因此不相鄰的方案數為:
（3）n對夫妻圍圓桌而坐，男女相間，且夫妻不相鄰有多少種方案。
不失一般性，我們先排女賓，方案數為
，對於任意這樣的方案數，順時針給每個女賓以編號1,2,...,n。
設第i號與第i+1號女賓之間的位置為第i號位置，
,第n號女賓與第1號之間的位置為第n號位置，設第i號女賓的丈夫的編號也在第i號，
,讓n個男賓做到上述編號的第n個位置上。
設
是坐在第i號位置上的男賓，則
.
上述這樣的要求也即要求在下面3行n列的排列中每列都無相同元素。
圍坐問題
滿足這樣的限制的排練
稱為二重錯排。
設這樣的錯排的個數為
,原問題也就是
.
也就是從（1,2）（2,3）...(n-1,n)（n,1）這n對數的k對中各取一數，且互不相同的取法的計數。
這就相當與從1,2,2,3,3,4，...,n-1,n-1,n,n,1中取k個互不相鄰數的組合的計數，條件是（1）任意兩個數在數列中不相鄰 （2）首尾的1不能同時取。
無重複不相鄰的組合計數為
,在這裡為
.
不滿足該條件的情況：在收尾兩列各取出1後，選取數為
。
因此總計有：
圍坐問題
理論解釋
圍坐問題可以很容易的用圖理論解釋，也就是皇冠圖中的有向哈密頓圈。
皇冠圖是通過從一個完整的二分圖Kn，n的一個完美匹配形成。它有兩種顏色的2n個頂點，每個頂點都有一個顏色，但其它顏色與相鄰點不同。在圍坐問題的情況下，該圖的頂點代表男性和女性，並且邊的存在表示男士和女士可以相鄰而坐。
圍坐問題
該圖是通過一個完整的二分圖的情形中刪除匹配而形成的。任何有效的座位安排都可以通過在圓的周圍形成的序列，形成一個漢密爾頓的周期在該圖進行說明。但是，有兩個哈密頓周期考慮，如果它們連線相同的頂點在相同的循環順序不分開始頂點，而在圍坐問題的起始位置被認為是顯著是等同的。舉例來說：如果在愛麗絲的茶話會，所有的客人由一個座轉移他們的位置，我們認為，即使它是由在同一周期中，他們也被描述在的不同的座位布置。因此，有向哈密頓周期在一個冠圖形的數目比圍坐數小一個2n因子。 （因此，當以n = 3）在這些圖的周期數序列是
2，12，312，9600，416880，23879520，1749363840，...（OEIS A094047）。
該問題的第二個圖論描述也是可能的。一旦女人已經落座，餘下的人可能安排座位，可以描述為從一個完整的二分圖中除去一個漢密爾頓的周期形成一個曲線完美匹配。圖形有邊緣連線到他人，邊的取消對應于禁止男子坐在任一毗鄰他們妻子的位置。在二分圖計數的匹配的問題，可以使用某些0-1矩陣的永久解決。在圍坐問題的情況下，從這一方法產生的矩陣是循環矩陣。[7]
