《排列、組合與二項式定理.ppt》由會員分享，可在線閱讀，更多相關(guān)《排列、組合與二項式定理.ppt（55頁珍藏版）》請在裝配圖網(wǎng)上搜索。

第20章排列與組合,10.1分類計數(shù)原理與分步計數(shù)原理,問題1某人從甲地到乙地，可以乘汽車、輪船或火車，一天中汽車有3班，輪船有2班，火車有1班．一天中乘坐這些交通工具從甲地到乙地共有多少種不同的走法？,實例考察,問題2某人從甲地出發(fā)，經(jīng)過乙地到達丙地．從甲地到乙地有A，B，C共3條路可走；從乙地到丙地有a，b共2條路可走．那么，從甲地經(jīng)過乙地到丙地共有多少種不同的走法？,10.1分類計數(shù)原理與分步計數(shù)原理,分類計數(shù)原理（加法原理）：,如果完成一件事有n類辦法，在第1類辦法中有k1種不同的方法，在第2類辦法中有k2種不同的方法……在第n類辦法中有kn種不同的方法，那么，完成這件事共有N＝k1＋k2＋…＋kn種不同的方法．,10.1分類計數(shù)原理與分步計數(shù)原理,分步計數(shù)原理（乘法原理）：,10.1分類計數(shù)原理與分步計數(shù)原理,如果一件事需要分成n個步驟完成，做第1步有k1種不同的方法，做第2步有k2種不同的方法……做第n步有kn種不同的方法，那么，完成這件事共有N＝k1k2…kn種不同的方法．,例1書架上層放有5本不同的語文書，中層放有6本不同的數(shù)學(xué)書，下層放有4本不同的外語書．求解下列問題：（1）從中任取1本，有多少種不同的取法？（2）從中任取語文、數(shù)學(xué)和外語書各1本，有多少種不同的取法？,10.1分類計數(shù)原理與分步計數(shù)原理,解（1）從書架上任取1本書，有3類辦法：第1類辦法是從上層取語文書，可以從5本書中任取1本，有5種方法；第2類辦法是從中層取數(shù)學(xué)書，可以從6本書中任取1本，有6種方法；第3類辦法是從下層取外語書，可以從4本書中任取1本，有4種方法．根據(jù)分類計數(shù)原理，得到不同的取法的種數(shù)是N＝5＋6＋4＝15,10.1分類計數(shù)原理與分步計數(shù)原理,（1）從中任取1本，有多少種不同的取法？,解從書架上任取語文、數(shù)學(xué)和外語書各1本，可以分成3個步驟完成：第1步是從上層取1本語文書，有5種方法；第2步是從中層取1本數(shù)學(xué)書，有6種方法；第3步是從下層取1本外語書，有4種方法．根據(jù)分步計數(shù)原理，得到不同的取法的種數(shù)是N＝564＝120,10.1分類計數(shù)原理與分步計數(shù)原理,（2）從中任取語文、數(shù)學(xué)和外語書各1本，有多少種不同的取法？,例2甲、乙兩個同學(xué)做“石頭、剪刀、布”的游戲，出手一次，共有多少種不同的情況發(fā)生？如果三個人做此游戲，出手一次，又有多少種不同的情況發(fā)生？,10.1分類計數(shù)原理與分步計數(shù)原理,分析雖然甲、乙兩個同學(xué)是同時出手，但不妨看作甲先出手、乙后出手，這是兩個接連進行的過程．,解甲出手有3種選擇，乙出手也有3種選擇，所以兩人做游戲出手一次，共有33＝9種不同的情況．類似地，如果甲、乙、丙三人做此游戲，出手一次，共有333＝27種不同的情況．,1．在一次讀書活動中，指定的書目包括：不同的文學(xué)書3本，歷史書5本，科技書7本，某同學(xué)任意選讀其中1本，共有多少種不同的選法？2．某班三好學(xué)生中男生有5人，女生有4人，從中任選1人去領(lǐng)獎，共有多少種不同的選法？從中任選男女各1人去參加座談會，共有多少種不同的選法？,10.1分類計數(shù)原理與分步計數(shù)原理,3．某手機生產(chǎn)廠為某種機芯設(shè)計了3種不同的外形，每種外形又有5種不同色彩的外殼及6種不同的屏幕背景燈光，問這種手機共可設(shè)計多少種不同的款式？4．由1，3，5，7這4個數(shù)字組成的沒有重復(fù)數(shù)字的兩位數(shù)共有多少個？,10.1分類計數(shù)原理與分步計數(shù)原理,10.2排列,要從甲、乙、丙3名工人中選取2名，分別安排上日班和晚班，找出所有的選擇方法，將下表補充完整．,實例考察,10.2排列,有分別編號的4個小球和3個盒子，要選取其中的3個小球分別放入盒子中，每個盒子只能放一個球，下表已給出兩種放置方法，請你補充列出其余所有方法．,一、排列與排列數(shù)的概念,10.2排列,10.2排列,10.2排列,一般地，從n個不同的元素中任取m個元素（n，m∈N*，m≤n），按照一定的順序排成一列，稱為從n個不同的元素中取出m個元素的一個排列．,1．判斷下列問題是不是求排列數(shù)的問題，如果是，請寫出相應(yīng)的排列數(shù)的符號：（1）把5只蘋果平均分給5個同學(xué)，計算共有多少種分配方法．（2）從5只蘋果中取出2只給某位同學(xué)，計算共有多少種選擇方法．（3）10個人互寫一封信，計算共寫多少封信．（4）10個人互通一次電話，計算共通幾次電話．,10.2排列,2．按要求寫出排列，并寫出相應(yīng)的排列數(shù)的符號：（1）3個元素a，b，c全部取出的所有排列．（2）從5個元素a，b，c，d，e中任取2個元素的所有排列．,10.2排列,10.2排列,二、排列數(shù)公式,10.2排列,由此可得排列數(shù)公式：,10.2排列,排列數(shù)公式的特點是：等號右邊第1個因數(shù)是n，后面的每個因數(shù)都比它前面一個因數(shù)少1，最后一個因數(shù)為n－m＋1，共有m個因數(shù)相乘．,根據(jù)分步計數(shù)原理，全部填滿m個空位共有n（n－1）（n－2）…（n－m＋1）,10.2排列,例1計算下列各題：,10.2排列,解（2）,本題也可以直接用計算器計算．計算的按鍵過程為：計算的按鍵過程為：,10.2排列,解由于即解得所以,例2若，求,10.2排列,例3有5本不同的書，發(fā)給3名同學(xué)，每人1本，共有多少種不同的分法？,例4某信號兵用紅、黃、藍3面旗掛在豎直的旗桿上表示信號，每次可以任掛1面、2面或3面，并且不同的懸掛順序表示不同的信號，一共可以表示多少種信號？,10.2排列,10.2排列,例5用0～9這10個數(shù)字可以組成多少個沒有重復(fù)數(shù)字的三位數(shù)？,解法1符合條件的三位數(shù)可以分為3類：第1類：每位數(shù)字都不是0的三位數(shù)，有個.第2類：個位數(shù)字是0的三位數(shù)，有個.第3類：十位數(shù)字是0的三位數(shù)，有個.根據(jù)分類計數(shù)原理，符合條件的三位數(shù)的個數(shù)是,10.2排列,解法2因為百位上的數(shù)字不能是0，所以可分兩個步驟來完成：第1步，先排百位上的數(shù)字，它只能從除0以外的1～9這9個數(shù)字中任選一個，有P種選法．第2步，再排十位和個位上的數(shù)字，它可以從余下的9個數(shù)字（包括0）中任選兩個，有P種選法．根據(jù)分步計數(shù)原理，所求的三位數(shù)的個數(shù)是,19,29,解法3從0～9這10個數(shù)字中任選3個數(shù)字的排列數(shù)為P，其中0排在百位上的排列數(shù)為P，因此所求的三位數(shù)的個數(shù)是,310,29,10.2排列,10.2排列,例6以所有26個英文字符組成一個26位的密碼，規(guī)定在一個密碼中不出現(xiàn)相同的字符，那么可以組成多少種不同的密碼？以單臺計算機去解密，若計算機解密的速度是每秒鐘檢查107個不同的密碼，那么最多需要多少時間才能解密？（結(jié)果以年為單位，保留6位有效數(shù)字）,解26個英文字符是26個不同的元素，一個密碼是26個元素的一個全排列，總計密碼數(shù)是26的全排列數(shù)．所以組成的密碼數(shù)是26?。?計算機解密耗時最長的情況是直到最后一個才檢查到設(shè)置的密碼，此時耗時T為所以，用題中所給計算機解密，最多需要時間約為12788.3億年．,10.2排列,,１．計算：2．若，求n。3．由0，1，2，3，5，7，9這7個數(shù)字能組成多少個沒有重復(fù)數(shù)字的三位數(shù)？4．（1）7人排隊，甲必須站在正中間有多少種排法？（2）7人排隊，甲，乙必須站頭尾有多少種排法,10.2排列,10.3組合,在一個4人（甲、乙、丙、?。﹨⒓拥男⌒凸ぷ鲿h上，任何一位與會者都要同其他與會者每人握手一次．下表已給出兩次握手的雙方名單，請補充列出其他各次握手的雙方名單．,實例考察,10.3組合,列出各次握手的雙方名單就是要從4個人中選出兩人，且不計兩人間的順序，并將各種選法羅列出來．,要從甲、乙、丙3名工人中選取2名，共同值晚班，有多少種選擇方法？請逐一列出．,10.3組合,一、組合與組合數(shù)的概念,（1）在人數(shù)為60人的班級中，選出5人參加專業(yè)知識競賽，有多少種選法？（2）由20人組成的足球隊中，除守門員外，還需選10人作為首發(fā)陣容，可組成多少種不同的首發(fā)陣容？又要在50名拉拉隊員中挑選20人前往助陣，有多少種挑選方案？,10.3組合,例把下列的問題歸結(jié)為組合問題，并寫出相應(yīng)的組合數(shù)的符號：,10.3組合,1．把下列的問題歸結(jié)為組合問題，并寫出相應(yīng)的組合數(shù)的符號：（1）6位朋友互相握手道別，共握手多少次？（2）6道習(xí)題任意選做4道題，有多少種不同的選法？（3）正16邊形有多少條對角線？,10.3組合,2．按要求寫出下列組合：（1）從5個元素a，b，c，d，e中任取2個元素的所有組合．（2）從4個元素a，b，c，d中任取3個元素的所有組合．,10.3組合,10.3組合,二、組合數(shù)公式,34,從４個不同元素中?。硞€元素的排列數(shù)Ｐ：,10.3組合,根據(jù)分步計數(shù)原理，得,因此,由此得到組合數(shù)公式：,10.3組合,10.3組合,因為所以組合數(shù)公式還可寫成,根據(jù)組合數(shù)公式，當(dāng)m＝n時有,10.3組合,例1計算：,解,10.3組合,解因為12個點中任何3個點都不在同一直線上，所以任取3個點都可以畫出一個三角形．因此所求三角形的個數(shù)，就是從12個不同的元素中取出3個元素的組合數(shù)，即所以一共可畫220個三角形．,例2平面內(nèi)有12個點，任何3個點不在同一直線上，以每3個點為頂點畫一個三角形，一共可畫多少個三角形？,10.3組合,例3一次小型聚會，每一個與會者都和其他與會者握一次手，共有15次握手，問有多少人參加這次聚會？,例4100件商品中含有3件次品，其余都是正品，從中任取3件：（1）3件都是正品，有多少種不同的取法？（2）3件中恰有1件次品，有多少種不同的取法？（3）3件中最多有1件次品，有多少種不同的取法？（4）3件中至少有1件次品，有多少種不同的取法？,解（１）因為3件都是正品，所以應(yīng)從97件正品中取，所有不同取法的種數(shù)是,10.3組合,10.3組合,（2）3件中恰有1件次品，有多少種不同的取法？,10.3組合,（3）3件中最多有1件次品，有多少種不同的取法？,解3件中至少有1件次品的取法，包括1件是次品，2件是次品和3件是次品，因此3件中至少有1件次品的取法的種數(shù)是,10.3組合,（4）3件中至少有1件次品，有多少種不同的取法？,10.3組合,10.3組合,三、組合數(shù)的性質(zhì),在一般情況下：從n個元素中選出m個元素的組合數(shù)，與從n個元素中選出n－m個元素的組合數(shù)是相等的．由此，得到組合數(shù)的一種重要性質(zhì)：,10.3組合,解,例1計算,10.3組合,例2已知，求n．,解為使，可令n=3n－2，即n=1又因為，所以成立又因此也可令10－n=3n－2，即n=3因此，n=1或n=3,10.3組合,