用不定方程求解排列组合问题

邢雅峰

【摘要】本文主要介绍如何利用不定方程求解排列组合问题，如果我们把这种方法教给学生，不但可以拓宽学生的解题思想和方法，而且还可以让学生更加深刻地理解问题.

【关键词】不定方程;整数解;排列组合问题

许多排列组合问题若能转换思考角度，转化为不定方程整数解的模型，则能化繁为简.

一、初步探讨不定方程解的数量随限制条件增多（或变严格）变化的规律

探讨以下三个题目：

1.方程x+y+z=10有多少组解？

2.方程x+y+z=10有多少组正整数解？

3.方程x+y+z=10有多少组非负整数解？

分析 三个题目研究的是同一个方程，由于有3个未知数，却只有一个方程，所以是个不定方程.区别在于，第1个问题中没有任何限制条件，而后两个问题的限制条件逐渐加强.那么它们的解的组数有什么变化规律呢？

若一个不定方程没有其他限制条件，则有无数组解，这是显而易见的.如果逐渐加上限制条件，情况就会有所不同.

我们先看第2题，因为这个问题容易.我们将其转化成熟悉的模式：“将10个球放入3个盒子中，每个盒子中至少放一个球，则有多少种放法？”这显然是一道隔板法的题目.相当于在10个球的9个空隙中插入2块板子，这样就可将10个球放入3个部分，且每个部分都有球.因此，方法数为C29=9×82×1=36，即方程的正整数解有36组.

如果限制条件略为宽松些，不是求正整数解了，而是求非负整数解，这样方程的解除了可以是正整数外，还可以是0，这时，如果再盲目套用刚才的方法，容易搞乱，因为你不知道有几个盒子可以不放球，也不知道是哪个盒子可以不放球，抑或是三个盒子都放球，因此，讨论起来就很麻烦.因此，我们可以这样想：如果预先在三个盒子中先各放一个球，这时就可成功地将问题转化为10+3=13个球放入三个盒子中，每个盒子中至少有一个球，有多少种放法？解法很简单：C212=12×112×1=66，对应到第2题，即原方程有66组非负整数解.

那么对一般的不定方程又如何呢？通过探索，我们有如下结论：

二、不定方程整数解的有关结论

命题1 不定方程x1+x2+…+xm=n（n≥m）共有Cm-1n-1组不同的正整数解.

证明 由题意可知，方程可以看作将n个元素分成m组的问题.n个元素中间（n-1）个空档，在其中选取（m-1）个放入隔板即可，共有Cm-1n-1种做法，即方程解的組数为Cm-1n-1.

注意：命题对xi（i=1，2，…，n）的基本要求为xi≥1，xi∈N*.

命题2 不定方程x1+x2+…+xm=n（n≥0）共有Cm-1n+m-1组不同的非负整数解.

证明 （x1+1）+（x2+1）+…+（xm+1）=n+m，记yi=xi+1（i=1，2，…，m）.

则y1+y2+…+ym=n+m，yi≥1（i=1，2，…，m）.

由命题1，此方程共有Cm-1n+m-1组不同的正整数解，即原不定方程共有Cm-1n+m-1组不同的非负整数解.

通过以上探索，我们得到：在求解不定方程的时候，若能通过“一一对应”关系找到其组合解释，则不定方程的求解会显得更加形象、直观.反之，若遇到组合问题，则可以构造不定方程来求解，可谓两种思路相得益彰.

三、利用不定方程整数解的结论解排列组合中的计数问题

用不定方程整数解的结论解排列组合中的计数问题，一般用于相同元素的分配问题.

例1 把2 017个不加区别的小球分别放在10个不同的盒子里，使得第i个盒子里至少有i个球（i=1，2，…，10），不同放法有多少种？

解析 先在第i个盒子里放入i个球（i=1，2，…，10），即第1个盒子里放入1个球，第2个盒子里放入2个球，…，这时共放了1+2+3+…+10=55个球，还剩余2 017-55=1 962个球.故问题转化为把1 962个球任意放入10个盒子里（允许有的盒子里不放球），即不定方程x1+x2+…+x10=1 962的非负整数解的个数.由结论2可知有C19621962+10-1=C91971种不同的放法.

例2 试问（a+b+c）9的展开式共有多少项？

解析 （a+b+c）9展开式的每一项均可表示为ax1·bx2·cx3，其中xi≥0（i=1，2，3）且x1+x2+x3=9.因此，求展开式中共有多少项，即求不定方程x1+x2+x3=9共有多少组非负整数解.由结论2知，此不定方程解的个数为C99+3-1=C211=55，所以展开式共有55项.

例3 某企业与一家电视台签订了一项播放广告的协议，电视台须在90天内播出这一广告600次，而且每天至少6次，就每天播出广告的次数而言，共有多少种播法？

解析 设每天播出广告的次数为x1，x2，x3，…，x90，则x1+x2+x3+…+x90=600且xi≥6（i=1，2，…，90），令yi=xi-5，

则y1+y2+…+y90=x1+x2+…+x90-90×5=150，

原问题转化为求不定方程y1+y2+…+y90=150有多少组正整数解.

由结论1知，共有C90-1150-1=C89149种播法.

例4 9个女孩和28个男孩围成一圈，任意两个女孩之间至少站两个男孩，那么，共有多少种不同的排列方法？

解析 以9个女孩为组长，将28个男孩分入9个组，每组男孩数记为x1，x2，x3，…，x9，则x1+x2+x3+…+x9=28（xi≥2，i=1，2，…，9），令yi=xi-1，

即y1+y2+…+y9=x1+x2+…+x9-9×1=19（yi≥1，i=1，2，…，9），由结论1知，共有C9-119-1=C818种不同的方法.9个组排成每组以女孩为组长的圆的排列有（9-1）！=8！，再将28个男孩全排列有28！，所以共有C818·8！·28！种不同的排列方法.

以上几个例子，通过适当的构造，开辟了一条新的解题思路，把排列组合问题转化为求不定方程的整数解的问题，不仅解决了问题，而且更深刻地理解了题意.当然，解题的关键是建立不定方程模型.

【参考文献】

[1]石向阳.构建不定方程模型解决计数问题[J].中学数学杂志，2016（5）：43-46.

[2]蒋彩荣.利用不定方程解一类排列组合问题[J].数学通报，2004（8）：36.