用不定方程求解排列組合問(wèn)題

邢雅峰

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

【關(guān)鍵詞】不定方程;整數(shù)解;排列組合問(wèn)題

許多排列組合問(wèn)題若能轉(zhuǎn)換思考角度，轉(zhuǎn)化為不定方程整數(shù)解的模型，則能化繁為簡(jiǎn).

一、初步探討不定方程解的數(shù)量隨限制條件增多（或變嚴(yán)格）變化的規(guī)律

探討以下三個(gè)題目：

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

2.方程x+y+z=10有多少組正整數(shù)解？

3.方程x+y+z=10有多少組非負(fù)整數(shù)解？

分析 三個(gè)題目研究的是同一個(gè)方程，由于有3個(gè)未知數(shù)，卻只有一個(gè)方程，所以是個(gè)不定方程.區(qū)別在于，第1個(gè)問(wèn)題中沒(méi)有任何限制條件，而后兩個(gè)問(wèn)題的限制條件逐漸加強(qiáng).那么它們的解的組數(shù)有什么變化規(guī)律呢？

若一個(gè)不定方程沒(méi)有其他限制條件，則有無(wú)數(shù)組解，這是顯而易見(jiàn)的.如果逐漸加上限制條件，情況就會(huì)有所不同.

我們先看第2題，因?yàn)檫@個(gè)問(wèn)題容易.我們將其轉(zhuǎn)化成熟悉的模式：“將10個(gè)球放入3個(gè)盒子中，每個(gè)盒子中至少放一個(gè)球，則有多少種放法？”這顯然是一道隔板法的題目.相當(dāng)于在10個(gè)球的9個(gè)空隙中插入2塊板子，這樣就可將10個(gè)球放入3個(gè)部分，且每個(gè)部分都有球.因此，方法數(shù)為C29=9×82×1=36，即方程的正整數(shù)解有36組.

如果限制條件略為寬松些，不是求正整數(shù)解了，而是求非負(fù)整數(shù)解，這樣方程的解除了可以是正整數(shù)外，還可以是0，這時(shí)，如果再盲目套用剛才的方法，容易搞亂，因?yàn)槟悴恢烙袔讉€(gè)盒子可以不放球，也不知道是哪個(gè)盒子可以不放球，抑或是三個(gè)盒子都放球，因此，討論起來(lái)就很麻煩.因此，我們可以這樣想：如果預(yù)先在三個(gè)盒子中先各放一個(gè)球，這時(shí)就可成功地將問(wèn)題轉(zhuǎn)化為10+3=13個(gè)球放入三個(gè)盒子中，每個(gè)盒子中至少有一個(gè)球，有多少種放法？解法很簡(jiǎn)單：C212=12×112×1=66，對(duì)應(yīng)到第2題，即原方程有66組非負(fù)整數(shù)解.

那么對(duì)一般的不定方程又如何呢？通過(guò)探索，我們有如下結(jié)論：

二、不定方程整數(shù)解的有關(guān)結(jié)論

命題1 不定方程x1+x2+…+xm=n（n≥m）共有Cm-1n-1組不同的正整數(shù)解.

證明 由題意可知，方程可以看作將n個(gè)元素分成m組的問(wèn)題.n個(gè)元素中間（n-1）個(gè)空檔，在其中選取（m-1）個(gè)放入隔板即可，共有Cm-1n-1種做法，即方程解的組數(shù)為Cm-1n-1.

注意：命題對(duì)xi（i=1，2，…，n）的基本要求為xi≥1，xi∈N*.

命題2 不定方程x1+x2+…+xm=n（n≥0）共有Cm-1n+m-1組不同的非負(fù)整數(shù)解.

證明 （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組不同的正整數(shù)解，即原不定方程共有Cm-1n+m-1組不同的非負(fù)整數(shù)解.

