特殊条件下可重复组合的计数

2015-05-30黄友谊

数学学习与研究 2015年21期

关键词：等式

黄友谊

【摘要】这里讨论了k个未知自然数之和成等差的各种方程，发现了这些方程之间的联系等式，由此所推出的可重复组合的计数公式，比教材中的适用范围更广，虽然这个计数公式早已出现，但在教材中还未讨论.

【关键词】可重复组合;等式，;不同的解

【分类号】O157

一、引言

可重复组合的计数是几百年都没有解决的数学难题，这里也未解决，只是有点新进展，希望本文能够推动这个难题的解决.与本文类似的问题有人用容斥原理去证明，此证法一直有争议，本文发现的b个等式，等号两边给出了合理的含义，这是证明命题的关键，由等式发现了容斥原理证明此类问题的集合，分析了容斥原理现有证法的不足.

二、理论探讨

命题1 在x1+x2+…+xk=n的非负整数解中，存在∑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的每一组非负整数解，从k个x中取一个x加上p，总共可形成新解k

1n+k-p-1

k-1组.

（二）x1+x2+…+xk=n-2p的每一组非负整数解，从k个x中取两个x每个x都加上p，总共可形成新解k

2n+k-2p-1

k-1组……

（b）x1+x2+…+xk=n-bp的每一组非负整数解，从k个x中取b个x每个x都加上p，总共可形成新解k

bn+k-bp-1

k-1组.

显然以上所有新解都满足命题的要求，令所有新解中不同解的个数是a，则有y1+y2+…+yb≥a，而有以下论述可知：y1+y2+…+yb中的每一组解在新解中都存在，则有y1+y2+…+yb≤a，因此y1+y2+…+yb=a.以上b个方程的任意一组解，所形成的新解中不存在相同的解，这个结论是理解以下内容的关键之一.

从y1中任意取一组解，把一个不小于p的x减去p，所得到的这组解是方程一的解，因此从y1中取的这组解在k

1n+k-p-1

k-1组新解中仅有一个，y1中的每一组解都能推出同样的结果.

从y2中任意取一组解（x1=h+p…xb=c+p…xk=g），把x1与xb任意减去p，可得到2

1+2

2组不同的非负整数解，这就说明所取的这组解，只能由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中的每一组解都能推出同样的结果.

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

1+3

2+3

3组不同的非负整数解，这就说明所取的这组解，只能由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中的每一组解都能推出同样的结果.……

从yb中任意取一组解，把b个不小于p的x任意减去p，可得到b

1+b

2+…+b

b组不同的非负整数解，这就说明所取的这组解，只能由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中的每一组解都能推出同样的结果.

由以上可知，在k

1n+k-p-1

k-1组新解中不同解的个数是y1+y2+…+yb，在k

2n+k-2p-1

k-1组新解中不同解的个数是y2+…+yb，在k

bn+k-bp-1

k-1组新解中不同解的个数是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）的所有整数解，算出每组解的线全排列数，只有线全排列之和等于n+k-1

n方算正确，在p的取值范围内任意取一个值，就可以对方程的解进行分类计数，可以得出y1，y2，…，yb的值，就能够对b个等式进行验证.

当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是整数，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有多少组正整数解，就有多少组不同的b个等式，因此本文讨论的命题可以给出一些错误的表达式，用容斥原理证明却与正确的，有同样的证明过程，其中一定要证明假设的集合是否存在，相当于证明b个等式恒有正整数解，容斥原理现有证法几乎没有这方面的论述.下面命题与命题一类似，用容斥原理去证明也存在同样的问题.命题：在x1+x2+…+xk=m的正整数解中，存在∑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的所有非负整数解中都有不小于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