例題】若有A、B、C、D、E五個(gè)人排隊(duì),要求A和B兩個(gè)人必須不站在一起,則有多少排隊(duì)方法?
解析:題中要求AB兩人不站在一起,所以可以先將除A和B之外的3個(gè)人排成一排,方法數(shù)為
然后再將A和B分別插入到其余3個(gè)人排隊(duì)所形成的4個(gè)空中,也就是從4個(gè)空中挑出兩個(gè)并排上兩個(gè)人,其方法數(shù)為
因此總方法數(shù)
【例題】8個(gè)人排成一隊(duì),要求甲乙必須相鄰且與丙不相鄰,有多少種方法?
解析:甲乙相鄰,可以捆綁看作一個(gè)元素,但這個(gè)整體元素又和丙不相鄰,所以先不排這個(gè)甲乙丙,而是排剩下的5個(gè)人,方法數(shù)為
然后再將甲乙構(gòu)成的整體元素及丙這兩個(gè)元素插入到此前5人所形成的6個(gè)空里,方法數(shù)為
另外甲乙兩個(gè)人內(nèi)部還存在排序要求為
故總方法數(shù)為
【練習(xí)】5個(gè)男生3個(gè)女生排成一排,要求女生不能相鄰,有多少種方法?
注釋:將要求不相鄰元素插入排好元素時(shí),要注釋是否能夠插入兩端位置。
【例題】若有A、B、C、D、E五個(gè)人排隊(duì),要求A和B兩個(gè)人必須不站在一起,且A和B不能站在兩端,則有多少排隊(duì)方法?
解析:原理同前,也是先排好C、D、E三個(gè)人,然后將A、B查到C、D、E所形成的兩個(gè)空中,因?yàn)锳、B不站兩端,所以只有兩個(gè)空可選,方法總數(shù)為
注釋:對于捆綁法和插空法的區(qū)別,可簡單記為“相鄰問題捆綁法,不鄰問題插空法”。
三、插板法
精要:所謂插板法,指在解決若干相同元素分組,要求每組至少一個(gè)元素時(shí),采用將比所需分組數(shù)目少1的板插入元素之間形成分組的解題策略。
提醒:其首要特點(diǎn)是元素相同,其次是每組至少含有一個(gè)元素,一般用于組合問題中。
【例題】將8個(gè)完全相同的球放到3個(gè)不同的盒子中,要求每個(gè)盒子至少放一個(gè)球,一共有多少種方法?
解析:解決這道問題只需要將8個(gè)球分成三組,然后依次將每一組分別放到一個(gè)盒子中即可。因此問題只需要把8個(gè)球分成三組即可,于是可以講8個(gè)球排成一排,然后用兩個(gè)板查到8個(gè)球所形成的空里,即可順利的把8個(gè)球分成三組。其中第一個(gè)板前面的球放到第一個(gè)盒子中,第一個(gè)板和第二個(gè)板之間的球放到第二個(gè)盒子中,第二個(gè)板后面的球放到第三個(gè)盒子中去。因?yàn)槊總€(gè)盒子至少放一個(gè)球,因此兩個(gè)板不能放在同一個(gè)空里且板不能放在兩端,于是其放板的方法數(shù)是
(板也是無區(qū)別的)
【例題】有9顆相同的糖,每天至少吃1顆,要4天吃完,有多少種吃法?
解析:原理同上,只需要用3個(gè)板插入到9顆糖形成的8個(gè)內(nèi)部空隙,將9顆糖分成4組且每組數(shù)目不少于1即可。因而3個(gè)板互不相鄰,其方法數(shù)為法數(shù)為
解析:題中要求AB兩人不站在一起,所以可以先將除A和B之外的3個(gè)人排成一排,方法數(shù)為
然后再將A和B分別插入到其余3個(gè)人排隊(duì)所形成的4個(gè)空中,也就是從4個(gè)空中挑出兩個(gè)并排上兩個(gè)人,其方法數(shù)為
因此總方法數(shù)
【例題】8個(gè)人排成一隊(duì),要求甲乙必須相鄰且與丙不相鄰,有多少種方法?
解析:甲乙相鄰,可以捆綁看作一個(gè)元素,但這個(gè)整體元素又和丙不相鄰,所以先不排這個(gè)甲乙丙,而是排剩下的5個(gè)人,方法數(shù)為
然后再將甲乙構(gòu)成的整體元素及丙這兩個(gè)元素插入到此前5人所形成的6個(gè)空里,方法數(shù)為
另外甲乙兩個(gè)人內(nèi)部還存在排序要求為
故總方法數(shù)為
【練習(xí)】5個(gè)男生3個(gè)女生排成一排,要求女生不能相鄰,有多少種方法?
注釋:將要求不相鄰元素插入排好元素時(shí),要注釋是否能夠插入兩端位置。
【例題】若有A、B、C、D、E五個(gè)人排隊(duì),要求A和B兩個(gè)人必須不站在一起,且A和B不能站在兩端,則有多少排隊(duì)方法?
解析:原理同前,也是先排好C、D、E三個(gè)人,然后將A、B查到C、D、E所形成的兩個(gè)空中,因?yàn)锳、B不站兩端,所以只有兩個(gè)空可選,方法總數(shù)為
注釋:對于捆綁法和插空法的區(qū)別,可簡單記為“相鄰問題捆綁法,不鄰問題插空法”。
三、插板法
精要:所謂插板法,指在解決若干相同元素分組,要求每組至少一個(gè)元素時(shí),采用將比所需分組數(shù)目少1的板插入元素之間形成分組的解題策略。
提醒:其首要特點(diǎn)是元素相同,其次是每組至少含有一個(gè)元素,一般用于組合問題中。
【例題】將8個(gè)完全相同的球放到3個(gè)不同的盒子中,要求每個(gè)盒子至少放一個(gè)球,一共有多少種方法?
解析:解決這道問題只需要將8個(gè)球分成三組,然后依次將每一組分別放到一個(gè)盒子中即可。因此問題只需要把8個(gè)球分成三組即可,于是可以講8個(gè)球排成一排,然后用兩個(gè)板查到8個(gè)球所形成的空里,即可順利的把8個(gè)球分成三組。其中第一個(gè)板前面的球放到第一個(gè)盒子中,第一個(gè)板和第二個(gè)板之間的球放到第二個(gè)盒子中,第二個(gè)板后面的球放到第三個(gè)盒子中去。因?yàn)槊總€(gè)盒子至少放一個(gè)球,因此兩個(gè)板不能放在同一個(gè)空里且板不能放在兩端,于是其放板的方法數(shù)是
(板也是無區(qū)別的)
【例題】有9顆相同的糖,每天至少吃1顆,要4天吃完,有多少種吃法?
解析:原理同上,只需要用3個(gè)板插入到9顆糖形成的8個(gè)內(nèi)部空隙,將9顆糖分成4組且每組數(shù)目不少于1即可。因而3個(gè)板互不相鄰,其方法數(shù)為法數(shù)為