夫妻圍梯形桌入座問題*

趙紅濤，姜書麗

(華北電力大學(xué)數(shù)理系，北京 102206)

摘要：將Lucas夫妻圓桌問題推廣為夫妻梯形桌問題(對夫妻圍兩邊分別有1個和2n-1個座位的梯形桌入座)，得出該坐法的計數(shù)公式.

關(guān)鍵詞：圓桌問題；直線桌問題；梯形桌問題

文章編號：1007-2985(2015)06-0001-04

中圖分類號：O157.2文獻標志碼：A

DOI:10.3969/j.cnki.jdxb.2015.06.001

收稿日期：*2015-06-04

基金項目：國家自然科學(xué)基金資助項目(10901051,11201143)；中央高校基本科研業(yè)務(wù)費專項資金資助(13MS38)；華北電力大學(xué)教改項目資助(《高等代數(shù)》在數(shù)學(xué)建模中的應(yīng)用)

作者簡介：趙紅濤(1978—)，男，河北滄縣人，華北電力大學(xué)數(shù)理系副教授，博士，主要從事組合數(shù)學(xué)研究.

n對夫妻圍圓桌入座問題是組合數(shù)學(xué)中一個非常著名的問題，學(xué)者們[1-5]用不同的方法給出了答案.趙立寬運用文獻中創(chuàng)建的“積和式”方法解決了n對夫妻沿直線桌入座問題的坐法計數(shù)，但文中并沒有給出坐法計數(shù)的具體計算過程.筆者給出了n對夫妻沿直線桌入座坐法計數(shù)的具體計算過程，并將n對夫妻圍圓桌入座問題推廣到n對夫妻圍梯形桌入座問題，即n對夫妻圍兩邊分別有1個和2n-1個座位的梯形桌入座 (n≥1).

1Pn的計算

文中所有入座問題的座位都已按順序編號，不再一一贅述. 為了書寫方便，定義如下符號：Mn為n對夫妻圍圓桌入座問題的坐法計數(shù)；Pn為n對夫妻沿直線桌入座問題的坐法計數(shù)；Q1,n為n對夫妻圍兩邊分別有1個和2n-1個座位的梯形桌入座問題的坐法計數(shù).

證明從文獻已知

(1)

下面利用積和式給出Mn的另外一種表達方式.分3個步驟：

(ⅰ)確定座位編號為1的位置入座人的性別，有2種可能；

(ⅱ)不妨設(shè)男士坐在奇數(shù)編號的座位上，讓n個男士入座有n!種坐法；

(ⅲ)對于男士入座的n!種坐法的每一種情況，給已經(jīng)入座的n位男士按座位號的順序分別標號1,2,…,n，他們的妻子對應(yīng)編號1′,2′,…,n′.標號為i′的女士若可以坐在標號為j的男士的右邊則記為aij=1，否則,記為aij=0.那么，n位女士的坐法對應(yīng)如下矩陣：

根據(jù)乘法原則圍圓桌入座問題方法計數(shù)

Mn=2·n!xn.

(2)

由(1)，(2)式可得

下面研究n對夫妻沿直線桌入座問題的坐法計數(shù).同上，分3個步驟.不過對于此種情況，女士的坐法對應(yīng)如下矩陣：

根據(jù)乘法原則，n對夫妻沿直線桌入座的坐法計數(shù)Pn=2·n!yn.下面根據(jù)yn與xn的關(guān)系計算yn.

yn按照第1行展開得

于是，n對夫妻沿直線桌入座問題坐法計數(shù)

證畢.

2Q1,n的計算

證明首先給梯形桌短邊的座位用1編號，然后給梯形桌長邊上的座位用2,3,…,2n按從小到大的順序繼續(xù)編號.同定理1，分3個步驟，女士的坐法對應(yīng)如下矩陣：

zn按第1行展開如下：

yn+yn-1=2yn-xn.

所以，

根據(jù)乘法原則，得到n對夫妻圍兩邊分別有1個和2n-1個座位的梯形桌入座問題的坐法計數(shù)

證畢.

3結(jié)語

研究了Lucas夫妻圓桌問題的推廣問題——圍梯形桌入座問題(n對夫妻圍兩邊分別有1個和2n-1個座位的梯形桌入座)，得到其坐法計數(shù)公式.而對于更為一般的圍梯形桌入座問題，即n對夫妻圍兩邊分別有l(wèi)個和2n-l個座位的梯形桌入座(l≤n)，則是下一步的工作.

參考文獻：

[1]謝孔彬.關(guān)于夫妻圍坐問題.山東工程學(xué)院學(xué)報,1995(3):21-22.

[2]耿濟.數(shù)學(xué)娛樂(一)——夫妻問題的新解與應(yīng)用.海南大學(xué)學(xué)報自然科學(xué)版,2008(4):321-324.

[3]邵品琮.關(guān)于夫妻圍桌入座公式的討論.數(shù)學(xué)通報,1956(9):10-11.

[4]曹汝成.組合數(shù)學(xué).第2版.廣州:華南理工大學(xué)出版社，2012:58-60.

[5]郭茂祖，洪家榮.夫妻圍坐問題的另一種解法.哈爾濱科學(xué)技術(shù)大學(xué)學(xué)報,1996(6):85-87.

[6]趙立寬.對夫妻直線入座問題的一個結(jié)果.曲阜師范大學(xué)學(xué)報:自然科學(xué)版,1992(1):65；87；90.

[7]于忠文.排列組合難題的正行列式解法.濟南大學(xué)學(xué)報,1993(3):48-52.

Married Couples’ Trapezoidal Table Problem

ZHAO Hongtao,JIANG Shuli

(School of Mathematics and Physics,North China Electric Power University,Beijing 102206,China)

Abstract:In 1891,French mathematician Edouard Lucas gave his famous Married Couples Circular Table Problem:in how many ways can n married couples be seated around a circular table in such a manner that there is always one man between two women and none of the men is next to his own wife.In this article,we generalize this problem to Married Couples’ Trapezoidal Table Problem:in how many ways can n married couples be seated around a trapezoidal table with two sides having 1 and 2n-1 seats,respectively,in such a manner that there is always one man between two women and none of the men is next to his own wife.In this paper,the enumeration formula of this problem is obtained.

Key words:circular table problem;linear table problem;trapezoidal table problem

(責任編輯向陽潔)