在教學(xué)組合內(nèi)容時(shí),時(shí)常遇到用插空法解題及涉及重復(fù)元素的組合數(shù)問題,現(xiàn)舉例看兩道題。
題目1:把n個(gè)相同的小球分給m(m≤n)個(gè)人,每人至少1個(gè),有多少種不同的方法?
題目2:把n個(gè)相同的小球放入m個(gè)有編號(hào)的小盒,每盒容量不限,有多少種不同的放法?
解決題目1,涉及插空法;
解決題目2,涉及一個(gè)定理。
定理1:在集A={a ,a ,a ,……,a }中,每次取r個(gè)元素有重復(fù)的組合為:H=C,證明詳見周萬(wàn)詳編著的初等數(shù)學(xué)研究書《排列組合與數(shù)列》。
現(xiàn)在我們就來(lái)談?wù)動(dòng)貌蹇辗ń鉀Q的組合題型及可轉(zhuǎn)化為有重復(fù)元素的組合數(shù)的題型。
一、用插空法解題
1.人排隊(duì)時(shí)不相鄰問題
例:13個(gè)人排成一排,其中A、B、C兩兩不相鄰,問有幾種不同排法?
分析:
(1)可先將A、B、C以外的10人排成一排,即A;
(2)10個(gè)人有11個(gè)空(含兩端),A、B、C去插這11個(gè)空,每人1空,即C;
(3)再將A、B、C進(jìn)行全排列即A,所以排法數(shù)為ACA=AA。
小結(jié):n個(gè)人排成一排,其中m人(m≤ )兩兩不相鄰,則有:AAA=A種不同的排法。
分析:先將余下的n-m人進(jìn)行全排列,從n-m+1個(gè)空中選出m個(gè),這m人每人站一個(gè)空,再將m人進(jìn)行全排列。
2.座位不相鄰問題
例:10個(gè)相鄰的座位,甲、乙每人坐1個(gè)位子且不相鄰,問有幾種不同坐法?
分析:
方法一:直接法
(1)當(dāng)甲選了兩邊之一時(shí),有C種選法,乙有C種選法;(2)當(dāng)甲未選兩邊時(shí),有C種選法,乙有C種選法,所以所求的坐法有CC+CC=72種。
方法二:間接法
總數(shù)-甲乙相鄰=甲乙不相鄰
總數(shù)為:CA=A;甲乙相鄰為:CA(因?yàn)閮蓚€(gè)座位相鄰的情況數(shù)有9種,故為C;而甲乙講順次,故為A);所以所求的分法數(shù)為:A-CA=72種。
3.分物時(shí)每人至少1份問題
例:把10個(gè)相同的小球分給4個(gè)人,每人至少1個(gè),有多少種不同的分法?
分析:10個(gè)球有11個(gè)空,除兩端外有9個(gè)空,在9個(gè)空中插入3人,每人插一個(gè)空,將小球分成4份,每人一份,所以不同的分法有C=C種。
如:
11*1111*111*1
甲乙丙丁
甲有2個(gè),乙有4個(gè),丙有3個(gè),丁有1個(gè)。
小結(jié):把n份相同的物品分給m(m≤n)人,每人至少1份則有C種不同的分法。
二、涉及允許重復(fù)選取元素的組合
例:3個(gè)人6種不同的卡片,每種均有多張,每人限選1張,有幾種選法?
方法一:有3個(gè)人和6種卡片,這3個(gè)人可以選同一種,也可以選2種,還可以選3種,由此可知,這個(gè)問題的實(shí)質(zhì)就是在6種不同的卡片里任意選3張,但這3張卡片可以重復(fù),屬于可以重復(fù)選取的重復(fù)組合問題,由定理1可知所求選法有H=C=C=56種。
方法二:因?yàn)檫@3張卡片可以是同一種,2種,3種,分為3類:①選1種,即C=6。②選2種,即C,假如選到A、B張,但可能會(huì)A張1人,B張2人;也可能會(huì)A張2人,B張1人,故有2種情況,所以為2C=30。③選3種,即C=20。
所以總的選法有C+2C+C=6+30+20=56種。
小結(jié):n個(gè)人選m種不同的東西,每種有多件,每人限選一件,則有H=C種不同選法。
例:將5個(gè)相同的小球放入7個(gè)有編號(hào)的小盒,每盒容量不限,有多少種方法?
分析:有5個(gè)小球和7個(gè)小盒,這5個(gè)小球可以選同一個(gè)盒子,也可以選2個(gè),3個(gè),4個(gè)或者5個(gè)盒子,由此可知,這個(gè)問題的實(shí)質(zhì)就是在7個(gè)不同的小盒里任取5個(gè),但這5個(gè)可以重復(fù),屬于可以重復(fù)選取的重復(fù)組合問題,由定理1可知所求方法為H=C=C種。
小結(jié):將n樣相同的東西,放在m樣不同的容量里,每個(gè)容器數(shù)量不限,則有H=C種放法。
注:“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文?!?/p>