排列組合之分堆問題.doc

排列組合之分堆問題（教師）引例 將6本不同的書按下列分法，各有多少種不同的分法？ 分給學(xué)生甲3 本，學(xué)生乙2本，學(xué)生丙1本； 分給甲、乙、丙3人，其中1人得3本、1人得2 本、1 人得1 本； 分給甲、乙、丙3人，每人2本； 分成3堆，一堆3 本，一堆2 本，一堆1 本； 分成3堆，每堆2 本； 分給甲、乙、丙3人，其中一人4本，另兩人每人1本； 分成3堆，其中一堆4本，另兩堆每堆1本.分析：分書過程中要分清：是均勻的還是非均勻的；是有序的還是無序的. 特別是均勻的分法中要注意算法中的重復(fù)問題.解：是指定人應(yīng)得數(shù)量的非均勻問題：學(xué)生甲從6本中取3 本有種取法，學(xué)生乙從余下的3本中取2本有種取法，學(xué)生丙從余下的1本中取1本有種取法. 所以方法數(shù)為60；是沒有指定人應(yīng)得數(shù)量的非均勻問題：從6本中取3 本作為一堆有種取法，從余下的3本中取2本作為一堆有種取法，從余下的1本中取1本作為一堆有種取法，將三堆依次分給甲乙丙三人有種分法. 所以方法數(shù)為360；是指定人應(yīng)得數(shù)量的均勻問題：學(xué)生甲從6本中取2本有種取法，學(xué)生乙從余下的4本中取2本有種取法，學(xué)生丙從余下的2本中取2本有種取法. 所以方法數(shù)為90；是分堆的非均勻問題：從6本中取3 本作為一堆有種取法，從余下的3本中取2本作為一堆有種取法，從余下的1本中取1本作為一堆有種取法. 所以方法數(shù)為60；是分堆的均勻問題：相當(dāng)于學(xué)生甲從6本中取2本有種取法，學(xué)生乙從余下的4本中取2本有種取法，學(xué)生丙從余下的2本中取2本有種取法.方法數(shù)為90.然后再取消甲乙丙的分配順序，故方法數(shù)為15；是部分均勻地分給人的問題：方法數(shù)為90； 是部分均勻地分堆的問題：方法數(shù)為15.以上問題歸納為：分給人（有序）分成堆（無序）非均勻均勻部分均勻分組（堆）問題有六個模型：有序不等分；有序等分；有序局部等分；無序不等分；無序等分；無序局部等分.是排列、組合及其應(yīng)用基本問題.在歷年的各地高考試題中都有體現(xiàn).例1 ( 2006年重慶卷理8) 將5名實(shí)習(xí)教師分配到高一年級的3個班實(shí)習(xí)，每班至少1名，最多2名，則不同的分配方案有（ ）（A）30種 （B）90種 （C）180種 （D）270種分析：這是一個有序局部等分問題. 根據(jù)題意應(yīng)先將5名實(shí)習(xí)教師按（221）分為三組，然后再將這三組依次安排到高一年級的3個班實(shí)習(xí).解：將5名實(shí)習(xí)教師分配到高一年級的3個班實(shí)習(xí)，每班至少1名，最多2名，則將5名教師分成三組，一組1人，另兩組都是2人，有種方法，再將3組依次分到3個班有種分法. 根據(jù)分步計數(shù)原理，共有種不同的分配方案，故選B.點(diǎn)評：沒有明確安排各班學(xué)校的教師分配數(shù)量時，要先將教師分成堆（組）再將各堆依次分配到班學(xué)校，簡稱為“先分組，后到位”；對于局部均勻的分堆（組），先依次選取出來再去掉均勻堆（組）選出的順序，即除以均勻堆（組）數(shù)的全排列. 例2（2007陜西理科第16題）安排3名支教老師去6所學(xué)校任教，每校至多2人，則不同的分配方案共有 種.（用數(shù)字作答）分析：根據(jù)題意應(yīng)先將3名支教老師按（111）分為三組或按（21）分為兩組，然后再將這組依次安排到學(xué)校.解：將3名支教老師按（111）分為三組有種分法，再將三組依次分到學(xué)校有種中分法，根據(jù)分步計數(shù)原理，共有1120120種不同的分配方案；將3名支教老師按（21）分為兩組有種分法，再將兩組依次分到學(xué)校有中分法，根據(jù)分步計數(shù)原理，共有33090種不同的分配方案.再由分類計數(shù)原理，共有120+90210種不同的分配方案. 故填210.點(diǎn)評：分類討論問題是考試的熱點(diǎn). 本題是將分類與分組問題巧妙的融合在了一起，同時達(dá)到考察分類計數(shù)原理和分步計數(shù)原理的目的.例3 （2007寧夏理科第16題）某校安排5個班到4個工廠進(jìn)行社會實(shí)踐，每個班去一個工廠，每個工廠至少安排一個班，不同的安排方法共有種（用數(shù)字作答）分析：5個班到4個工廠進(jìn)行社會實(shí)踐，每個班去一個工廠，每個工廠至少安排一個班，說明必有某一個工廠安排了兩個班，其余的3個工廠各有一個班，由于到一個工廠的兩個班的“地位”是等同的（無序），不能出現(xiàn)誰先進(jìn)入誰后進(jìn)入的局面，也就是說這兩個班要同時進(jìn)入（無序）到這個工廠才可以. 因此應(yīng)該先分組后到班. 解：由題意，先將5個班分為四組（2111）有種分法；再將這四組依次分配到4個工廠有種分配方法. 根據(jù)分步計數(shù)原理，共有1024240種不同的進(jìn)行社會實(shí)踐分配方案. 故填240.一般地，對于分組（堆）的問題模型，其解題思路及步驟為：明確每個人的分配數(shù)量時，依次選取即可；沒有明確安排位置的分配數(shù)量時，要先分堆（組）再將各堆依次安排到對應(yīng)位置，簡稱為“先分組，后到位”；非均勻的分堆（組），依次選取出來即可；均勻的分堆（組），先依次選取出來再去掉選出的順序，即除以堆（組）數(shù)的全排列；局部均勻的分堆（組），先依次選取出來再去掉均勻堆（組）選出的順序，即除以均勻堆（組）數(shù)的全排列. 排列組合之分堆問題引例 將6本不同的書按下列分法，各有多少種不同的分法？ 分給學(xué)生甲3 本，學(xué)生乙2本，學(xué)生丙1本； 分給甲、乙、丙3人，其中1人得3本、1人得2 本、1 人得1 本； 分給甲、乙、丙3人，每人2本； 分成3堆，一堆3 本，一堆2 本，一堆1 本； 分成3堆，每堆2 本； 分給甲、乙、丙3人，其中一人4本，另兩人每人1本； 分成3堆，其中一堆4本，另兩堆每堆1本.分組（堆）問題有六個模型：有序不等分；有序等分；有序局部等分；無序不等分；無序等分；無序局部等分.是排列、組合及其應(yīng)用基本問題.在歷年的各地高考試題中都有體現(xiàn).例1（2006年重慶卷理8） 將5名實(shí)習(xí)教師分配到高一年級的3個班實(shí)習(xí)，每班至少1名，最多2名，則不同的分配方案有（ ）（A）30種 （B）90種 （C）180種 （D）270種例2（2007陜西理科第16題）安排3名支教老師去6所學(xué)校任教，每校至多2人，則不同的分配方案共有 種.（用數(shù)字作答）例3 （2007寧夏理科第16題）某校安排5個班到4個工廠進(jìn)行社會實(shí)踐，每個班去一個工廠，每個工廠至少安排一個班，不同的安排方法共有種（用數(shù)字作答）一般地，對于分組（堆）的問題模型，其解題思路及步驟為：明確每個人的分配數(shù)量時，依次選取即可；沒有明確安排位置的分配數(shù)量時，要先分