隔板法在排列組合中的應用

■河南省虞城縣高級中學 何海濤

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

一、問題的提出

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

模型1.要求每盒非空

例1 某校準備組建一個由12人組成的籃球隊,這12個人來自高一年級10個班級,每個班至少1人,問分配方案共有多少種。

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

模型2.要求盒子可空

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

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

方法總結如下:

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

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

二、應用舉例

1.要求每盒至少n個元素

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

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

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

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

例4 某校準備參加今年高中的數學聯賽,把16個選手名額分配到三(1)、三(2)、三(3)、三(4)四個教學班,每班的名額不少于該班的序號數,則不同的分配方案共有多少種?

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

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

3.求不定方程非負整數解的個數

例5 求不定方程x+y+z=12非負整數解的個數。

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

例6 求(x1+x2+…+x5)10的展開式中共有多少項。

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

則該問題轉化為求不定方程k1+k2+k3+k4+k5=10的非負整數解的個數,根據例5不難得到方程非負整數解的個數為C414,故(x1+x2+…+x5)10的展開式中共有C414項。

所以,(x1+x2+…+x5)10的展開式中共有1001項。