第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種不同的方法，那么，完成這件事共有Nk1k2kn種不同的方法,10.1分類計數(shù)原理與分步計數(shù)原理,分步計數(shù)原理（乘法原理）：,10.1分類計數(shù)原理與分步計數(shù)原理,如果一件事需要分成n個步驟完成，做第1步有k1種不同的方法，做第2步有k2種不同的方法做第n步有kn種不同的方法，那么，完成這件事共有Nk1k2kn種不同的方法,例1書架上層放有5本不同的語文書，中層放有6本不同的數(shù)學書，下層放有4本不同的外語書求解下列問題：（1）從中任取1本，有多少種不同的取法？（2）從中任取語文、數(shù)學和外語書各1本，有多少種不同的取法？,10.1分類計數(shù)原理與分步計數(shù)原理,解（1）從書架上任取1本書，有3類辦法：第1類辦法是從上層取語文書，可以從5本書中任取1本，有5種方法；第2類辦法是從中層取數(shù)學書，可以從6本書中任取1本，有6種方法；第3類辦法是從下層取外語書，可以從4本書中任取1本，有4種方法根據(jù)分類計數(shù)原理，得到不同的取法的種數(shù)是N56415,10.1分類計數(shù)原理與分步計數(shù)原理,（1）從中任取1本，有多少種不同的取法？,解從書架上任取語文、數(shù)學和外語書各1本，可以分成3個步驟完成：第1步是從上層取1本語文書，有5種方法；第2步是從中層取1本數(shù)學書，有6種方法；第3步是從下層取1本外語書，有4種方法根據(jù)分步計數(shù)原理，得到不同的取法的種數(shù)是N564120,10.1分類計數(shù)原理與分步計數(shù)原理,（2）從中任取語文、數(shù)學和外語書各1本，有多少種不同的取法？,例2甲、乙兩個同學做“石頭、剪刀、布”的游戲，出手一次，共有多少種不同的情況發(fā)生？如果三個人做此游戲，出手一次，又有多少種不同的情況發(fā)生？,10.1分類計數(shù)原理與分步計數(shù)原理,分析雖然甲、乙兩個同學是同時出手，但不妨看作甲先出手、乙后出手，這是兩個接連進行的過程,解甲出手有3種選擇，乙出手也有3種選擇，所以兩人做游戲出手一次，共有339種不同的情況類似地，如果甲、乙、丙三人做此游戲，出手一次，共有33327種不同的情況,1在一次讀書活動中，指定的書目包括：不同的文學書3本，歷史書5本，科技書7本，某同學任意選讀其中1本，共有多少種不同的選法？2某班三好學生中男生有5人，女生有4人，從中任選1人去領獎，共有多少種不同的選法？從中任選男女各1人去參加座談會，共有多少種不同的選法？,10.1分類計數(shù)原理與分步計數(shù)原理,3某手機生產(chǎn)廠為某種機芯設計了3種不同的外形，每種外形又有5種不同色彩的外殼及6種不同的屏幕背景燈光，問這種手機共可設計多少種不同的款式？4由1，3，5，7這4個數(shù)字組成的沒有重復數(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，mN*，mn），按照一定的順序排成一列，稱為從n個不同的元素中取出m個元素的一個排列,1判斷下列問題是不是求排列數(shù)的問題，如果是，請寫出相應的排列數(shù)的符號：（1）把5只蘋果平均分給5個同學，計算共有多少種分配方法（2）從5只蘋果中取出2只給某位同學，計算共有多少種選擇方法（3）10個人互寫一封信，計算共寫多少封信（4）10個人互通一次電話，計算共通幾次電話,10.2排列,2按要求寫出排列，并寫出相應的排列數(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ù)為nm1，共有m個因數(shù)相乘,根據(jù)分步計數(shù)原理，全部填滿m個空位共有n（n1）（n2）（nm1）,10.2排列,例1計算下列各題：,10.2排列,解（2）,本題也可以直接用計算器計算計算的按鍵過程為：計算的按鍵過程為：,10.2排列,解由于即解得所以,例2若，求,10.2排列,例3有5本不同的書，發(fā)給3名同學，每人1本，共有多少種不同的分法？,例4某信號兵用紅、黃、藍3面旗掛在豎直的旗桿上表示信號，每次可以任掛1面、2面或3面，并且不同的懸掛順序表示不同的信號，一共可以表示多少種信號？,10.2排列,10.2排列,例5用09這10個數(shù)字可以組成多少個沒有重復數(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以外的19這9個數(shù)字中任選一個，有P種選法第2步，再排十位和個位上的數(shù)字，它可以從余下的9個數(shù)字（包括0）中任選兩個，有P種選法根據(jù)分步計數(shù)原理，所求的三位數(shù)的個數(shù)是,19,29,解法3從09這10個數(shù)字中任選3個數(shù)字的排列數(shù)為P，其中0排在百位上的排列數(shù)為P，因此所求的三位數(shù)的個數(shù)是,310,29,10.2排列,10.2排列,例6以所有26個英文字符組成一個26位的密碼，規(guī)定在一個密碼中不出現(xiàn)相同的字符，那么可以組成多少種不同的密碼？以單臺計算機去解密，若計算機解密的速度是每秒鐘檢查107個不同的密碼，那么最多需要多少時間才能解密？（結果以年為單位，保留6位有效數(shù)字）,解26個英文字符是26個不同的元素，一個密碼是26個元素的一個全排列，總計密碼數(shù)是26的全排列數(shù)所以組成的密碼數(shù)是26！,計算機解密耗時最長的情況是直到最后一個才檢查到設置的密碼，此時耗時T為所以，用題中所給計算機解密，最多需要時間約為12788.3億年,10.2排列,計算：2若，求n。3由0，1，2，3，5，7，9這7個數(shù)字能組成多少個沒有重復數(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組合,例把下列的問題歸結為組合問題，并寫出相應的組合數(shù)的符號：,10.3組合,1把下列的問題歸結為組合問題，并寫出相應的組合數(shù)的符號：（1）6位朋友互相握手道別，共握手多少次？（2）6道習題任意選做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ù)公式，當mn時有,10.3組合,例1計算：,解,10.3組合,解因為12個點中任何3個點都不在同一直線上，所以任取3個點都可以畫出一個三角形因此所求三角形的個數(shù)，就是從12個不同的元素中取出3個元素的組合數(shù)，即所以一共可畫220個三角形,例2平面內有12個點，任何3個點不在同一直線上，以每3個點為頂點畫一個三角形，一共可畫多少個三角形？,10.3組合,例3一次小型聚會，每一個與會者都和其他與會者握一次手，共有15次握手，問有多少人參加這次聚會？,例4100件商品中含有3件次品，其余都是正品，從中任取3件：（1）3件都是正品，有多少種不同的取法？（2）3件中恰有1件次品，有多少種不同的取法？（3）3件中最多有1件次品，有多少種不同的取法？（4）3件中至少有1件次品，有多少種不同的取法？,解（）因為3件都是正品，所以應從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ù)的性質,在一般情況下：從n個元素中選出m個元素的組合數(shù)，與從n個元素中選出nm個元素的組合數(shù)是相等的由此，得到組合數(shù)的一種重要性質：,10.3組合,解,例1計算,10.3組合,例2已知，求n,解為使，可令n=3n2，即n=1又因為，所以成立又因此也可令10n=3n2，即n=3因此，n=1或n=3,10.3組合,