夫妻圍梯形桌入座問題*

趙紅濤，姜書麗

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

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

關鍵詞：圓桌問題；直線桌問題；梯形桌問題

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

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

DOI:10.3969/j.cnki.jdxb.2015.06.001

收稿日期：*2015-06-04

基金項目：國家自然科學基金資助項目(10901051,11201143)；中央高?；究蒲袠I(yè)務費專項資金資助(13MS38)；華北電力大學教改項目資助(《高等代數(shù)》在數(shù)學建模中的應用)

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

n對夫妻圍圓桌入座問題是組合數(shù)學中一個非常著名的問題，學者們[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ù)編號的座位上，讓n個男士入座有n!種坐法；

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

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

Mn=2·n!xn.

(2)

由(1)，(2)式可得

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

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

yn按照第1行展開得

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

證畢.

2Q1,n的計算

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

zn按第1行展開如下：

yn+yn-1=2yn-xn.

所以，

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

證畢.

3結語

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

參考文獻：

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

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

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

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

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

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

[7]于忠文.排列組合難題的正行列式解法.濟南大學學報,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

(責任編輯向陽潔)