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

黃友誼

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

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

【分類號(hào)】O157

一、引 言

可重復(fù)組合的計(jì)數(shù)是幾百年都沒(méi)有解決的數(shù)學(xué)難題，這里也未解決，只是有點(diǎn)新進(jìn)展，希望本文能夠推動(dòng)這個(gè)難題的解決.與本文類似的問(wèn)題有人用容斥原理去證明，此證法一直有爭(zhēng)議，本文發(fā)現(xiàn)的b個(gè)等式，等號(hào)兩邊給出了合理的含義，這是證明命題的關(guān)鍵，由等式發(fā)現(xiàn)了容斥原理證明此類問(wèn)題的集合，分析了容斥原理現(xiàn)有證法的不足.

二、理論探討

命題1 在x1+x2+…+xk=n的非負(fù)整數(shù)解中，存在∑i=1（-1）1+ik

in+k-ip-1

k-1組解，每組解中至少有一個(gè)不小于p的值.（n≥p≥1）

證明 令每組解中最多有b個(gè)不小于p的值（k≥b≥1）.在滿足命題要求的解中，令有y1組解，每組解中有一個(gè)不小p的值，令有y2組解，每組解中有兩個(gè)不小于p的值……令有yb組解，每組解中有b個(gè)不小于p的值.

（一）x1+x2+…+xk=n-p的每一組非負(fù)整數(shù)解，從k個(gè)x中取一個(gè)x加上p，總共可形成新解k

1n+k-p-1

k-1組.

（二）x1+x2+…+xk=n-2p的每一組非負(fù)整數(shù)解，從k個(gè)x中取兩個(gè)x每個(gè)x都加上p，總共可形成新解k

2n+k-2p-1

k-1組……

（b）x1+x2+…+xk=n-bp的每一組非負(fù)整數(shù)解，從k個(gè)x中取b個(gè)x每個(gè)x都加上p，總共可形成新解k

bn+k-bp-1

k-1組.

顯然以上所有新解都滿足命題的要求，令所有新解中不同解的個(gè)數(shù)是a，則有y1+y2+…+yb≥a，而有以下論述可知：y1+y2+…+yb中的每一組解在新解中都存在，則有y1+y2+…+yb≤a，因此y1+y2+…+yb=a.以上b個(gè)方程的任意一組解，所形成的新解中不存在相同的解，這個(gè)結(jié)論是理解以下內(nèi)容的關(guān)鍵之一.

從y1中任意取一組解，把一個(gè)不小于p的x減去p，所得到的這組解是方程一的解，因此從y1中取的這組解在k

1n+k-p-1

k-1組新解中僅有一個(gè)，y1中的每一組解都能推出同樣的結(jié)果.

從y2中任意取一組解（x1=h+p…xb=c+p…xk=g），把x1與xb任意減去p，可得到2

1+2

2組不同的非負(fù)整數(shù)解，這就說(shuō)明所取的這組解，只能由2

1+2

2組解來(lái)形成，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個(gè)，在k

2n+k-2p-1

k-1組新解中僅有2

2個(gè)，y2中的每一組解都能推出同樣的結(jié)果.

從y3中任意取一組解（x1=h+p…xb=c+p…xk=f+p），把x1，xb，xk任意減去p，可得3

1+3

2+3

3組不同的非負(fù)整數(shù)解，這就說(shuō)明所取的這組解，只能由3

1+3

2+3

3組解來(lái)形成，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個(gè)，在k

2n+k-2p-1

k-1組新解中僅有3

2個(gè)，在k

3n+k-3p-1

k-1組新解中僅有3

3個(gè)，y3中的每一組解都能推出同樣的結(jié)果.……

從yb中任意取一組解，把b個(gè)不小于p的x任意減去p，可得到b

1+b

2+…+b

b組不同的非負(fù)整數(shù)解，這就說(shuō)明所取的這組解，只能由b

1+b

2+…+b

b組解來(lái)形成，b

1組是方程一的解，b

2組是方程二的解……b

b組是方程b的解，因此從yb中取的這組解，在k

1n+k-p-1

k-1組新解中僅有b

1個(gè)，在k

2n+k-2p-1

k-1組新解中僅有b

2個(gè)……在k

bn+k-bp-1

k-1組新解中僅有b

b個(gè)，yb中的每一組解都能推出同樣的結(jié)果.

由以上可知，在k

1n+k-p-1

k-1組新解中不同解的個(gè)數(shù)是y1+y2+…+yb，在k

2n+k-2p-1

k-1組新解中不同解的個(gè)數(shù)是y2+…+yb，在k

bn+k-bp-1

