特殊條件下可重復組合的計數(shù)

黃友誼

【摘要】這里討論了k個未知自然數(shù)之和成等差的各種方程，發(fā)現(xiàn)了這些方程之間的聯(lián)系等式，由此所推出的可重復組合的計數(shù)公式，比教材中的適用范圍更廣，雖然這個計數(shù)公式早已出現(xiàn)，但在教材中還未討論.

【關(guān)鍵詞】可重復組合;等式，;不同的解

【分類號】O157

一、引 言

可重復組合的計數(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作為可重復組合的計數(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）證明：命題二中可重復組合的生成函數(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)的一些新等式，使其具有含義，因此可以驗證，解決了可重復組合在特殊條件下的計數(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.