通過(guò)以上探索，我們得到：在求解不定方程的時(shí)候，若能通過(guò)“一一對(duì)應(yīng)”關(guān)系找到其組合解釋，則不定方程的求解會(huì)顯得更加形象、直觀.反之，若遇到組合問(wèn)題，則可以構(gòu)造不定方程來(lái)求解，可謂兩種思路相得益彰.

三、利用不定方程整數(shù)解的結(jié)論解排列組合中的計(jì)數(shù)問(wèn)題

用不定方程整數(shù)解的結(jié)論解排列組合中的計(jì)數(shù)問(wèn)題，一般用于相同元素的分配問(wèn)題.

例1 把2 017個(gè)不加區(qū)別的小球分別放在10個(gè)不同的盒子里，使得第i個(gè)盒子里至少有i個(gè)球（i=1，2，…，10），不同放法有多少種？

解析 先在第i個(gè)盒子里放入i個(gè)球（i=1，2，…，10），即第1個(gè)盒子里放入1個(gè)球，第2個(gè)盒子里放入2個(gè)球，…，這時(shí)共放了1+2+3+…+10=55個(gè)球，還剩余2 017-55=1 962個(gè)球.故問(wèn)題轉(zhuǎn)化為把1 962個(gè)球任意放入10個(gè)盒子里（允許有的盒子里不放球），即不定方程x1+x2+…+x10=1 962的非負(fù)整數(shù)解的個(gè)數(shù).由結(jié)論2可知有C19621962+10-1=C91971種不同的放法.

例2 試問(wèn)（a+b+c）9的展開(kāi)式共有多少項(xiàng)？

解析 （a+b+c）9展開(kāi)式的每一項(xiàng)均可表示為ax1·bx2·cx3，其中xi≥0（i=1，2，3）且x1+x2+x3=9.因此，求展開(kāi)式中共有多少項(xiàng)，即求不定方程x1+x2+x3=9共有多少組非負(fù)整數(shù)解.由結(jié)論2知，此不定方程解的個(gè)數(shù)為C99+3-1=C211=55，所以展開(kāi)式共有55項(xiàng).

例3 某企業(yè)與一家電視臺(tái)簽訂了一項(xiàng)播放廣告的協(xié)議，電視臺(tái)須在90天內(nèi)播出這一廣告600次，而且每天至少6次，就每天播出廣告的次數(shù)而言，共有多少種播法？

解析 設(shè)每天播出廣告的次數(shù)為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，

原問(wèn)題轉(zhuǎn)化為求不定方程y1+y2+…+y90=150有多少組正整數(shù)解.

由結(jié)論1知，共有C90-1150-1=C89149種播法.

例4 9個(gè)女孩和28個(gè)男孩圍成一圈，任意兩個(gè)女孩之間至少站兩個(gè)男孩，那么，共有多少種不同的排列方法？

解析 以9個(gè)女孩為組長(zhǎng)，將28個(gè)男孩分入9個(gè)組，每組男孩數(shù)記為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），由結(jié)論1知，共有C9-119-1=C818種不同的方法.9個(gè)組排成每組以女孩為組長(zhǎng)的圓的排列有（9-1）！=8！，再將28個(gè)男孩全排列有28！，所以共有C818·8！·28！種不同的排列方法.

以上幾個(gè)例子，通過(guò)適當(dāng)?shù)臉?gòu)造，開(kāi)辟了一條新的解題思路，把排列組合問(wèn)題轉(zhuǎn)化為求不定方程的整數(shù)解的問(wèn)題，不僅解決了問(wèn)題，而且更深刻地理解了題意.當(dāng)然，解題的關(guān)鍵是建立不定方程模型.

【參考文獻(xiàn)】

[1]石向陽(yáng).構(gòu)建不定方程模型解決計(jì)數(shù)問(wèn)題[J].中學(xué)數(shù)學(xué)雜志，2016（5）：43-46.

[2]蔣彩榮.利用不定方程解一類排列組合問(wèn)題[J].數(shù)學(xué)通報(bào)，2004（8）：36.