用不定方程求解排列組合問題

邢雅峰

【摘要】本文主要介紹如何利用不定方程求解排列組合問題，如果我們把這種方法教給學生，不但可以拓寬學生的解題思想和方法，而且還可以讓學生更加深刻地理解問題.

【關鍵詞】不定方程;整數解;排列組合問題

許多排列組合問題若能轉換思考角度，轉化為不定方程整數解的模型，則能化繁為簡.

一、初步探討不定方程解的數量隨限制條件增多（或變嚴格）變化的規律

探討以下三個題目：

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.