石向陽(yáng)

許多組合問(wèn)題看似與方程無(wú)關(guān)，若能去偽存真，轉(zhuǎn)換思維角度，轉(zhuǎn)化為不定方程整數(shù)解的模型，則往往能化繁為簡(jiǎn)、柳暗花明.1不定方程整數(shù)解的有關(guān)結(jié)論

定理1不定方程x1+x2+…+xk=n（k，n∈N+）的非負(fù)整數(shù)解的個(gè)數(shù)為Cnn+k-1.

證法1將不定方程x1+x2+…+xk=n的任意一組非負(fù)整數(shù)解（x1，x2，…，xk）對(duì)應(yīng)于一個(gè)由n個(gè)圓圈“○”和k-1個(gè)“+”組成的如圖○…○x1個(gè)+○…○x2個(gè)+…+○…○xk個(gè)所示的排列，每段圓圈“○”的個(gè)數(shù)即為原方程的一組非負(fù)整數(shù)解，易證對(duì)應(yīng)關(guān)系是一對(duì)一的.

所以不定方程x1+x2+…+xk=n的非負(fù)整數(shù)解的個(gè)數(shù)就是n個(gè)圓圈“○”和k-1個(gè)“+”組成的直線排列數(shù)，即在n+k-1個(gè)位置中選k-1放置“+”（或選n個(gè)位置放置圓圈“○”），因此共有不同的排法種數(shù)為Ck-1n+k-1=Cnn+k-1.

證法2對(duì)不定方程x1+x2+…+xk=n的任意一組非負(fù)整數(shù)解（x1，x2，…，xk），令y1=x1+1，y2=x1+x2+2，…，yk=x1+x2+…+xk+k，則1≤y1

定理2不定方程x1+x2+…+xk=n（k≥2，n≥2，k≤n）的正整數(shù)解的個(gè)數(shù)為Ck-1n-1.

證法1設(shè)想將n個(gè)1排成一排，這n個(gè)1之間有n-1個(gè)空檔，從n-1個(gè)空檔中選k-1個(gè)放入k-1個(gè)“+”，共有Ck-1n-1種放法，這k-1個(gè)“+”把n個(gè)1分成k段，各段1的個(gè)數(shù)即為原方程的一組正整數(shù)解，這樣“+”的每一種放法就對(duì)應(yīng)著原不定方程的一組正整數(shù)解，所以原不定方程共有Ck-1n-1組解.

證法2令yi=xi-1，其中xi≥1，不定方程x1+x2+…+xk=n的正整數(shù)解與不定方程y1+y2+…+yk=n-k非負(fù)整數(shù)解之間建立了一一對(duì)應(yīng)關(guān)系，所以不定方程x1+x2+…+xk=n的正整數(shù)解組（x1，x2，…，xk）的組數(shù)與不定方程y1+y2+…+yk=n-k非負(fù)整數(shù)解組（y1，y2，…，yk）的組數(shù)相等，由定理1知，方程y1+y2+…+yk=n-k有Cn-k（n-k）+k-1=Cn-kn-1=Ck-1n-1個(gè)非負(fù)整數(shù)解，所以方程x1+x2+…+xk=n有Ck-1n-1個(gè)正整數(shù)解.2利用不定方程整數(shù)解的結(jié)論解有限制條件的不定方程或不定方程組的整數(shù)解的個(gè)數(shù)問(wèn)題

例1求方程2x1+x2+x3+…+x10=3的非負(fù)整數(shù)解的個(gè)數(shù).

解析由題意，x1=0，1，故分情況討論如下：

若x1=0，則x2+x3+…+x10=3，該方程非負(fù)整數(shù)解的個(gè)數(shù)為：C39+3-1=165；

若x1=1，則x2+x3+…+x10=1，該方程非負(fù)整數(shù)解的個(gè)數(shù)為：C19+1-1=9.

綜上，非負(fù)整數(shù)解的個(gè)數(shù)為：165+9=174個(gè).

例2求方程x+y+z=2010滿足x≤y≤z的正整數(shù)解x，y，z的個(gè)數(shù).

解析首先由定理2知，方程x+y+z=2010的正整數(shù)解的個(gè)數(shù)為C22009=2009×1004.

把x+y+z=2010滿足x≤y≤z的正整數(shù)解分為三類：

