不定方程的解与排列组合的巧妙运用

钟建芳

摘 要：本文从不定方程的正整数解的个数与隔板法的组合数的对应关系，得出求关于组合数中隔板法的两种模型，然后从这两个模型出发，得出求排列组合一类问题可用不定方程解的个数结合隔板法来解决，起到了非常简便和实用的效果.

关键词：不定方程；排列组合；综合应用

在排列组合的问题中，我们常常会碰到把若干相同的元素分成几组，每个组至少要有一个元素，问分法数有几种？其问题的实质就是用隔板法求排列组合数的问题.隔板法中强调的是每组元素的个数，而与每组包含哪个元素无关.

常见的隔板法问题如下：

例1 （1）6本完全相同的书分给4人，每人至少1本，有几种分法？

（2）6本完全相同的书分给4人，允许有人分不到书，有几种分法？

分析：（1）可以设想把6本书排成一排，要分成4堆，可以想象成用了3块板插到5个空位中，第一块板之前的为第一个人得书数，第一块板和第二块板之间的为第二个人得书数，第二块板和第三块板之间的为第三个人得书数，第三块板以后的为第四个人得书数，故排法数有C■=10种.

（2）可以在（1）的基础上，将“允许有人分不到书”与“至少有一本”建立一一对应关系，由“0”个变为“1”问题等价于有10本相同的书分给4人，每人至少有一本，即分法数有C■=84种.

我们可以将上面两种问题归类，可看成隔板法的两种基本模型.

模型1 不定方程x1+x2+…+xn=m. （m，n∈N*，且m≥n≥1）的正整数解（x1，x2，…，xn）的个数.

分析：正整数中最小值为1，即至少取1，故解的个数有C■种.

模型2 不定方程x1+x2+…+xn=m（m，n∈N*，且m≥n≥1）的非负整数解（x1，x2，…，xn）的个数.

分析：由0≤x1，x2，…，xn≤m. 不妨令x1=y1-1，x2=y2-1，…，xn=yn-1，则y1+y2+…+yn=m+n，其中1≤y1，y2，…，yn≤m+1，即原不定方程的非负整数解即为不定方程y1+y2+…+yn=m+n的正整数解的个数，即C■.

然而，在我们经常碰到的问题中，每组的数目要求不尽相同，且被分的元素又要区别对待，该如何根据实际情况分组呢？建立在以上两个基础模型的基础上，我们可以这样解决此类问题.例如：

例2 （1）8名男生与25名女生排成一列，任意相邻两名男生之间至少有两名女生的排法有多少种？

（2）8名男生与25名女生沿圆周排成一圈，任意相邻两名男生之间至少有两名女生的排法有多少种？

分析与解法：（1）首先将8名男生排成一列，共有Α■=40320种. 8个男生之间可产生9个空格，为求女生的排法，先将这些空格所排的女生依次记为x1，x2，x3，…，x9，显然有x1+x2+x3+…+x9=25.

依题设，x1≥0，xi≥2（i=2，3，…，8），x9≥0，女生插空方法数对应着方程x′1+x′2+x′3+…+x′9=20的正整数解个数为C■.而每一种插空方法对应着女生的A■种排列，所以所求的排法数有：C■Α■A■种.

（2）首先考虑将8个男生排成一排，共有Α■种排列方法，先将排列好的8个男生身后再排上若干个女生，将排上的女生数依次记为x1，x2，x3，…，x8，显然x1+x2+x3+…+x8=25，其中xi≥2（i=1，2，…，8）.由前面的例子可知，方程合乎要求的解有C■组，对于每一组符合要求的解对应着A■种女生的排列组成圆排列时，方法种数一共有：■·C■A■A■种.

问题的拓展：把1996个女生和10个男生排成一列，自左至右每相邻两个男生之间分别至少有4、5、6、7、8、9、10、11、12名女生，问有多少种不同的排法？

分析与解法：首先将10名男生排成一排共有A■种排法，10个男生之间可产生11个空格，为求女生的排法，先将这些空格所排的女生依次记为x1，x2，x3，…，x11. 显然有x1+x2+x3+…+x11=1996.

依题设，x1≥0，x2≥4，x3≥5，…x10≥12，x11≥0，女生插空的方法对应着方程x′1+x′2+x′3+…+x′11=1996+2-（3+4+…+11），

即x′1+x′2+x′3+…+x′11=1935的正整数的解为C■，而每一种插空的方法对应女生的排列数为A■，故所求的排列数为C■A■A■.

试想，此类题如果不结合不定方程解的个数模型来解决的话，那将会是多么复杂的而又难以解决的问题，我们不得不感叹不定方程在排列组合中解决问题的神奇之处.