圓組合的夫妻問題

許多適用于男性和女性的問題是國外的數(shù)學(xué)游戲。現(xiàn)在，原問題的內(nèi)容也有所改變和解釋如下。設(shè)n,k為正整數(shù),而且n≥2k.圓桌有n個(gè)坐位,k對夫妻入坐時(shí),要求每位丈夫的左鄰是他的妻子;當(dāng)k>1時(shí),任意2對夫妻交換坐位都算作相同坐法,問有幾種不同坐法?簡單情況:當(dāng)k=1時(shí),圓桌有n個(gè)坐位,1對夫妻共有n種坐法;當(dāng)n=2k時(shí),k對夫妻僅有2種坐法;又當(dāng)k=0時(shí),圓桌上沒有人坐,也算作1種坐法.例子3對夫妻坐在8個(gè)席位的圓桌上,共有幾種不同坐法?解首先,指定圓桌上某坐位為第1席,按順時(shí)針方向依次確定第2席、第3席直至第8席;3對夫妻表示為A1B1,A2B2,A3B3.其次,假設(shè)A1坐1席,B1坐2席,A2坐3席,B2坐4席,A3坐5席,B3坐6席,表示為1(A1)2(B1)3(A2)4(B2)5(A3)6(B3);由于丈夫左鄰是他的妻子,簡化為1(A1)3(A2)5(A3);又規(guī)定每對夫妻交換坐位都算作相同的,所以只要把3位丈夫安排在1席、3席、5席上,記為1,3,5.最后,采用以上記法,不同的坐法為1,3,5;1,3,6;1,3,7;1,4,6;1,4,7;1,5,7;2,4,6;2,4,7;2,4,8;2,5,7;2,5,8;2,6,8;3,5,7;3,5,8;3,6,8;4,6,8等16種.本文的目的,一方面是通過圓組合概念,給出夫妻問題4種新解;另一方面指出夫妻問題在實(shí)際應(yīng)用上的意義.1[nk]的再求解夫妻問題在1943年由KaplanskyI解決,現(xiàn)在把具體的夫妻問題轉(zhuǎn)化成抽象的數(shù)學(xué)問題,筆者提出下面的概念.定義集合{1,2,3,…,n}中所有元素按照順時(shí)針方向依次排列在圓周上,使得首尾兩元素相鄰,即元素1與n相鄰,在圓周上任取一組元素,要求符合條件(1)不計(jì)次序;(2)不含相鄰的兩元素,稱為圓組合.由此可知,圓桌有n個(gè)坐位,k對夫妻的不同坐法,就是n個(gè)元素任取k個(gè)元素的圓組合,記為[nk].[nk].接著談?wù)劮蚱迒栴}的4種新解.解法1首先,把n個(gè)元素中任取k個(gè)元素的圓組合數(shù)[nk][nk]中每組k個(gè)元素重新排列成k種不同形式,使得該組k個(gè)元素依次出現(xiàn)在第1個(gè)元素的位置上,其余各元素的次序不變,因此重新排列的組數(shù)為k[nk].k[nk].其次,再把重新排列的k[nk]k[nk]組分成n類,要求第1類含有元素1,第2類含有元素2,如此類推,直至第n類含有元素n,此時(shí)每1類中都有(n-k-1k-1)(n?k?1k?1)組.事實(shí)上,每1類中既含有1個(gè)指定元素,又不含相鄰的k個(gè)元素.現(xiàn)在從n個(gè)元素中減去k+1個(gè)元素得到n-k-1個(gè)元素,再從n-k-1個(gè)元素中任取k-1個(gè)元素,要求“不計(jì)次序”,但不要求“不含相鄰元素”,這是普通組合問題,該類含有(n-k-1k-1)組.最后,綜上所述,得到k[nk]=n(n-k-1k-1),就有[nk]=nk(n-k-1k-1).解法2n個(gè)元素中任取k個(gè)元素的圓組合數(shù)為[nk].由于不能選取相鄰的k個(gè)元素,只能從n-k個(gè)元素中任取k個(gè)元素,現(xiàn)在分2種情況來考慮:第1種情況,不含指定的一個(gè)元素,即從n-k個(gè)元素中任取k個(gè)元素的普通組合數(shù)為(n-kk);第2種情況,含有指定的一個(gè)元素,從n-k個(gè)元素減去指定元素得到n-k-1個(gè)元素,再從n-k-1個(gè)元素中任取k-1個(gè)元素的普通組合數(shù)為(n-k-1k-1).因此[nk]=(n-kk)+(n-k-1k-1).解法3現(xiàn)在分3個(gè)步驟來敘述:第1步驟,n個(gè)元素中第1次任取1個(gè)元素的不同方法有n種.第2步驟,n個(gè)元素中任取k個(gè)元素,此處k>1.由于不允許出現(xiàn)相鄰元素,只能從n-k個(gè)元素中選取.當(dāng)?shù)?次任取1個(gè)元素不同方法有n-k-1種(這里減去第1次選出的元素),類似地,第3次任取1個(gè)元素不同方法有n-k-2種,直至第k次任取1個(gè)元素不同方法有n-k-(k-1)=n-2k+1種.第3步驟,總的說來,經(jīng)過k次任取得到不同的排列共有n(n-k-1)(n-k-2)…(n-2k+1).由于不計(jì)次序,除去排列中重復(fù)出現(xiàn)的k!次,就有[nk]=n(n-k-1)(n-k-2)?(n-2k+1)k!.再談一種新解,這一解法應(yīng)用到下面重要恒等式[nk]=[n-1k]+[n-2k-1].證明1已知[nk]=n(n-k-1)(n-k-2)?(n-2k+1)k!,直接代入即得.證明2n個(gè)元素中任取k個(gè)元素的圓組合數(shù)為[nk].又可分為2類,一類不含指定元素,即n-1個(gè)元素中任取k個(gè)元素的圓組合數(shù)為[n-1k];另一類含有指定元素,該元素與相鄰2個(gè)元素共有3個(gè)元素不能取出.現(xiàn)在特別注意處理的辦法;先從n-2個(gè)元素中任取k-1個(gè)元素的圓組合數(shù)為[n-2k-1],再把另1個(gè)不能取出元素安排在沒有取出元素之中,因?yàn)?n-2)-(k-1)=n-k+1≥n-[n2]+1＞1的關(guān)系,所以上述恒等式成立.敘述解法4之前,先以為例,加以說明.從重要恒等式得到下面一批等式=+?=+?=+?=+?=+?=+,分別代入中得到=+2+3++3,由于==以及=,合并成2項(xiàng)=(1+2+3)+(1+3)=16,與前例結(jié)果完全一致.解法4首先,把[nk]多次應(yīng)用重要恒等式展開就有[nk]=(A1+A2+A3+?)+(B1+B2+B3+?),由于===?,===?,又有[nk]=A+B,其中A=A1+A2+A3+…,B=B1+B2+B3+….其次,為了計(jì)算A與B的數(shù)值,假設(shè)h=n-2k以及函數(shù)f(h,k)=[nk],就能得到f(h-1,k)=[n-1k],f(h,k-1)=[n-2k-1]以及f(1,0)=,f(0,1)=等等,就有f(h,k)=f(h-1,k)+f(h,k-1)=f(h-2,k)+2f(h-1,k-1)+f(h,k-2)=…=Af(1,0)+Bf(0,1).函數(shù)f(h,k)展開中h,k依次減低h-1,k次后出現(xiàn)f(1,0)的總數(shù),即A的數(shù)值.根據(jù)不盡相同的文字排列定義可知A的數(shù)值等于(h-1)+k個(gè)文字內(nèi)含有h-1個(gè)相同文字,k個(gè)相同文字排列的總數(shù),得到A=(h-1+k)!(h-1)!k!=(n-k-1)!(n-2k-1)!k!=(n-k-1k),類似地,還有B=(h+k-1)!h!(k-1)!=(n-k-1)!(n-2k)!(k-1)!=(n-k-1k-1).最后,把A,B數(shù)值代入得到[nk]=f(h,k)=(n-k-1k)+2(n-k-1k-1).以上解法4的結(jié)果通過解法1的結(jié)果很簡單地得出[nk]=nk(n-k-1k-1)=(n-2k)+2kk(n-k-1k-1)=(n-k-1k)+2(n-k-1k-1).一繁一簡,各有特色,殊途同歸,體現(xiàn)出數(shù)學(xué)的美妙.2等價(jià)leibniz定理圓桌有n個(gè)坐位,k對夫妻不同坐法就是n個(gè)元素中任取k個(gè)元素的圓組合數(shù)[nk],這里k=0?1?2???[n2],由此得到數(shù)列:[n0]?[n1]?[n2]???[n[n/2]],這一數(shù)列有許多應(yīng)用,現(xiàn)舉兩例以作本文結(jié)束.第1應(yīng)用筆者在1962年得到等價(jià)二項(xiàng)式定理an+bn=[n0](a+b)n-[n1](a+b)n-2(ab)+[n2](a+b)n-4(ab)2-?+(-1)[n2][n[n/2]](a+b)n-2[n/2](ab)[n/2]以及1965年得到等價(jià)Leibniz定理f(n)g+fg(n)=[n0](fg)(n)-[n1](f′g′)(n-2)+[n2](f″g″)(n-4)-?+(-1)[n/2][n[n/2]](f([n/2])g([n/2]))(n-2[n/2]).已經(jīng)認(rèn)識(shí)到記號(hào)[nk]中蘊(yùn)涵著組合的新概念,直到2004年才提出圓組合的概念,這一概念的“源頭”就是夫妻問題.第2應(yīng)用眾所周知,Fibonacci數(shù)和Lucas數(shù)是數(shù)論上的孿生數(shù)列.從兔子繁殖規(guī)律得出Fibonacci數(shù);現(xiàn)在從夫妻問題得出Lucas數(shù).Lucas數(shù)是指l0=2,l1=1,l2=3,l3=4,l4=7,…,ln=ln-1+ln-2,這里n≥2;Lucas數(shù)另一表示式ln=(1+√52)n+(1-√52)n.設(shè)a=1+√52,b=1-√52,就有a+b=1,ab=-1,代入上述等價(jià)二項(xiàng)式定理得到ln=[n0]+[n1]+[n2]+?+[n[n/2]],這就是Lucas數(shù)的圓組合表示式.此外,圓組合恒等式的問題也是具有