隔板法在排列組合中的應(yīng)用

■河南省虞城縣高級(jí)中學(xué) 何海濤

排列組合是高考的必考內(nèi)容,它聯(lián)系生活實(shí)際、題型多變、解法靈活、能力要求高,但得分率低。而排列組合中的分配問(wèn)題,是排列組合問(wèn)題中的重點(diǎn)與難點(diǎn) ,對(duì)于排列組合中涉及相同物品的分配或名額分配的問(wèn)題,若采用隔板法,則能起到事半功倍的效果。

一、問(wèn)題的提出

將n個(gè)相同的元素分到m個(gè)(n≥m)不同盒中,有多少種不同的分法?

模型1.要求每盒非空

例1 某校準(zhǔn)備組建一個(gè)由12人組成的籃球隊(duì),這12個(gè)人來(lái)自高一年級(jí)10個(gè)班級(jí),每個(gè)班至少1人,問(wèn)分配方案共有多少種。

解析:將問(wèn)題抽象為:12個(gè)相同的小球,分配給10個(gè)不同的班級(jí),也就是將12個(gè)小球排成一排,在其兩兩之間的11個(gè)空中任取9個(gè)插上隔板,這樣就將12個(gè)小球分成了10組,分隔成的10個(gè)小組的球的個(gè)數(shù)與名額分配數(shù)相等,則隔板插入的方法數(shù)就等于名額分配方案數(shù),共有C911=55(種)分法。

模型2.要求盒子可空

例2 將8個(gè)相同的小球放入4個(gè)不同的盒子中,盒子可空,有多少種不同的方法?

解析:首先設(shè)想每個(gè)盒子中借來(lái)1個(gè)球,共用去4個(gè)球,若某盒最后分得結(jié)果為n個(gè)(n≥1),則代表原來(lái)8個(gè)相同的小球分入該盒n-1個(gè)球,則原問(wèn)題等價(jià)于“將12個(gè)相同的小球放入4個(gè)不同盒子中,每盒至少一個(gè)小球”,由例1知方法數(shù)為C311=165。

方法總結(jié)如下:

模型1:將n個(gè)相同的元素分裝到m個(gè)不同盒中(n≥m),每個(gè)盒子至少1個(gè)元素,方法數(shù)為Cm-1n-1。

模型2:將n個(gè)相同的元素分裝到m個(gè)不同的盒中,盒子可空,則方法數(shù)為Cm-1n+m-1。

二、應(yīng)用舉例

1.要求每盒至少n個(gè)元素

例3 將20本相同的書(shū)分給4名學(xué)生,要求每名學(xué)生至少3本,有多少種不同的分法。

解法1:可以將問(wèn)題轉(zhuǎn)化為模型1,首先每人分得相同的2本,然后從剩下的12本按照模型1的方法分配分給4個(gè)人,則有C311=165(種)分法。

解法2:可以將問(wèn)題轉(zhuǎn)化為模型2,首先每人分得相同的3本,然后從剩下的8本按照模型2的方法分配分給4個(gè)人,則有C4-18+4-1=C311=165(種)分法。

2.要求每盒分別有n1,n2…,nm個(gè)元素

例4 某校準(zhǔn)備參加今年高中的數(shù)學(xué)聯(lián)賽,把16個(gè)選手名額分配到三(1)、三(2)、三(3)、三(4)四個(gè)教學(xué)班,每班的名額不少于該班的序號(hào)數(shù),則不同的分配方案共有多少種?

解法1:可以將問(wèn)題轉(zhuǎn)化為模型1,首先三(2)班分得1個(gè)名額,三(3)班分得2個(gè)名額,三(4)班分得3個(gè)名額,再將剩余的10個(gè)相同的名額分配給4個(gè)班級(jí),每個(gè)班級(jí)至少有1個(gè)名額,按照模型1的方法共有C39=84(種)分配方案。

解法2:可以將問(wèn)題轉(zhuǎn)化為模型2,首先三(1)班分得1個(gè)名額,三(2)班分得2個(gè)名額,三(3)班分得3個(gè)名額,三(4)班分得4個(gè)名額,再將剩余的6個(gè)相同的名額分配給4個(gè)班級(jí),按照模型2的方法共有C4-16+4-1=C39=84(種)分配方案。

3.求不定方程非負(fù)整數(shù)解的個(gè)數(shù)

例5 求不定方程x+y+z=12非負(fù)整數(shù)解的個(gè)數(shù)。

解析:將x、y、z分別看成是x個(gè)1,y個(gè)1,z個(gè)1組成,則共有12個(gè)1,問(wèn)題轉(zhuǎn)化為模型2,將12個(gè)1分給3個(gè)對(duì)象x、y、z,允許有空,則不同的分配方法有ffff93=91(種),不定方程非負(fù)整數(shù)解的個(gè)數(shù)為91個(gè)。

例6 求(x1+x2+…+x5)10的展開(kāi)式中共有多少項(xiàng)。

解析:(x1+x2+…+x5)10的展開(kāi)式中的通項(xiàng)公式為k3+k4+k5=10(k1、k2、k3、k4、k5∈Z)。

則該問(wèn)題轉(zhuǎn)化為求不定方程k1+k2+k3+k4+k5=10的非負(fù)整數(shù)解的個(gè)數(shù),根據(jù)例5不難得到方程非負(fù)整數(shù)解的個(gè)數(shù)為C414,故(x1+x2+…+x5)10的展開(kāi)式中共有C414項(xiàng)。

所以,(x1+x2+…+x5)10的展開(kāi)式中共有1001項(xiàng)。