




下載本文檔
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、一.集團(tuán)排列問題:部分元素必須安排在一起(相鄰)的排列問題,稱之為“集團(tuán)排列”問題.解決這類問題,常用“捆綁法”,其方法是先排“集團(tuán)”內(nèi)部的元素,再把這個(gè)大“元素”與其它元素一起排列即可.例1若7位同學(xué)站成一排(1)甲、乙兩同學(xué)必須相鄰的排法共有多少種?(2)甲、乙和丙三個(gè)同學(xué)都相鄰的排法共有多少種?(3)甲、乙兩同學(xué)必須相鄰,而且丙不能站在排頭和排尾的排法有多少種?(4)甲、乙、丙三個(gè)同學(xué)必須站在一起,另外四個(gè)人也必須站在一起的排法有多少種?解:(1)先將甲、乙兩位同學(xué)“捆綁”在一起看成一個(gè)元素與其余的5個(gè)元素(同學(xué))一起進(jìn)行全排列有A6種方法;再將甲、乙兩個(gè)同學(xué)“松綁”進(jìn)行排列有A;種方法
2、.所以這樣的排法一共有A 6=1440種.(2)方法同上,一共有 A5 A =720種.(3)解法一:將甲、乙兩同學(xué)“捆綁”在一起看成一個(gè)元素,此時(shí)一共有6個(gè)元素,因?yàn)楸荒苷驹谂蓬^和排尾,所以可以從其余的 5個(gè)元素中選取2個(gè)元素放在排頭和排尾,有 A2種方法;將剩下的4個(gè)元素進(jìn) 行全排列有 A:種方法;最后將甲、乙兩個(gè)同學(xué)“松綁”進(jìn)行排列有A;種方法.所以這樣的排法一共有-2 - 4 - 2.、.A5 A4 A2 =960 種方法.解法二:將甲、乙兩同學(xué)“捆綁”在一起看成一個(gè)元素,此時(shí)一共有6個(gè)元素,若丙站在排頭或排尾有_5.,_6_5、_22A5種方法,所以,丙不能站在排頭和排尾的排法有(
3、A6 -2A5) A; =960種方法.解法三:將甲、乙兩同學(xué)“捆綁”在一起看成一個(gè)元素,此時(shí)一共有6個(gè)元素,因?yàn)楸荒苷驹谂蓬^和排尾,所以可以從其余的四個(gè)位置選擇共有A:種方法,再將其余的5個(gè)元素進(jìn)行全排列共有 A5種方法,最后將甲、乙兩同學(xué)“松綁”,所以,這樣的排法一共有 A4 A55 A: =960種方法.(4)將甲、乙、丙三個(gè)同學(xué)“捆綁”在一起看成一個(gè)元素,另外四個(gè)人“捆綁”在一起看成一個(gè)元素, 時(shí)一共有2個(gè)元素,一共有排法種數(shù):A3A4A2 =288 (種)說明:對(duì)于相鄰問題,常用“捆綁法”(先捆后松).二.間隔排列問題:部分元素不能安排在一起(間隔)的排列問題,稱之為“間隔排列”問
4、題.解決這類問題,常用“插空法”,其方法是先排不需要間隔的元素,再將需要間隔的元素通過插空的方式插進(jìn)來即可.例2在一條南北方向的步行街同側(cè)有8塊廣告牌,牌的底色可選用紅、藍(lán)兩種顏色.若只要求相鄰兩塊牌的底色不都為紅色,則不同的配色方案共有()A.55.B.56.C.46.D.45.解:沒有紅牌,一種方法;有一塊紅牌,讓其插空,有c;種方法;有二塊紅牌,讓其插空,有c。種方法; 有三塊紅牌,讓其插空,有c;種方法;有四塊紅牌,讓其插空,有c54種方法;共有方法 1+C; +Cy +C;+C; =55 種.說明:對(duì)于不相鄰問題,常用“插空法”(特殊元素后考慮)例3某儀表顯示屏上一排有 7個(gè)小孔,每
5、個(gè)小孔可顯示出 0或1,若每次顯示其中三個(gè)孔,但相鄰的兩 孔不能同時(shí)顯示,則這顯示屏可以顯示的不同信號(hào)的種數(shù)有 種.解:四個(gè)孔不亮,三個(gè)孔亮,相當(dāng)于三個(gè)亮著的孔在四個(gè)不亮的孔之間插空,故有c53 M 2 M 2 M 2 =80 種方法.三.部分不同元素定序與部分相同元素排列問題:部分不同元素在排列前后的順序固定不變(不一定相鄰)的排列問題,稱之為“定序排列”問題.解決這類問題的基本方法有三種(1) “消序法”(有些地方叫“整體法”),即若有m+n個(gè)元素排成一列,其中有 m個(gè)元素之間的排列順序不變,將這 m + n個(gè)元素任意排成一列,共有Am:種不同的排法,其中未定序的n個(gè)元素排在某一特定位置的
6、排列的個(gè)數(shù)有 Am種排法,但只有一個(gè)排列是我們所需要的排列,因而共有m:un包0種不同的排法.類似地還可推廣到一般情形,如有有 m+n+k個(gè)元素排成一列,其中有 m個(gè)元素之間的排列順序不變,且另外 k個(gè)元m,n k素之間的排列順序也不變,則共有牛擊中不同的算法.m Akmm k(2)逐一插空法:先將定序的元素進(jìn)行排列,再將其它元素逐一插入這組元素兩端及中間(3)優(yōu)序法:先將所有位置中按 “特殊元素”個(gè)數(shù)選出若干位置,并把這些特殊元素按規(guī)定順序排上去,再將普通元素在其余位置上全排列例4若5男5女排成一排,按下列要求各有多少種排法(1)男女相間;(2)女生按指定順序排列.解:(1)先將男生排好,有
7、2種排法;再將5名女生插在男生之間的 6個(gè)“空擋”(包括兩端)中,有2A5種排法.故本題的排法有 N =2A5 A5 =28800 (種);A10 .(2)方法 1 (消序法):N =Af = A50 =30240; A方法2 (逐一插空法):5個(gè)女生按序排列,有 1中方法,5個(gè)男生逐個(gè)才1空,有 6,7,8,9,10 種方法,共 有 6 M 7 M8 M 9父 10 = 30240 種方法.方法3 (優(yōu)序法):設(shè)想有10個(gè)位置,先將男生排在其中的任意5個(gè)位置上,有 A50種排法;余下的5個(gè)位置排女生,因?yàn)榕捻樞蛞呀?jīng)指定,所以她們只有一種排法故本題的結(jié)論為 N = A0父1 =30240
8、(種).例5今有2本相同的語(yǔ)文書,3本相同的數(shù)學(xué)書,4本相同的英語(yǔ)書排成一排,有多少種不同的排法?a9解:(消序法)有 2A3 4 =1260種.A2A3A4例6 一個(gè)樓梯共18個(gè)臺(tái)階,12步登完,可一步登一個(gè)臺(tái)階,也可一步登兩個(gè)臺(tái)階,一共有多少種不同的走法?解:根據(jù)題意,要想12步登完,只能6個(gè)一步登一個(gè)臺(tái)階,6個(gè)一步登二個(gè)臺(tái)階.因此,把問題轉(zhuǎn)化為“相 同元素”的排列問題.因此有一A4 =924 (種)A6A6點(diǎn)評(píng):對(duì)于部分不同元素定序排列以及相同元素的排列問題,可用優(yōu)序法【隨堂練習(xí)】1 .從5位同學(xué)中選派4位同學(xué)在星期五、星期六、星期日參加公益活動(dòng),每人一天,要求星期五有2人參加,星期六、
9、星期日各有1人參加,則不同的選派方法共有( B )A. 40 種B.60種C. 100 種D. 120 種2 .安排3名支教老師去6所學(xué)校任教,每校至多 2人,則不同的分配方案共有 210種.(用數(shù)字作答)3 .用數(shù)字0, 1, 2, 3, 4, 5組成沒有重復(fù)數(shù)字,且比20000大的五位偶數(shù)有(A.288 個(gè) B.240 個(gè) C.144 個(gè) D.1264 .如圖,用6種不同的顏色給圖中的 4個(gè)格子涂色,每個(gè)格子涂一種顏色,要求最多使用3種顏色且相鄰的兩個(gè)格子顏色不同,則不同的涂色方法共有390種(用數(shù)字作答)5 .某校開設(shè)9門課程供學(xué)生選修,其中 A,B,C三門由于上課時(shí)間相同,至多選一門,
10、學(xué)校規(guī)定每位同學(xué)選修4門,共有 75種不同選修方案.(用數(shù)值作答)6 .從班委會(huì)5名成員中選出3名,分別擔(dān)任班級(jí)學(xué)習(xí)委員、文娛委員與體育委員,其中甲、乙二人不能擔(dān)任文娛委員,則不同的選法共有36種.(用數(shù)字作答)【課后作業(yè)】1 .某校安排5個(gè)班到4個(gè)工廠進(jìn)行社會(huì)實(shí)踐,每個(gè)班去一個(gè)工廠,每個(gè)工廠至少安排一個(gè)班,不同的安排方法共有240種.(用數(shù)字作答)2 .將數(shù)字 1,2, 3, 4, 5, 6拼成一列,記第 i 個(gè)數(shù)為 a (i=1, 2,,6),若 , %#3, a5#5, a1 <a3 <% ,則不同的排列方法有 30 種(用數(shù)字作答)解:分兩步:(1)先排a1,
11、 a3, a5,當(dāng)a1 =2時(shí),有2種;當(dāng)a1 =3時(shí),有2種;當(dāng)& =4時(shí),有1種,共有5種;(2)再排a2,%,%,共有 A =6種,故不同的排列方法種數(shù)為 5X6=30,填30.3 .中韓兩支圍棋隊(duì)各由 8人組成,按事先排好的次序出場(chǎng)進(jìn)行圍棋擂臺(tái)賽,雙方先由 1號(hào)隊(duì)員比賽,負(fù)者被淘汰,勝者再與負(fù)方2號(hào)隊(duì)員比賽,直到有一方全部被淘汰為止,另一方獲勝,形成一個(gè)比賽過程.(1)已知中方動(dòng)用了 5名隊(duì)員,取得了勝利,問這樣的比賽過程有多少種?(2)求由中方第8位選手獲得最后勝利的概率 .解:(1)中方勝利時(shí),雙方共有 8 + 5 = 13名隊(duì)員參加了比賽,將他們按淘汰的順序從左向右排列,
12、則最右為中方5號(hào),右第二個(gè)為韓方 8號(hào),從右第三個(gè)至最左,共 11個(gè)位置上,有4個(gè)位置排中方隊(duì)員,其余排韓方隊(duì)員,每一種排法,對(duì)應(yīng)一種比賽結(jié)果,故共有C: =330種.(2)PC86 154 .若7位同學(xué)站成一排(1)甲、乙兩同學(xué)不能相鄰的排法共有多少種?(2)甲、乙和丙三個(gè)同學(xué)都不能相鄰的排法共有多少種?解:(1)解法一:(排除法)A; A6八;=3600;解法二:(插空法)先將其余五個(gè)同學(xué)排好有A5種方法,此時(shí)他們留下六個(gè)位置(就稱為“空”吧),再將甲、乙同學(xué)分別插入這六個(gè)位置(空)有A2種方法,所以一共有 A:A2 =3600種方法.(2)先將其余四個(gè)同學(xué)排好有A4種方法,此時(shí)他們留下五
13、個(gè)“空”,再將甲、乙和丙三個(gè)同學(xué)分別插入這五個(gè)“空”有 A;種方法,所以一共有 A4 A3 = 1440種.【課后記】四.錯(cuò)位排列問題n個(gè)不同元素排成一排,有 m個(gè)元素(mWn)不排在相應(yīng)位置的排列種數(shù)共有:An C1 An 4' !:;'C2An-2 -C3 An -3 . ( 1)mCmAn mAn CmAn 4 CmAn -2 CmAn -3( 1) CmAn 用.當(dāng)n = m時(shí),規(guī)定A0 =0! =1 ,這個(gè)公式亦成立.例7五封標(biāo)號(hào)為15的信放進(jìn)5個(gè)編號(hào)為15的信箋里面,若信的編號(hào)與信箋的編號(hào)都不相同,一共有多少種不同放法.解:這是著名的信封問題,很多著名數(shù)學(xué)家都研究過
14、.瑞士數(shù)學(xué)家歐拉按一般情況給出了一個(gè)遞推公式:用A、B、C表示寫著n位友人名字的信封,a、b、c表示n份相應(yīng)的寫好的信.把錯(cuò)裝的總數(shù)記為f(n).假設(shè)把a(bǔ)錯(cuò)裝進(jìn)B里了,包含著這個(gè)錯(cuò)誤的一切錯(cuò)裝法分兩類:(1) b錯(cuò)裝進(jìn)A里,這時(shí)每種錯(cuò)裝的其余部分都與a、b、A、B無關(guān),應(yīng)有f(n-2)種錯(cuò)裝法.(2) b錯(cuò)裝進(jìn)A、B之外的信封,這時(shí)的裝信工作實(shí)際是把(除a之外的)信紙b、c裝入(除B之外的)n_1個(gè)信封A、C,顯然這種錯(cuò)裝方法有f(n1)種.錯(cuò)裝的其余部分都與 a、b、A、B無關(guān),應(yīng)有f(n-2)種錯(cuò)裝法.總之在a錯(cuò)裝入B的錯(cuò)誤之下,共有錯(cuò)裝法f (n-1)+f(n-2)種.裝入D的n2種錯(cuò)誤
15、之下,同樣都有f (n1)十f(n2)種錯(cuò)裝法.因此 f(n) =(n -1)f (n 1) + f (n 2),顯然 f (1) = 0 , f (2) =1.由此可得f (5) -44.注意:用容斥原理亦可解決此題.111c 1W遍結(jié)論為專日排公式 1: f(n)=n!1 + + ,+(1).1! 2! 3!n!錯(cuò)排遞推公式 2:f(n)=(n-1)f (n-1)+ f(n-2)錯(cuò)排公式3: A ©An: CmAnnj -CmAnn - (-1)mC:An;m例8有5個(gè)人站成一排,其中 A不站第一位,B不站第二位,C不站第三位,D不站第四位,E不站第五位,共有多少種不同的站法.解
16、析:上面兩例實(shí)際上可以看成n個(gè)不同元素中有 m (mWn)錯(cuò)位排列的問題.而這個(gè)問題是其特殊情況,即全錯(cuò)位排列問題共有 A5 -C5A4 +CIA33 -C3A22 +C54A1 -C;A0=44種(注意 A0=0!=1)例9同室四人各寫一張賀年卡,先集中起來.然后每人從中拿一張別人送出的賀年卡.則四張賀年卡不同的分配方式有A.6 種B.9 種C.11 種D.23 種解析:由上面公式得:a4 c4A +c:8 -c43A1 +c4a0 =9種,選擇 b答案.因此可得到全錯(cuò)位排列的公式:n個(gè)不同元素排成一排,第一個(gè)元素不在第一位,第二個(gè)元素不在第二位,第n個(gè)元素不在第n位的排列數(shù)為:A -cnA
17、ni+cX -c3An + +(-i)nc:A這實(shí)際上是公式a -cmAni十cmwj2 此耳+ +(i)mcmAn比的特殊情況.這個(gè)公式很有用,只要有特殊元素不站特殊位置的問題,都可以用這個(gè)公式很快得到解決,希望這個(gè)公式對(duì)大家有所幫助五.圓桌排列從n個(gè)不同元素中不重復(fù)的取出 m (iMmWn)個(gè)元素排在一個(gè)圓周上,叫做這 n個(gè)不同元素的圓排列.如果一個(gè)m-圓排列旋轉(zhuǎn)可以得到另一個(gè) m-圓排列,則認(rèn)為這兩個(gè)圓排列是相同的.特別的,當(dāng) m = n時(shí),n個(gè)不同元素作成的圓排列總數(shù)為(n-1)!.證明:在圓周上任選一個(gè)位置排 2_,有口種排法,再選一個(gè)位置排 22有門-1種排法,最后一個(gè)位置排n!a
18、n有1種排法.而這n個(gè)人順時(shí)針(或逆時(shí)針)挪動(dòng) n次位置都是同一種排列.所以共有一=(n -1)!種排法. n例10有5對(duì)夫婦參加一場(chǎng)婚宴,他們被安排在一張10個(gè)座位的圓桌就餐,但是婚禮操辦者并不知道他們彼此之間的關(guān)系,只是隨機(jī)安排座位。問5對(duì)夫婦恰好都被安排在一起相鄰而坐的概率是多少?()4!種坐法,而夫婦間又可以換位置,所A.在1%o到5%o之間 B.在5%o到1%之間 C.超過1% D.不超過1%o解:5對(duì)夫婦相鄰而座,可以看做是五個(gè)大元素為桌而坐,所以有.4! 2 2 2 2 229459!n個(gè)人,需要確定最終的三個(gè)“先進(jìn)人物”人以共有 4. 2 2 2 2 2 0.002.故選:A.
19、例11博杰學(xué)習(xí)網(wǎng)競(jìng)賽小組“先進(jìn)人物評(píng)比”最終圈定了選.方法是:這n個(gè)人排成一行,從第一名開始,1至3循環(huán)報(bào)數(shù),凡報(bào)出 3的就退出,余下的向前靠攏,按此規(guī)律重復(fù)進(jìn)行.直到第p次報(bào)數(shù)后,只剩下 3個(gè)人為止.試問:這剩下的三個(gè)人,分別在隊(duì)伍最初的什么位置?解:設(shè)n個(gè)人的編號(hào)依次為 1,2,,n.最后剩下的三個(gè)人中,第三人的編號(hào)為bn.因bn未被淘汰,故不是3的倍數(shù).第一次報(bào)數(shù)后淘汰了 一個(gè)人,還剩n -個(gè)人.bn向前移動(dòng)了 bn-bk (k = n-"n)個(gè)人,前面 333淘汰了 bn =bn rn(rn=1,2 )個(gè)人.故bn=3bk一rn.其中當(dāng)bk為奇數(shù)時(shí),rn =1 ;否則,rn=
20、 2,每報(bào)一次321號(hào),人數(shù)減少-(除不盡時(shí)取整).計(jì)算bn逐步歸納為減小的數(shù)列,最終劃歸到小情況.例如n =1000時(shí),第3三個(gè)人的初始位置是 712.例12 將圓分成n ( n圭2)個(gè)扇形,現(xiàn)用 m ( m至2)種顏色給這些扇形染色,每個(gè)扇形恰染一種顏色 且要求相鄰的扇形不同色.問有多少種不同的染色方法?解:設(shè)染色方法數(shù)為 an.(1)求初始值.當(dāng)n=2時(shí),給§染色有m種方法,給 &染色有m-1種方法.所以 a2 =m(m -1);(2)求遞推關(guān)系.給§染色有m種方法,給 &染色有m-1種方法,給S染色有m-1種方法,給Sn染色有m-1種方法.共有m(m
21、-1)n種方法.這種情況可以分為兩類一類是Sn與S,不同色,此時(shí)的染色方法種數(shù)是an ;另一類是Sn與S同色,Sn與S可以合并為一個(gè)扇形,與S不同色,染色方法種數(shù)為 an.由加法原理,得到n 1an +an=m(m1)( n >2).(3)求an.構(gòu)造等比數(shù)列.結(jié)論:共有an =(m1)n+(1)n(m1)種染色方法.六.轉(zhuǎn)化命題對(duì)于一些較難的排列組合問題,通常采用轉(zhuǎn)化命題的方法來解決.比如圓內(nèi)弦的交點(diǎn)個(gè)數(shù)可轉(zhuǎn)化為圓內(nèi)接四邊形的個(gè)數(shù);異面直線的對(duì)數(shù)可轉(zhuǎn)化為3倍的四面體的個(gè)數(shù)等.例13圓周上共有15個(gè)不同的點(diǎn),過其中任意兩點(diǎn)連一弦,這些弦在圓內(nèi)的交點(diǎn)最多有多少個(gè)?分析:若兩弦有交點(diǎn),則兩弦
22、應(yīng)是圓內(nèi)接四邊形的對(duì)角線,即一個(gè)四邊形對(duì)應(yīng)一個(gè)交點(diǎn).所以共有C15 =1365個(gè)交點(diǎn).小結(jié):1 . “在”與“不在”可以相互轉(zhuǎn)化.解決某些元素在某些位置上用“定位法”,解決某些元素不在某些位置上一般用“間接法”或轉(zhuǎn)化為“在”的問題求解2 .排列組合應(yīng)用題極易出現(xiàn)“重”、“漏”現(xiàn)象,而“重”、“漏”錯(cuò)誤常發(fā)生在該不該分類、有無順序的問 題上.為了更好地防“重”堵“漏”,在做題時(shí)需認(rèn)真分析自己做題思路,也可改變解題角度,利用一題多解核 對(duì)答案.【作業(yè)】1 .今有8個(gè)人坐圓桌,有多少種坐法?2 .有5個(gè)男孩,3個(gè)女孩圍成一圓,其中 3個(gè)女孩不相鄰,有多少種站法?3 . 一圓型餐桌依次有 A、B、C、
23、D、E、F六個(gè)座位,現(xiàn)讓 3個(gè)大人和3個(gè)孩子入座進(jìn)餐,要求任何兩個(gè)小孩都不能坐在一起,則不同的作法總數(shù)為72 .七.用容斥原理解排列問題有些排列組合問題可轉(zhuǎn)化為求集合的元素的個(gè)數(shù)來求.充分應(yīng)用容斥原理:n(A IjB) =n(A) n(B) -n(ApB)n(A LB LC)=n(A) n(B) n(C) -n(ApB) -n(BDc)-n(ApB) n(AB! C).例14五人站成一排,其中甲不站第一位,乙不立第二位,共有多少種不同的站法解:這個(gè)問題在高中很多參考書上都有,有幾種解法,其中一解法是用排除法:先考慮5個(gè)有的全排列,544有A5種不同的排法,然后除去甲排第一(有 A種)與乙排第二
24、(也有 A種),但兩種又有重復(fù)部分,因此多減,必須加上多減部分,這樣得到共有:A -2A4 +a =78種.例15 有5個(gè)人站成一排,其中甲不站第一位,乙不站第二位,丙不站第三位,共有多少種不同的站法.仿上分析可得: A5 -3A4 +3A3 - A; =64種.八.均勻分組問題.般地:將mn個(gè)不同元素均勻分成n組(每組m個(gè)元素),共有Cm CmCmCmn Cmn -mCm種方法.例16 有6本不同的書,按下列要求各有多少種不同的選法:(1)分給甲、乙、丙三人,每人 2本;(2)分為三份,每份2本;(3)分為三份,一份 1本,一份2本,一份3本;(4)分給甲、乙、丙三人,一人 1本,一人2本,
25、一人3本;(5)分給甲、乙、丙三人,每人至少1本.解:(1)根據(jù)分步計(jì)數(shù)原理得到:C;C2C; =90種;(2)分給甲、乙、丙三人,每人兩本有Cf2C42C2種方法,這個(gè)過程可以分兩步完成:第一步分為三份,每份兩本,設(shè)有X種方法;第二步再將這三份分給甲、乙、丙三名同學(xué)有A;種方法.根據(jù)分步計(jì)數(shù)原理可得:c;c2c;= xC,所以 x = C62c干2 =15.A因此,分為三份,每份兩本一共有15種方法.(3)這是“不均勻分組”問題,一共有C6C;C; =60種方法.653(4)在(3)的基礎(chǔ)上再進(jìn)行全排列,所以一共有C6C;C;A; =360種方法.(5)可以分為三類情況:“2、2、2型”即(
26、1)中的分配情況,有 C2C42CI =90種方法;“1、2、3型”即(4)中的分配情況,有 C6C;C;A3 =360種方法;“1、1、4型”,有C:A; =90種方法;所以,一共有 90+360+90= 540種方法.點(diǎn)評(píng):本題第(3)種類型為部分均勻分組再分配,其分組總數(shù)為C&G1A2題型變換:8名球員住A、B、C三個(gè)房間,每個(gè)房間最多住 3人,有多少種住宿方法?解:A3.例17 若3名飛行員和6名特勤人員分別上 3架不同型號(hào)的直升飛機(jī)執(zhí)行任務(wù),每機(jī)一名飛行員和兩名特勤人員,有多少種分配方法?解:先分組,再分配,2 2 2 1 1 1 一 一C6C4 c2 C3C2c133A F
27、 A A3 或者 c62c:c2 Cc;c;.類題:20名同學(xué)分兩組,每組10人去某地社會(huì)實(shí)踐,其中 6名干部,每組3人,不同分法總數(shù)是多少? 37答案:C6與A2 .A2 A九.隔板法:將n個(gè)相同元素,分成k (n之k, n, k= N )組,可以看成是在 n個(gè)元素之間的n-1個(gè) 空隙間插入k -1塊隔板.共有C:種方法.例18 將六本相同的書全部發(fā)給甲、乙、丙三人 .(1)每人至少分到一本書,問有多少種不同的分法?(2)每人不一定都分到一本書,問有多少種不同的分法?解:(1)用“隔板法”處理,六本書之間有五個(gè)空,插入兩塊隔板,有C;種分法;用“隔板站位法”處理,六本書之間有五個(gè)空,需插入兩
28、塊隔板,但由于有人可能沒有書,所以兩塊隔板站著兩個(gè)位置,加上六本書,可以看著是6+2 =8本書,分成3分,所以有CjnC: =28種分法.點(diǎn)評(píng):類類題1求不定方程Xi +X2 +X3 =6的非負(fù)整數(shù)解的個(gè)數(shù)?題型變換一:四本不同的書,分給三個(gè)人,每人至少一本,全部分完,有幾種分法?解:先分組,再分配有 c:a3種.題型變換二:n本不同的書,分給 n-1個(gè)人,每人至少1本,全部分完,有幾種分法?解:先分組,再分配有 C12Al二種.題型變換三:n本相同的書,全部分給 m (m<n)個(gè)人.(1)每人至少分到一本書,問有多少種不同的分法?(2)每人不一定都分到一本書,問有多少種不同的分法?解:
29、(1)解法一(隔板站位法):每人先分一本書,還剩下n-m本書,加上 m-1塊隔板,可視為(n -m)+(m -1) = n -1本書,分給m個(gè)人,所以有Cm:種方法.解法二(隔板法):n本書之間有n-1個(gè)空,需插入 m-1塊隔板,所以有 Cmf種方法.(2)(隔板站位法):n本書之間,需插入 m-1塊隔板,但是,由于有人分不到書,所以 m-1塊隔板站 著m-1個(gè)位置,加上n本書,可視為n+m-1本書,用m-1塊隔板分成 m分,所以有Cnmm種方法(這也 是一個(gè)公式).【隨堂練習(xí)】1. (1)四個(gè)不同的小球放入四個(gè)不同的盒中,一共有多少種不同的放法?(2)四個(gè)不同的小球放入四個(gè)不同的盒中且恰有一
30、個(gè)空盒的放法有多少種?解:(1)根據(jù)分步計(jì)數(shù)原理:一共有 44 =256種方法;(2)(捆綁法)第一步:從四個(gè)不同的小球中任取兩個(gè)“捆綁”在一起看成一個(gè)元素有C42種方法;第二步:從四個(gè)不同的盒中任取三個(gè)將球放入有A:種方法,所以,一共有 C42 A43 = 144種方法.說明:先組合,再排列是解決問題的關(guān)鍵.本題亦可先將4個(gè)小球分成三組,每組分別有 1/1/ 2個(gè),共再放入四個(gè)盒子中的三個(gè),共有 C4C2C1 a3 =144種.A2思考:(1)四個(gè)相同的小球放入四個(gè)不同的盒子中,一共有多少種不同的放法?解:(隔板站位法)共C:+=C3=35.(2) 10個(gè)相同的小球放入編號(hào)為 1、2、3的盒
31、子中,球數(shù)不少于編號(hào)數(shù)的放法有多少種?解:按要求放6個(gè),其余4個(gè)按隔板站位法 有C:w =C: =15種方法.另解:(隔板法)設(shè)1, 2, 3號(hào)盒子所放的千數(shù)分別為 a, b, c.則有a + b + c = 10.設(shè)乂 = 2, y=b-1, z = c-2,則方程x + y+z = 7的正整數(shù)解的組數(shù),就是放球的方法數(shù).所以共有22C4 H2 =C6 =15種方法.注意:這種利用“先換元,再用隔板技巧”的方法對(duì)于求有限制條件的不定方程的非負(fù)整數(shù)解的問題很有效!【總結(jié)提煉】均勻分組(不計(jì)組的順序)問題不是簡(jiǎn)單的組合問題,如:將3個(gè)人分成3組,每組一個(gè)人,顯然只有1種分法,而不是=6種.cmc
32、mcm一般地,將 m n個(gè)不同元素均勻分成 n組,有(): 一m種分法;Am十.窮舉法:對(duì)于一些不能直接用兩個(gè)原理,且類別不多的問題,通常采用窮舉法.即列舉所有情況.例19將五個(gè)市級(jí)三好學(xué)生名額和八個(gè)區(qū)級(jí)優(yōu)秀學(xué)生干部名額全部分配到轄區(qū)的兩所中學(xué),每所學(xué)校至少有一個(gè)名額,有多少種不同的分配方案?解:分配情況用有序數(shù)組 (x, y)表示:(1,12), (2,11 ), (3,10), (4,9), (5,8), (6,7).然后兩校交換所以共有分配方案數(shù)為 2 M(2 + 3+4十5十6+6)=52種.例20 .十一.遞推法:對(duì)于一些較復(fù)雜的排列問題,可以建立排法之間的一個(gè)遞推關(guān)系,通過遞推關(guān)系
33、求出排法種數(shù)例19 一個(gè)樓梯共10個(gè)臺(tái)階,如果規(guī)定一步登一個(gè)臺(tái)階或登兩個(gè)臺(tái)階,一共有多少種不同的走法?解:設(shè)上n級(jí)臺(tái)階的走法為an種,易知a1 =1, a2 = 2 ,當(dāng)n至2時(shí),上n級(jí)臺(tái)階的走法可分兩類:第一類是最后一步跨一級(jí),有an q種走法,第二類是最后一步跨二級(jí),有ani種走法.由加法原理可知an=an4+an/,據(jù)此可得a10=89種不同的走法.例20 有五個(gè)人排成一列,現(xiàn)在要重新排列,要求都不能站在原來的位置,有幾種不同排法?.設(shè)滿足這解:我們考慮人數(shù)為 n的情況,即n個(gè)人排成一列,重新站隊(duì)時(shí),各人都不站在原來的位置上樣的站隊(duì)方式有an種,現(xiàn)在我們來通過合理分步,恰當(dāng)分類找出遞推關(guān)
34、系:第一步:第一個(gè)人不站在原來的第一個(gè)位置,有 n1種站法.第二步:假設(shè)第一個(gè)人站在第2個(gè)位置,則第二個(gè)人的站法又可以分為兩類:第一類,第二個(gè)人恰好站在第一個(gè)位置,則余下的n2個(gè)人有an/種站隊(duì)方式;第二類,第二個(gè)人不站在第一個(gè)位置,則就是第二個(gè)人不站在第一個(gè)位置,第三個(gè)人不站在第三個(gè)位置, 第四個(gè)人不站在第四個(gè)位置,第n個(gè)人不站在第n個(gè)位置,所以有an_1種站隊(duì)方式.由分步計(jì)數(shù)原理和分類計(jì)數(shù)原理,我們便得到了數(shù)列K的遞推關(guān)系式:an =(n 1)3,+an/),顯然,2=0, a2=1,,a5=44.故有 44種不同排法.注意:n個(gè)人排成一排后,解散后重新排隊(duì),自己不站原來的位置的排法種數(shù)可
35、由以下公式推導(dǎo)得到:(1) & =0, %=1, an=(n - 1)(an* an_2)( n - 3 );(2)an1= n!1 -1!11n 1(1)-. 2! 3!n! an =a -cnA+cnx-Cn3AnE+(-1)ncnx.例21在n=<m的網(wǎng)格中,從(0,0)點(diǎn)到(n, m)點(diǎn),只能沿網(wǎng)格的邊向 x軸正方向或y軸正方向前進(jìn),問共有多少種不同的前進(jìn)路線?解:對(duì)任意一個(gè)非 x軸、y軸上的點(diǎn)(x,y),可以從點(diǎn)(x,y1)走來,也可以從點(diǎn)(x 1,y)走來.因此,設(shè)(x, y)處的路線條數(shù)為f(x, y),則有遞推公式:f(x, y) - f(x, y -1) f (
36、x -1, y).下面的推理很重要:根據(jù)上述遞推公式,可得f (x, y) =cxx+y,即從x + y件物品中選出無順序的 x件(或(x y)!y件)的總方案數(shù).即f (x, y) = (紇.x!y!小結(jié):上述問題中把每個(gè)f(x,y)指標(biāo)在對(duì)應(yīng)的坐標(biāo)點(diǎn)處,再將坐標(biāo)系順時(shí)針旋轉(zhuǎn)135°,你發(fā)現(xiàn)了什么?這是楊輝三角,f (x, y) =Cx4y.而我們知道,C: = CL +C:”這就是通項(xiàng)公式的來源.另解:記網(wǎng)格橫向的x條線段從左至右依次為a1、a2、ax,網(wǎng)格縱向的y條線段從下至上依次為 b、b2、by.從(0,0)至U(x, y)的走法種數(shù),就是為、a?、ax及b、b2、by這x+y個(gè)元素的一個(gè)N y定序排列.于是有 m (或(x+y)!)種不同走法.Ax Ayx!y!例22某地決定在一個(gè)大型廣場(chǎng)建一個(gè)同心圓形花壇,花壇分為兩部分,中間小圓部分種植草坪
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 停業(yè)通知的司法實(shí)踐-洞察及研究
- 楷書硬筆、毛筆書法技法系統(tǒng)化教程
- 發(fā)酵技術(shù)的基礎(chǔ)原理與應(yīng)用分析
- 文化產(chǎn)業(yè)發(fā)展融資模式探究
- 自然辯證法考試重點(diǎn)與難點(diǎn)總結(jié)
- 多維度特征提取在電力系統(tǒng)擾動(dòng)識(shí)別中的應(yīng)用
- 內(nèi)部資金調(diào)劑管理辦法
- 生物炭與有機(jī)肥配施對(duì)土壤健康及設(shè)施栽培黃瓜生長(zhǎng)的影響機(jī)制研究
- 安全運(yùn)輸操作規(guī)程與案例分析
- PCR實(shí)驗(yàn)室管理與標(biāo)準(zhǔn)化操作流程
- GB/T 45698-2025物業(yè)服務(wù)客戶滿意度測(cè)評(píng)
- 2025年新高考1卷(新課標(biāo)Ⅰ卷)語(yǔ)文試卷(含答案)
- 本土品牌“品牌年輕化”策略研究
- 湖南省永州市寧遠(yuǎn)縣2025屆七年級(jí)數(shù)學(xué)第二學(xué)期期末達(dá)標(biāo)檢測(cè)試題含解析
- 創(chuàng)新人才小升初試題及答案
- 2025年行政管理期末試題及答案
- 胰島素筆的使用操作流程
- 九年級(jí)化學(xué)上冊(cè)(滬教版2024)新教材解讀課件大綱
- 江山南方水泥有限公司浙江省江山市大陳鄉(xiāng)烏龍村鐵錘山水泥用灰?guī)r礦建設(shè)項(xiàng)目環(huán)境影響報(bào)告表
- 小學(xué)語(yǔ)文主題教學(xué)論:理論重塑與創(chuàng)新實(shí)踐
- 工程框架協(xié)議合同協(xié)議
評(píng)論
0/150
提交評(píng)論