1x，y，z均相等的正整數(shù)解的個(gè)數(shù)顯然為1；

2x，y，z中有且僅有兩個(gè)相等的正整數(shù)解的個(gè)數(shù)，易知為1003個(gè)；

3x，y，z兩兩均不相等的正整數(shù)解個(gè)數(shù)為k.

易知1+3×1003+6k=2009×1004，解得k=335671，從而方程x+y+z=2010滿足x≤y≤z的正整數(shù)解的個(gè)數(shù)為1+1003+335671=336675

例3在世界杯足球賽前，F(xiàn)國(guó)教練為了考察A1，A2，…，A7這七名隊(duì)員，準(zhǔn)備讓他們?cè)谌龍?chǎng)訓(xùn)練比賽（每場(chǎng)90分鐘）中都上場(chǎng).假設(shè)在比賽的任何時(shí)刻，這些隊(duì)員中有且僅有一人在場(chǎng)上，且A1，A2，A3，A4每人上場(chǎng)的總時(shí)間（以分鐘為單位）均能被7整除，A5，A6，A7每人上場(chǎng)的總時(shí)間（以分鐘為單位）均能被13整除.如果每場(chǎng)換人次數(shù)不限，那么，按每名隊(duì)員上場(chǎng)的總時(shí)間計(jì)算，共有多少種不同的情況.

解析設(shè)第i名隊(duì)員上場(chǎng)的時(shí)間為xi分鐘（i=1，2，3，…，7），問(wèn)題即求不定方

程x1+x2+…+x7=270在條件7xi（1≤i≤4）且13xj（5≤j≤7）下的正整數(shù)解的組數(shù).由條件，設(shè)x1+x2+x3+x4=7m，x5+x6+x7=13n（m≥4，n≥3）.于是m、n即是不定方程7m+13n=270的一組正整數(shù)解.由m=270-13n7≥4，易得3≤n≤18，（n∈N）.進(jìn)而得到方程的三組正整數(shù)解：

m=33，

n=3，m=20，

n=10，m=7，

n=17，設(shè)xi=7yi（1≤i≤4），xj=13yj（5≤j≤7）.

所以本題轉(zhuǎn)化為求方程組y1+y2+y3+y4=33，

y5+y6+y7=3，y1+y2+y3+y4=20，

y5+y6+y7=10，

y1+y2+y3+y4=7，

y5+y6+y7=17，的正整數(shù)解的組數(shù).由分步乘法計(jì)數(shù)原理和分類加法計(jì)數(shù)原理及定理2知共有正整數(shù)解C332C22+C319C29+C36C216=42244組.3利用不定方程整數(shù)解的結(jié)論解排列組合中的計(jì)數(shù)問(wèn)題

利用不定方程整數(shù)解的結(jié)論解決排列組合中的計(jì)數(shù)問(wèn)題，一般用于相同元素的有序分配問(wèn)題，如指標(biāo)數(shù)、個(gè)數(shù)、人數(shù)等相同的事物的數(shù)量分配問(wèn)題.

3.1投球入盒問(wèn)題

例4把2016個(gè)不加區(qū)別的小球分別放在10個(gè)不同的盒子里，使得第i個(gè)盒子里至少有i個(gè)球（i=1，2，…，10），問(wèn)不同放法的總數(shù)是多少？

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

3.2名額分配問(wèn)題

例5將24個(gè)志愿者名額分配給3個(gè)學(xué)校，則每校至少有一個(gè)名額且各校名額互不

相同的分配方法共有多少種？解析設(shè)分配給3個(gè)學(xué)校的名額數(shù)分別為x1，x2，x3，則每校至少有一個(gè)名額的分法數(shù)為不定方程x1+x2+x3=24的正整數(shù)解的個(gè)數(shù)，由定理2得不定方程x1+x2+x3=24的正整數(shù)解的個(gè)數(shù)為C223=253.又在“每校至少有一個(gè)名額的分法”中“至少有兩個(gè)學(xué)校的名額數(shù)相同”的分配方法有31種.

綜上知，滿足條件的分配方法共有253-31=222種.

3.3染色問(wèn)題

例6用紅、橙、黃、綠、青、藍(lán)、紫七種顏色的一種，或兩種，或三種，或四種，分別涂在正四面體各個(gè)面上，一個(gè)面不能用兩色，也無(wú)一個(gè)面不著色的，問(wèn)共有幾種著色法？

