圆组合的夫妻问题

圆组合的夫妻问题

许多适用于男性和女性的问题是国外的数学游戏。现在，原问题的内容也有所改变和解释如下。设n,k为正整数,而且n≥2k.圆桌有n个坐位,k对夫妻入坐时,要求每位丈夫的左邻是他的妻子;当k>1时,任意2对夫妻交换坐位都算作相同坐法,问有几种不同坐法?简单情况:当k=1时,圆桌有n个坐位,1对夫妻共有n种坐法;当n=2k时,k对夫妻仅有2种坐法;又当k=0时,圆桌上没有人坐,也算作1种坐法.例子3对夫妻坐在8个席位的圆桌上,共有几种不同坐法?解首先,指定圆桌上某坐位为第1席,按顺时针方向依次确定第2席、第3席直至第8席;3对夫妻表示为A1B1,A2B2,A3B3.其次,假设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);又规定每对夫妻交换坐位都算作相同的,所以只要把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种新解;另一方面指出夫妻问题在实际应用上的意义.1[nk]的再求解夫妻问题在1943年由KaplanskyI解决,现在把具体的夫妻问题转化成抽象的数学问题,笔者提出下面的概念.定义集合{1,2,3,…,n}中所有元素按照顺时针方向依次排列在圆周上,使得首尾两元素相邻,即元素1与n相邻,在圆周上任取一组元素,要求符合条件(1)不计次序;(2)不含相邻的两元素,称为圆组合.由此可知,圆桌有n个坐位,k对夫妻的不同坐法,就是n个元素任取k个元素的圆组合,记为[nk].[nk].接着谈谈夫妻问题的4种新解.解法1首先,把n个元素中任取k个元素的圆组合数[nk][nk]中每组k个元素重新排列成k种不同形式,使得该组k个元素依次出现在第1个元素的位置上,其余各元素的次序不变,因此重新排列的组数为k[nk].k[nk].其次,再把重新排列的k[nk]k[nk]组分成n类,要求第1类含有元素1,第2类含有元素2,如此类推,直至第n类含有元素n,此时每1类中都有(n-k-1k-1)(n−k−1k−1)组.事实上,每1类中既含有1个指定元素,又不含相邻的k个元素.现在从n个元素中减去k+1个元素得到n-k-1个元素,再从n-k-1个元素中任取k-1个元素,要求“不计次序”,但不要求“不含相邻元素”,这是普通组合问题,该类含有(n-k-1k-1)组.最后,综上所述,得到k[nk]=n(n-k-1k-1),就有[nk]=nk(n-k-1k-1).解法2n个元素中任取k个元素的圆组合数为[nk].由于不能选取相邻的k个元素,只能从n-k个元素中任取k个元素,现在分2种情况来考虑:第1种情况,不含指定的一个元素,即从n-k个元素中任取k个元素的普通组合数为(n-kk);第2种情况,含有指定的一个元素,从n-k个元素减去指定元素得到n-k-1个元素,再从n-k-1个元素中任取k-1个元素的普通组合数为(n-k-1k-1).因此[nk]=(n-kk)+(n-k-1k-1).解法3现在分3个步骤来叙述:第1步骤,n个元素中第1次任取1个元素的不同方法有n种.第2步骤,n个元素中任取k个元素,此处k>1.由于不允许出现相邻元素,只能从n-k个元素中选取.当第2次任取1个元素不同方法有n-k-1种(这里减去第1次选出的元素),类似地,第3次任取1个元素不同方法有n-k-2种,直至第k次任取1个元素不同方法有n-k-(k-1)=n-2k+1种.第3步骤,总的说来,经过k次任取得到不同的排列共有n(n-k-1)(n-k-2)…(n-2k+1).由于不计次序,除去排列中重复出现的k!次,就有[nk]=n(n-k-1)(n-k-2)⋯(n-2k+1)k!.再谈一种新解,这一解法应用到下面重要恒等式[nk]=[n-1k]+[n-2k-1].证明1已知[nk]=n(n-k-1)(n-k-2)⋯(n-2k+1)k!,直接代入即得.证明2n个元素中任取k个元素的圆组合数为[nk].又可分为2类,一类不含指定元素,即n-1个元素中任取k个元素的圆组合数为[n-1k];另一类含有指定元素,该元素与相邻2个元素共有3个元素不能取出.现在特别注意处理的办法;先从n-2个元素中任取k-1个元素的圆组合数为[n-2k-1],再把另1个不能取出元素安排在没有取出元素之中,因为(n-2)-(k-1)=n-k+1≥n-[n2]+1＞1的关系,所以上述恒等式成立.叙述解法4之前,先以为例,加以说明.从重要恒等式得到下面一批等式=+‚=+‚=+‚=+‚=+‚=+,分别代入中得到=+2+3++3,由于==以及=,合并成2项=(1+2+3)+(1+3)=16,与前例结果完全一致.解法4首先,把[nk]多次应用重要恒等式展开就有[nk]=(A1+A2+A3+⋯)+(B1+B2+B3+⋯),由于===⋯,===⋯,又有[nk]=A+B,其中A=A1+A2+A3+…,B=B1+B2+B3+….其次,为了计算A与B的数值,假设h=n-2k以及函数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).函数f(h,k)展开中h,k依次减低h-1,k次后出现f(1,0)的总数,即A的数值.根据不尽相同的文字排列定义可知A的数值等于(h-1)+k个文字内含有h-1个相同文字,k个相同文字排列的总数,得到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数值代入得到[nk]=f(h,k)=(n-k-1k)+2(n-k-1k-1).以上解法4的结果通过解法1的结果很简单地得出[nk]=nk(n-k-1k-1)=(n-2k)+2kk(n-k-1k-1)=(n-k-1k)+2(n-k-1k-1).一繁一简,各有特色,殊途同归,体现出数学的美妙.2等价leibniz定理圆桌有n个坐位,k对夫妻不同坐法就是n个元素中任取k个元素的圆组合数[nk],这里k=0‚1‚2‚⋯‚[n2],由此得到数列:[n0]‚[n1]‚[n2]‚⋯‚[n[n/2]],这一数列有许多应用,现举两例以作本文结束.第1应用笔者在1962年得到等价二项式定理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年得到等价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]).已经认识到记号[nk]中蕴涵着组合的新概念,直到2004年才提出圆组合的概念,这一概念的“源头”就是夫妻问题.第2应用众所周知,Fibonacci数和Lucas数是数论上的孪生数列.从兔子繁殖规律得出Fibonacci数;现在从夫妻问题得出Lucas数.Lucas数是指l0=2,l1=1,l2=3,l3=4,l4=7,…,ln=ln-1+ln-2,这里n≥2;Lucas数另一表示式ln=(1+√52)n+(1-√52)n.设a=1+√52,b=1-√52,就有a+b=1,ab=-1,代入上述等价二项式定理得到ln=[n0]+[n1]+[n2]+⋯+[n[n/2]],这就是Lucas数的圆组合表示式.此外,圆组合恒等式的问题也是具有