黃友誼
【摘要】這里討論了k個未知自然數(shù)之和成等差的各種方程,發(fā)現(xiàn)了這些方程之間的聯(lián)系等式,由此所推出的可重復(fù)組合的計數(shù)公式,比教材中的適用范圍更廣,雖然這個計數(shù)公式早已出現(xiàn),但在教材中還未討論.
【關(guān)鍵詞】可重復(fù)組合;等式,;不同的解
【分類號】O157
一、引 言
可重復(fù)組合的計數(shù)是幾百年都沒有解決的數(shù)學難題,這里也未解決,只是有點新進展,希望本文能夠推動這個難題的解決.與本文類似的問題有人用容斥原理去證明,此證法一直有爭議,本文發(fā)現(xiàn)的b個等式,等號兩邊給出了合理的含義,這是證明命題的關(guān)鍵,由等式發(fā)現(xiàn)了容斥原理證明此類問題的集合,分析了容斥原理現(xiàn)有證法的不足.
二、理論探討
命題1 在x1+x2+…+xk=n的非負整數(shù)解中,存在∑i=1(-1)1+ik
in+k-ip-1
k-1組解,每組解中至少有一個不小于p的值.(n≥p≥1)
證明 令每組解中最多有b個不小于p的值(k≥b≥1).在滿足命題要求的解中,令有y1組解,每組解中有一個不小p的值,令有y2組解,每組解中有兩個不小于p的值……令有yb組解,每組解中有b個不小于p的值.
(一)x1+x2+…+xk=n-p的每一組非負整數(shù)解,從k個x中取一個x加上p,總共可形成新解k
1n+k-p-1
k-1組.
(二)x1+x2+…+xk=n-2p的每一組非負整數(shù)解,從k個x中取兩個x每個x都加上p,總共可形成新解k
2n+k-2p-1
k-1組……
(b)x1+x2+…+xk=n-bp的每一組非負整數(shù)解,從k個x中取b個x每個x都加上p,總共可形成新解k
bn+k-bp-1
k-1組.
顯然以上所有新解都滿足命題的要求,令所有新解中不同解的個數(shù)是a,則有y1+y2+…+yb≥a,而有以下論述可知:y1+y2+…+yb中的每一組解在新解中都存在,則有y1+y2+…+yb≤a,因此y1+y2+…+yb=a.以上b個方程的任意一組解,所形成的新解中不存在相同的解,這個結(jié)論是理解以下內(nèi)容的關(guān)鍵之一.
從y1中任意取一組解,把一個不小于p的x減去p,所得到的這組解是方程一的解,因此從y1中取的這組解在k
1n+k-p-1
k-1組新解中僅有一個,y1中的每一組解都能推出同樣的結(jié)果.
從y2中任意取一組解(x1=h+p…xb=c+p…xk=g),把x1與xb任意減去p,可得到2
1+2
2組不同的非負整數(shù)解,這就說明所取的這組解,只能由2
1+2
2組解來形成,2
1組是方程一的解 (x1=h…xb=c+p…xk=g),(x1=h+p…xb=c…xk=g),2
2組是方程二的解(x1=h…xb=c…xk=g),因此從y2中取的這組解,在k
1n+k-p-1
k-1組新解中僅有2
1個,在k
2n+k-2p-1
k-1組新解中僅有2
2個,y2中的每一組解都能推出同樣的結(jié)果.
從y3中任意取一組解(x1=h+p…xb=c+p…xk=f+p),把x1,xb,xk任意減去p,可得3
1+3
2+3
3組不同的非負整數(shù)解,這就說明所取的這組解,只能由3
1+3
2+3
3組解來形成,3
1組是方程一的解(x1=h…xb=c+p…xk=f+p),(x1=h+p…xb=c…xk=f+p),(x1=h+p…xb=c+p…xk=f),3
2組是方程二的解(x1=h+p…xb=c…xk=f),(x1=h…xb=c+p…xk=f),(x1=h…xb=c……xk=f+p),3
3組是方程三的解(y3),因此從y3中取的這組解,在k
1n+k-p-1
k-1組新解中僅有3
1個,在k
2n+k-2p-1
k-1組新解中僅有3
2個,在k
3n+k-3p-1
k-1組新解中僅有3
3個,y3中的每一組解都能推出同樣的結(jié)果.……
從yb中任意取一組解,把b個不小于p的x任意減去p,可得到b
1+b
2+…+b
b組不同的非負整數(shù)解,這就說明所取的這組解,只能由b
1+b
2+…+b
b組解來形成,b
1組是方程一的解,b
2組是方程二的解……b
b組是方程b的解,因此從yb中取的這組解,在k
1n+k-p-1
k-1組新解中僅有b
1個,在k
2n+k-2p-1
k-1組新解中僅有b
2個……在k
bn+k-bp-1
k-1組新解中僅有b
b個,yb中的每一組解都能推出同樣的結(jié)果.
由以上可知,在k
1n+k-p-1
k-1組新解中不同解的個數(shù)是y1+y2+…+yb,在k
2n+k-2p-1
k-1組新解中不同解的個數(shù)是y2+…+yb,在k
bn+k-bp-1
k-1組新解中不同解的個數(shù)是yb,也可推出下列b個等式:
(1)y1+2
1y2+3
1y3+…+b
1yb=k
1n+k-p-1
k-1
(2)2
2y2+3
2y3+…+b
2yb=k
2n+k-2p-1
k-1
(3)3
3y3+4
3y4+…+b
3yb=k
3n+k-3p-1
k-1……
(4)b
byb=k
bn+k-bp-1
k-1
(1)-(2)+(3)-(4)+…+(-1)b+1(b)可得:
y1+[2
1-2
2]y2+3
1-3
2+3
3]y3+…+[b
1-b
2+b
3+…+(-1)b+1b
byb=y1+y2+y3+…+yb=∑bi=1(-1)1+ik
in+k-ip-1
k-1.
注釋 命題一證明過程中所推出的b個等式是可以驗證的,寫出x1+x2+…+xk=n(x1≥x2≥…≥xk≥0)的所有整數(shù)解,算出每組解的線全排列數(shù),只有線全排列之和等于n+k-1
n方算正確,在p的取值范圍內(nèi)任意取一個值,就可以對方程的解進行分類計數(shù),可以得出y1,y2,…,yb的值,就能夠?qū)個等式進行驗證.
當P=1時,易證yi=k
in-1
i-1,(i=1,2,…,b)代入b個等式可得:n+k-s-1
k-1=∑bi=sn-1
i-1k-s
k-i,(n≥k=b≥s≥1或k≥n=b≥s≥1),此等式的成立也可以說明b個等式的正確性.此等式可以由另一個等式推出,n+k-s-c
k-c=∑i=sn-c
i-ck-s
k-i,s與c是整數(shù),i的最小取值是s與c中較大的一個,
n+k-s-c個不同的元素分成n-c個和k-s個兩組,從這兩組元素中每次共取k-c個,所有不同取法等于n+k-s-c
k-c.
令Z0+ Z1+ Z2+…+ Zb=n+k-1
n,
A1={Z1,Z2,Z3,…,Zb},
A2={Z2,Z3,…,Zb},
A3={Z3,…,Zb}……Ab={Zb}從b個集合中取m個集合,利用已知等式k
k+k+1
k+k+2
k+…+n
k=n+1
k+1,易證m個集合的交集之和是m
mZm+m+1
mZm+1+m+2
mZm+2+…+b
mZb,m等于1,2,…,b分別代入上式,
Z0+ Z1+ Z2+…+ Zb=n+k-1
n有多少組正整數(shù)解,就有多少組不同的b個等式,因此本文討論的命題可以給出一些錯誤的表達式,用容斥原理證明卻與正確的,有同樣的證明過程,其中一定要證明假設(shè)的集合是否存在,相當于證明b個等式恒有正整數(shù)解,容斥原理現(xiàn)有證法幾乎沒有這方面的論述.下面命題與命題一類似,用容斥原理去證明也存在同樣的問題.命題:在x1+x2+…+xk=m的正整數(shù)解中,存在∑i=1(-1)1+ik
im-ip-1
k-1組解,每組解中至少有一個大于p的值.
推論(1)n+k-1
k-1=∑i=1(-1)1+ik
in+k-ip-1
k-1
n+k-1k≥p≥1.
(2)∑i=0(-1)ik
ipk-ip+r
k-1=0(p≥1,r≥0).
提示 當n≥k(p-1)+1時,x1+x2+…+xk=n的所有非負整數(shù)解中都有不小于p的值,此時推論中的(1)式成立.把n=k(p-1)+1+r代入(1)式,可得推論中的(2)式.
命題2 元素x1,元素x2,…,元素xk均有p-1個,p≥2,從k(p-1)個元素中取n個元素,共有∑i=0(-1)ik
in+k-ip-1
k-1種不同的取法.
證明 命題二相當于這個問題,在x1+x2+…+xk=n的非負整數(shù)解中,有多少組解中不存在大于p-1的值,由命題一可知滿足條件的解是:n+k-1
k-1-∑i=1(-1)1+ik
i
n+k-ip-1
k-1=∑i=0(-1)ik
in+k-ip-1
k-1
注釋:現(xiàn)在所用的教材中,把n+k-1
n作為可重復(fù)組合的計數(shù)公式,必須k種元素每種元素的個數(shù)都不小于n,這個計數(shù)公式才成立.
推論(1)k
n=∑i=0(-1)ik
in+k-2i-1
k-1(k≥n).
(2)∑k(p-1)n=0∑i=0(-1)ik
in+k-ip-1
k-1=pk(p≥2).
(1)提示:當p=2時,命題二就是從k個不同的元素中取n個.
(2)證明:命題二中可重復(fù)組合的生成函數(shù)是:
G(x)=(1+x+x2+…+xp-1)k
=∑k(p-1)n=0∑i=0(-1)ik
in+k-ip-1
k-1xn.
當x=1時npk=∑k(p-1)n=0∑i=0(-1)ik
in+k-ip-1
k-1
三、結(jié) 論
通過發(fā)現(xiàn)的一些新等式,使其具有含義,因此可以驗證,解決了可重復(fù)組合在特殊條件下的計數(shù),同時指出了用容斥原理證明此類問題的不足之處.
【參考文獻】
[1]馬光思.組合數(shù)學[M].西安電子科技大學出版社,2002.
[2]盧開澄,盧華明.組合數(shù)學[M].清華大學出版社,2006.
[3][美]羅森(Rosen,K.H).袁崇義,屈婉玲,王捍貧,劉田譯.離散數(shù)學及其應(yīng)用[M].機械工業(yè)出版社,2007.
[4][美]多西(Dossey,J·A)等,章炯民,王新偉,曹立譯.離散數(shù)學[M].機械工業(yè)出版社,2007.
[5][美]格里馬迪(Grimaldi,R).林永鋼譯.離散數(shù)學與組合數(shù)學[M].清華大學出版社,2007.
[6]柯召,魏萬迪.組合論(上)[M].科學出版社,2010.