解析設(shè)紅色涂了x1個(gè)面，橙色涂了x2個(gè)面，…紫色涂了x7個(gè)面，則x1+x2+…+x7=4，正四面體著色方法與方程的非負(fù)整數(shù)解建立了一一對(duì)應(yīng)的關(guān)系.由定理1知該不定方程有C47+4-1=210組非負(fù)整數(shù)解，所以正四面體共有210種著色方法.

3.4擲骰子問(wèn)題

例7三粒骰子同時(shí)擲出，有多少種不同的結(jié)果？

解析設(shè)擲出1點(diǎn)的有x1粒，設(shè)擲出2點(diǎn)的有x2粒，…，設(shè)擲出6點(diǎn)的有x6粒，則有x1+x2+…+x6=3.擲骰子的結(jié)果與方程的非負(fù)整數(shù)解建立了一一對(duì)應(yīng)的關(guān)系.由定理1知該不定方程有C36+3-1=C38=56組非負(fù)整數(shù)解，所以共有56種不同的結(jié)果.

3.5進(jìn)站問(wèn)題

例8某民航站共有1到4個(gè)入口，每個(gè)入口處每次只能進(jìn)一個(gè)人，一小組4個(gè)人進(jìn)站的方案數(shù)有多少種.

解析設(shè)第1，2，3，4個(gè)入口分別進(jìn)x1，x2，x3，x4人，則xi≥0且x1+x2+x3+x4=4，由定理1知不定方程x1+x2+x3+x4=4的非負(fù)整數(shù)解的個(gè)數(shù)C44+4-1=C37即為4個(gè)人進(jìn)站的分組方法數(shù)；由于每個(gè)入口處每次只能進(jìn)一個(gè)人，按第1，2，3，4個(gè)入口順序同時(shí)通過(guò)入口排成一列，就每一分組方法將四個(gè)人全排列有A44種方法，所以共有不同進(jìn)站方法C37·A44=840種.

3.6開(kāi)關(guān)燈問(wèn)題

例9街道上有10盞路燈，要求晚上關(guān)掉其中4盞，且為了方便行人，相鄰的路燈不允許關(guān)掉.問(wèn)共有多少種關(guān)燈的方法？

解析先考慮關(guān)著的燈，再考慮開(kāi)著的燈，如圖：○○○○，有4盞燈關(guān)著，它們之間形成了5個(gè)空，這5個(gè)空共要插進(jìn)6盞燈作為開(kāi)著的燈，設(shè)從左到右第i個(gè)空共有xi（i=1，2，3，4，5）盞燈開(kāi)著，則有x1+x2+x3+x4+x5=6，等價(jià)于（x1+1）+x2+x3+x4+（x5+1）=8（x1+1，x2，x3，x4，x5+1≥1，且xi∈N），由定理2知，共有C47=35種方法，所以共有35種開(kāi)關(guān)燈的方法.

3.7在線性規(guī)劃中整點(diǎn)個(gè)數(shù)問(wèn)題

例10在直角坐標(biāo)系xOy中，已知△ABC三邊所在直線方程分別為x=0，y=0，x+y=4，則在△ABC內(nèi)部（包括邊界）的整點(diǎn)個(gè)數(shù)是多少？

解析此類題常見(jiàn)解法是畫(huà)圖描出整點(diǎn)，然后數(shù)一下.實(shí)際上滿足題意的整點(diǎn)（x，y）必有x+y≤4，且x≥0，y≥0.若令z=4-（x+y）則z≥0且z為整數(shù).所以x+y+z=4，該方程非負(fù)整數(shù)解的組數(shù)即為整點(diǎn)個(gè)數(shù).所以整點(diǎn)個(gè)數(shù)是C44+3-1=C26=15.

3.8n項(xiàng)展開(kāi)式的項(xiàng)數(shù)問(wèn)題

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

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

同理可得（a1+a2+…+an）m展開(kāi)式共有Cmn+m-1項(xiàng).

3.9廣告問(wèn)題

例12電視臺(tái)在n天內(nèi)共播出r次商業(yè)廣告，問(wèn)若每天至少播p次廣告（np≤r），就每天播出廣告的次數(shù)而言，共有幾種播出方法？