k-1組新解中不同解的個(gè)數(shù)是yb，也可推出下列b個(gè)等式：

（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.

注釋 命題一證明過(guò)程中所推出的b個(gè)等式是可以驗(yàn)證的，寫(xiě)出x1+x2+…+xk=n（x1≥x2≥…≥xk≥0）的所有整數(shù)解，算出每組解的線全排列數(shù)，只有線全排列之和等于n+k-1

n方算正確，在p的取值范圍內(nèi)任意取一個(gè)值，就可以對(duì)方程的解進(jìn)行分類計(jì)數(shù)，可以得出y1，y2，…，yb的值，就能夠?qū)個(gè)等式進(jìn)行驗(yàn)證.

當(dāng)P=1時(shí)，易證yi=k

in-1

i-1，（i=1，2，…，b）代入b個(gè)等式可得：n+k-s-1

k-1=∑bi=sn-1

i-1k-s

k-i，（n≥k=b≥s≥1或k≥n=b≥s≥1），此等式的成立也可以說(shuō)明b個(gè)等式的正確性.此等式可以由另一個(gè)等式推出，n+k-s-c

k-c=∑i=sn-c

i-ck-s

k-i，s與c是整數(shù)，i的最小取值是s與c中較大的一個(gè)，

n+k-s-c個(gè)不同的元素分成n-c個(gè)和k-s個(gè)兩組，從這兩組元素中每次共取k-c個(gè)，所有不同取法等于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個(gè)集合中取m個(gè)集合，利用已知等式k

k+k+1

k+k+2

k+…+n

k=n+1

k+1，易證m個(gè)集合的交集之和是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個(gè)等式，因此本文討論的命題可以給出一些錯(cuò)誤的表達(dá)式，用容斥原理證明卻與正確的，有同樣的證明過(guò)程，其中一定要證明假設(shè)的集合是否存在，相當(dāng)于證明b個(gè)等式恒有正整數(shù)解，容斥原理現(xiàn)有證法幾乎沒(méi)有這方面的論述.下面命題與命題一類似，用容斥原理去證明也存在同樣的問(wèn)題.命題：在x1+x2+…+xk=m的正整數(shù)解中，存在∑i=1（-1）1+ik

im-ip-1

k-1組解，每組解中至少有一個(gè)大于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）.

提示 當(dāng)n≥k（p-1）+1時(shí)，x1+x2+…+xk=n的所有非負(fù)整數(shù)解中都有不小于p的值，此時(shí)推論中的（1）式成立.把n=k（p-1）+1+r代入（1）式，可得推論中的（2）式.

命題2 元素x1，元素x2，…，元素xk均有p-1個(gè)，p≥2，從k（p-1）個(gè)元素中取n個(gè)元素，共有∑i=0（-1）ik

in+k-ip-1

k-1種不同的取法.

證明 命題二相當(dāng)于這個(gè)問(wèn)題，在x1+x2+…+xk=n的非負(fù)整數(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ù)組合的計(jì)數(shù)公式，必須k種元素每種元素的個(gè)數(shù)都不小于n，這個(gè)計(jì)數(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）提示：當(dāng)p=2時(shí)，命題二就是從k個(gè)不同的元素中取n個(gè).

（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.

當(dāng)x=1時(shí)npk=∑k（p-1）n=0∑i=0（-1）ik

in+k-ip-1

k-1

三、結(jié) 論

通過(guò)發(fā)現(xiàn)的一些新等式，使其具有含義，因此可以驗(yàn)證，解決了可重復(fù)組合在特殊條件下的計(jì)數(shù)，同時(shí)指出了用容斥原理證明此類問(wèn)題的不足之處.

【參考文獻(xiàn)】

[1]馬光思.組合數(shù)學(xué)[M].西安電子科技大學(xué)出版社，2002.

[2]盧開(kāi)澄，盧華明.組合數(shù)學(xué)[M].清華大學(xué)出版社，2006.

[3][美]羅森（Rosen，K.H）.袁崇義，屈婉玲，王捍貧，劉田譯.離散數(shù)學(xué)及其應(yīng)用[M].機(jī)械工業(yè)出版社，2007.

[4][美]多西（Dossey，J·A）等，章炯民，王新偉，曹立譯.離散數(shù)學(xué)[M].機(jī)械工業(yè)出版社，2007.

[5][美]格里馬迪（Grimaldi，R）.林永鋼譯.離散數(shù)學(xué)與組合數(shù)學(xué)[M].清華大學(xué)出版社，2007.

[6]柯召，魏萬(wàn)迪.組合論（上）[M].科學(xué)出版社，2010.