隔板法ppt課件

1、一、將一、將n件相同物品（或名額）分給件相同物品（或名額）分給m個(gè)人（或個(gè)人（或位置），每人（或位置）必須有物品問(wèn)題位置），每人（或位置）必須有物品問(wèn)題例如：某校組建一球隊(duì)需16人，該校共10個(gè)班級(jí)，且每個(gè)班至少分配一個(gè)名額,共有幾種情況？ 解:C（16-1），（10-1）=C（15，9）=1816214400種 歸納：歸納：練習(xí)、將練習(xí)、將20個(gè)優(yōu)秀學(xué)生名額分給個(gè)優(yōu)秀學(xué)生名額分給18個(gè)班，每班至少個(gè)班，每班至少1個(gè)名額，有多少種不同的分配方法？個(gè)名額，有多少種不同的分配方法？ 二、二、將將n n件相同物品（或名額）分給件相同物品（或名額）分給m m個(gè)人（或位個(gè)人（或位置），允許若干個(gè)人（或位

2、置）為空的問(wèn)題置），允許若干個(gè)人（或位置）為空的問(wèn)題. .例例2、將將10個(gè)大小形狀完全相同的小球放入個(gè)大小形狀完全相同的小球放入3個(gè)不同個(gè)不同的盒子，允許有盒子為空，但球必須放完，有多少的盒子，允許有盒子為空，但球必須放完，有多少種不同的方法？種不同的方法？分析：本題中的小球大小形狀完全相同，故這些分析：本題中的小球大小形狀完全相同，故這些小球沒(méi)有區(qū)別，問(wèn)題等價(jià)于將小球分成三組，允小球沒(méi)有區(qū)別，問(wèn)題等價(jià)于將小球分成三組，允許有若干組無(wú)元素，用隔板法許有若干組無(wú)元素，用隔板法.歸納：歸納：練習(xí)：把8個(gè)相同的球放入4個(gè)不同的盒子，有多少種不同方法？ 應(yīng)用應(yīng)用1 (1)12個(gè)相同的小球放入編號(hào)為個(gè)

3、相同的小球放入編號(hào)為1、2、3、4的盒子中，的盒子中，問(wèn)每個(gè)盒子中至少有一個(gè)小球的不同放法有多少種問(wèn)每個(gè)盒子中至少有一個(gè)小球的不同放法有多少種? (2)12個(gè)相同的小球放入編號(hào)為個(gè)相同的小球放入編號(hào)為1、2、3、4的盒子中，的盒子中，每盒可空，問(wèn)不同的放法有多少種每盒可空，問(wèn)不同的放法有多少種? (3)12個(gè)相同的小球放入編號(hào)為個(gè)相同的小球放入編號(hào)為1、2、3、4的盒子中，的盒子中，要求每個(gè)盒子中的小球數(shù)不小于其編號(hào)數(shù)，問(wèn)不同的放要求每個(gè)盒子中的小球數(shù)不小于其編號(hào)數(shù)，問(wèn)不同的放法有多少種法有多少種? 解：解：(1)將將12個(gè)小球排成一排，中間有個(gè)小球排成一排，中間有11個(gè)間隔，在這個(gè)間隔，在這

4、11個(gè)間隔中選出個(gè)間隔中選出3個(gè)，放上個(gè)，放上“隔板隔板”，這樣每一種隔板的插，這樣每一種隔板的插法，就對(duì)應(yīng)了球的一種放法，即每一種從法，就對(duì)應(yīng)了球的一種放法，即每一種從11個(gè)間隔中選個(gè)間隔中選出了出了3個(gè)間個(gè)間 隔的組合對(duì)應(yīng)于一種放法，所以不同的放法有隔的組合對(duì)應(yīng)于一種放法，所以不同的放法有C（11，3）=165(種種)。 2)由隔板法可知：由隔板法可知：C(15,3)=455種。種。(3)解法一：用解法一：用(1)的處理問(wèn)題的方法。的處理問(wèn)題的方法。 將將1個(gè)、個(gè)、2個(gè)、個(gè)、3個(gè)個(gè)小球放入編號(hào)為小球放入編號(hào)為2、3、4的盒子中，將余下的的盒子中，將余下的6個(gè)小球放個(gè)小球放在在4個(gè)盒子中，每個(gè)盒子至少一個(gè)小球，據(jù)個(gè)盒子中，每個(gè)盒子至少一個(gè)小球，據(jù)(1)有有C(5,3)=10(種種)。 解法解法(2)：用：用(2)的處理問(wèn)題的分法。的處理問(wèn)題的分法。 將將1個(gè)、個(gè)、2個(gè)、個(gè)、3個(gè)、個(gè)、4個(gè)小球分別放在編號(hào)為個(gè)小球分別放在編號(hào)為1、2、3、4的盒子中，的盒子中，將余下的將余