解析設(shè)第i天播出廣告xi次，由題設(shè)知：x1+x2+…+xn=r，xi≥p（i=1，2，…，n），令yi=xi-p，則y1+y2+…+yn=r-np≥0，故問(wèn)題轉(zhuǎn)化為求上述不定方程的非負(fù)整數(shù)解的個(gè)數(shù)，由定理1知廣告播放的方法數(shù)為Cr-np（r-np）+n-1.

3.10有條件的環(huán)形排列問(wèn)題

例138個(gè)女孩和25個(gè)男孩圍成一圈，任意兩個(gè)女孩之間至少站兩個(gè)男孩，那么，共有多少種不同的排列方法.（只要把圈旋轉(zhuǎn)一下就重合的排法認(rèn)為是相同的）.

解析以8個(gè)女孩為組長(zhǎng)，將25個(gè)男孩分入該8組，每組內(nèi)男孩數(shù)記為x1，x2，…，x8，

則x1+x2+…+x8=25，（xi≥2，i=1，2，…8），設(shè)xi-1=yi（i=1，2，…，8），即得y1+y2+…+y8=17，（yi≥1，i=1，2，…，8），于是由定理2可求出符合條件的方程組的解的個(gè)數(shù)為C8-117-1=C716，即25個(gè)男孩分入8組，每組至少2人的分組方法有C716種.

8個(gè)組排成每組以女孩為頭的圓排列有（8-1）！=7?。ㄒ粋€(gè)8個(gè)元素的圓排列包括8個(gè)不同的線性排列，設(shè)8個(gè)元素的圓排列數(shù)為N，則8N=A88，所以N=A77）種排列方法，再將25個(gè)男孩站入的方法數(shù)為25！.

所以總的排列數(shù)為C716·7！·25！=16！·25！9！.

3.11比賽過(guò)程的種數(shù)問(wèn)題

例14甲乙兩隊(duì)各出7名隊(duì)員按事先排好的順序出場(chǎng)參加圍棋擂臺(tái)賽.雙方先由1號(hào)隊(duì)員比賽，負(fù)者被淘汰，勝者再與負(fù)方2號(hào)隊(duì)員比賽，……直到有一方隊(duì)員全被淘汰為止，另一方獲得勝利，形成一種比賽過(guò)程.求所有可能出現(xiàn)的比賽過(guò)程的種數(shù).

解析先考慮甲隊(duì)獲勝的比賽過(guò)程，設(shè)甲隊(duì)隊(duì)員第i號(hào)隊(duì)員勝了xi場(chǎng)，（i=1，2，…，7），則x1+x2+…+x7=7，于是甲隊(duì)獲勝的比賽過(guò)程與方程x1+x2+…+x7=7的非負(fù)整數(shù)解組（x1，x2，…，x7）構(gòu)成一一對(duì)應(yīng)，由定理1知方程x1+x2+…+x7=7有C67+6=C613組非負(fù)整數(shù)解，所以甲隊(duì)獲勝的比賽過(guò)程有C613種，同理乙隊(duì)獲勝的比賽過(guò)程也有C613種，故不同的比賽過(guò)程共有2C613=3432種.

3.12集合、映射個(gè)數(shù)問(wèn)題

例15已知兩個(gè)實(shí)數(shù)集合A={a1，a2，…，a100}與B={b1，b2，…，b50}.若從A到B的映射f使得B中每個(gè)元素都有原像，且f（a1）≤f（a2）≤…≤f（a100），求這樣的映射的個(gè)數(shù).

解析不妨設(shè)b1

例16設(shè)集合M={1，2，3，…，14}，Ma={a1，a2，a3}，Ma為M的子集，且滿足a1+6≤a2+3≤a3，求Ma的個(gè)數(shù).

解析由a1≥1，a2-a1≥3，a3-a2≥3，14-a3≥0，令a1=x1，a2-a1=x2，a3-a2=x3，14-a3=x4，則x1+x2+x3+x4=14，問(wèn)題即求不定方程在x1≥1，x2≥3，x3≥3，x4≥0下的整數(shù)解的組數(shù)，又方程轉(zhuǎn)化為x1+（x2-2）+（x3-2）+（x4+1）=11.令x1=y1，x2-2=y2，x3-2=y3，x4+1=y4，而y1+y2+y3+y4=11的正整數(shù)解的組數(shù)是C310.所以符合條件的Ma的個(gè)數(shù)有C310=120個(gè).

