夫妻對入座問題

夫妻對入座問題

夫妻對入座問題又叫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號位置的丈夫的編號為ai,按要求
和i+1(當
時),
和1,即要求排列
使得上表中
與同列中前兩行之數無一相重,記這樣的排列
的總數為Un,Un稱為夫妻數,
n≥2,從而
,易知,

相關定理及證明

套用容斥原理容易解決這個似乎很困難的問題。
定理 n對夫妻圍圓桌(2n個座位已編號)而坐,男女相間,夫妻不相鄰,則不同的坐法數為
Mn稱為夫妻數。
證明:以S表示n對夫妻男女相間地圍圓桌而坐的全部不同坐法所成之集,則
,設s∈S,若在坐法s中,第
對夫妻相鄰而坐,則稱s具有性質ai,對任意
個正整數
,以
表示S中同時具有性質
的元素個數,下面求
先設k<n,可依如下4個步驟去作出具有性質
的坐法。
步驟1:設不在集合
中的最小正整數為j,安排第j對夫妻的丈夫Aj入座(這樣男女座位編號的奇偶性就確定了),有2n種方法。
步驟2:安排第
對夫妻入座,使得每對夫妻相鄰而坐,因為男女座位編號的奇偶性已確定了,所以每對夫妻可看成一個人,他們坐的兩個座位可看成一個座位,故完成步驟2的方法數等於從
個座位中選取k個座位,再把k個人安排在這k個座位上的方法數,為
步驟3:安排餘下的n-k-1個男人入座,有
種方法。
步驟4:安排餘下的n-k個女人入座,有
種方法。
由乘法原則,
因為
,故當k=n時上式仍成立,於是由容斥原理,S中不具有
中任一個性質的元素個數,即所求的夫妻數為

相關詞條

熱門詞條

聯絡我們