[科普中國(guó)]-夫妻對(duì)入座問(wèn)題

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

基本介紹Lucas(魯卡斯，法國(guó)數(shù)學(xué)家，1842-1891)曾提出如下的“夫妻問(wèn)題”：今需安排n對(duì)夫妻圍圓桌(2n個(gè)座位已編號(hào))而坐，男女相間，夫妻不相鄰，問(wèn)有多少種不同的安排座位方法?

不妨讓婦女先入坐，共有2n!種方式，然后丈夫再入坐。設(shè)婦女已入坐并按環(huán)形順序給以1，2，…，n的編號(hào)，把第i號(hào)婦女的丈夫編號(hào)為第i號(hào)，把第i號(hào)婦女和第i+1號(hào)婦女間的位置稱(chēng)為第i號(hào)位置 ，第n號(hào)和第1號(hào)婦女間的位置稱(chēng)為第n號(hào)位置.現(xiàn)假定男子也已入坐，坐在第i號(hào)位置的丈夫的編號(hào)為ai，按要求 和i+1(當(dāng) 時(shí))， 和1，即要求排列 使得上表中 與同列中前兩行之?dāng)?shù)無(wú)一相重，記這樣的排列 的總數(shù)為Un，Un稱(chēng)為夫妻數(shù)，

n≥2，從而 ，易知， 。

相關(guān)定理及證明應(yīng)用容斥原理容易解決這個(gè)似乎很困難的問(wèn)題1。

定理 n對(duì)夫妻圍圓桌(2n個(gè)座位已編號(hào))而坐，男女相間，夫妻不相鄰，則不同的坐法數(shù)為

Mn稱(chēng)為夫妻數(shù)。

證明：以S表示n對(duì)夫妻男女相間地圍圓桌而坐的全部不同坐法所成之集，則 ，設(shè)s∈S，若在坐法s中，第 對(duì)夫妻相鄰而坐，則稱(chēng)s具有性質(zhì)ai，對(duì)任意 個(gè)正整數(shù) ，以 表示S中同時(shí)具有性質(zhì) 的元素個(gè)數(shù)，下面求 。

先設(shè)k