以上問(wèn)題雖然背景各異，但經(jīng)充分挖掘后發(fā)現(xiàn)本質(zhì)是相同的，其結(jié)果均與不定方程的整數(shù)解有一一對(duì)應(yīng)的關(guān)系.解題的關(guān)鍵是建立不定方程模型.問(wèn)題一般有三類，第一類是中間的可以一個(gè)也沒(méi)有，用定理1求解（如例4、例6、例7、例8、例10、例11、例14）；第二類是中間的個(gè)數(shù)至少有一個(gè)，用定理2求解（如例5、例9、例15）；第三類是中間的個(gè)數(shù)多于1個(gè)，這類有約束條件的相同元素的有序分配問(wèn)題，相對(duì)來(lái)講破解較難，需要通過(guò)轉(zhuǎn)化問(wèn)題才能用不定方程來(lái)處理.轉(zhuǎn)化的關(guān)鍵是使問(wèn)題變成第一個(gè)類型（如例12），當(dāng)然也可以轉(zhuǎn)化第二個(gè)類型（如例13、例16）.4不定方程非負(fù)整數(shù)解與重復(fù)組合數(shù)的關(guān)系

從k個(gè)不同的元素中，取n個(gè)允許重復(fù)的元素而不考慮其次序，被稱為從k個(gè)不同元素中取n個(gè)允許重復(fù)的組合，簡(jiǎn)稱為n-重復(fù)組合，允許重復(fù)的組合數(shù)常常記作Hnk.

設(shè)（a1，a2，…，an）是取自{1，2，…，k}中的任一n-可重復(fù)組合，并設(shè)a1≤a2≤…≤an，令bi=ai+i-1（1≤i≤n），從而b1=a1，b2=a2+1，b3=a3+2，…，bn=an+n-1，顯然下面兩組數(shù)是一對(duì)一的：

a1≤a2≤…≤an，1≤a1

設(shè)A={（a1，a2，…，an）|ai∈{1，2，…，k}，a1≤a2≤…≤an}，

B={（b1，b2，…，bn）|bi∈{1，2，…，k+n-1}，b1

其一、上述證明，與定理1的證法2大同小異，請(qǐng)仔細(xì)體味其中小異妙在何處.

其二、設(shè)n-可重復(fù)組合a1，a2，…，an中含有x1個(gè)1，x2個(gè)2，…，xk個(gè)k，則x1+x2+…+xk=n（k，n∈N+），顯然（a1，a2，…，an）與不定方程x1+x2+…+xk=n的解（x1，x2，…，xk）一一對(duì)應(yīng).

其三、允許重復(fù)的組合的典型模型是把n只相同顏色的球放到k個(gè)編號(hào)不同的盒子中，而且每個(gè)盒子放球數(shù)不加限制，xi代表第i（i=1，2，3，…，k）個(gè)盒子中所放的球的個(gè)數(shù)，那么就有x1+x2+…+xk=n（k，n∈N+），不同的放法就對(duì)應(yīng)該方程的不同的解.

對(duì)例6我們用重復(fù)的組合數(shù)來(lái)理解，易知，正四面體的相關(guān)位置，沒(méi)有先后順序，即先涂或后涂哪個(gè)面，沒(méi)有什么不同，所以是組合問(wèn)題；這四個(gè)面可以分別用一種，或兩種，或三種，或四種顏色，故是一個(gè)重復(fù)組合問(wèn)題，即可歸結(jié)為4只相同顏色的球放到7個(gè)編號(hào)不同的盒子中，每個(gè)盒子放球數(shù)不加限制，故有著色法H47=C47+4-1=210.

對(duì)例7我們用重復(fù)的組合數(shù)來(lái)理解，因?yàn)閿S三粒骰子等價(jià)于從六個(gè)數(shù)1，2，3，4，5，6中允許重復(fù)的選取三個(gè)數(shù)，故不同結(jié)果的數(shù)目是H36=C36+3-1=C38=56.

從重復(fù)的組合數(shù)來(lái)理解不定方程的非負(fù)整數(shù)解，對(duì)于培養(yǎng)思維的深刻性、邏輯性大有裨益.