奧數(shù)-排列組合講義-第二講

排列與組合經(jīng)典精講1.排列的定義:從n個不同元素中,任取m個元素,按照一定的順序排成一列,叫做從n個不同元素中取出m個元素的一個排列.2.組合的定義:從n個不同元素中,任取m個元素,并成一組,叫做從n個不同元素中取出m個元素的一個組合.3.排列數(shù)公式:組合數(shù)公式:5.組合數(shù)的兩個性質(zhì)規(guī)定：排列與組合的區(qū)別與聯(lián)系:與順序有關的為排列問題,與順序無關的為組合問題.從分別寫有1、3、5、7、9的五張卡片中任取兩張，作成一道兩個一位數(shù)的乘法題，問：①有多少個不同的乘積？②有多少個不同的乘法算式？解：①要考慮有多少個不同乘積.由于只要從5張卡片中取兩張，就可以得到一個乘積，因為乘法的交換率，有多少個乘積只與所取的卡片有關，而與卡片取出的順序無關，所以這是一個組合問題.由組合數(shù)公式得到，共有個不同的乘積.②要考慮有多少個不同的乘法算式，它不僅與兩張卡片上的數(shù)字有關，而且與取到兩張卡片的順序有關，所以這是一個排列問題.由排列數(shù)公式，共有P25＝5×4＝20種不同的乘法算式.點評：看準是排列還是組合，剩下的就是簡單計算了。如下圖，問：①下左圖中，共有多少條線段？②下右圖中，共有多少個角？解：①在線段AB上共有7個點（包括端點A、B）.注意到，只要在這七個點中選出兩個點，就有一條以這兩個點為端點的線段，而與選這兩個端點的順序無關，所以，這是一個組合問題由組合數(shù)公式知，共有條不同的線段；②從O點出發(fā)的射線一共有11條，它們是OA，OP1，OP2，OP3，…，OP9，OB.注意到每兩條射線可以形成一個角，所以，只要看從11條射線中取兩條射線有多少種取法，就有多少個角.顯然，是組合問題，共有C211種不同的取法，所以，可組成C211個角.由組合數(shù)公式知，共有點評：在幾何計數(shù)當中也用到了很多排列組合的方法。此題可拓展常用的數(shù)線段，數(shù)三角形，數(shù)正方形、數(shù)長方形的公式和方法國家舉行足球賽，共15個隊參加.比賽時，先分成兩個組，第一組8個隊，第二組7個隊.各組都進行單循環(huán)賽（即每個隊要同本組的其他各隊比賽一場）.然后再由各組的前兩名共4個隊進行單循環(huán)賽，決出冠亞軍.問：①共需比賽多少場？②如果實行主客場制（即A、B兩個隊比賽時，既要在A隊所在的城市比賽一場，也要在B隊所在的城市比賽一場），共需比賽多少場？解：①實行單循環(huán)賽，比賽的所有場次包括三類：第一組中比賽的場次，第二組中比賽的場次，決賽時比賽的場次.總的場次計算要用加法原理。第一組中8個隊，每兩隊比賽一場，8個隊里邊選2兩個隊，是組合問題，所以共比賽C28場；第二組中7個隊，每兩隊比賽一場，所以共比賽C27場；決賽中4個隊，每兩隊比賽一場，所以共比賽C24場.實行單循環(huán)賽共比賽②由于是實行主客場制，每兩個隊之間要比賽兩場，比賽場次是①中的2倍.另外，還可以用排列的知識來解決.由于主客場制不僅與參賽的隊有關，而且與比賽所在的城市（即與順序）有關.所以，第一組共比賽P28場，第二組共比賽P27場，決賽時共比賽P24場.實行主客場制，共需比賽2×（C28＋C27＋C24）＝110（場）.或解為：P28＋P27＋P24＝8×7＋7×6＋4×3＝56＋42＋12＝110（場）.某班要在42名同學中選出3名同學去參加夏令營，問共有多少種選法？如果在42人中選3人站成一排，有多少種站法？提示1：首先根據(jù)不同情況分清楚看是用排列還是組合，然后再根據(jù)排列組合公式進行求解。提示2。要在42人中選3人去參加夏令營，那么，所有的選法只與選出的同學有關，而與三名同學被選出的順序無關.所以，共有C343種不同的選法.要在42人中選出3人站成一排，那么，所有的站法不僅與選出的同學有關，而且與三名同學被選出的順序有關.所以，共有P342種不同的站法.提示3。由組合數(shù)公式，共有種不同的選法由排列數(shù)公式，共有P342＝42×41×40＝68880種不同的站法.從8人的數(shù)學興趣小組中選2個（1）分別擔任正副組長，有多少種不同的選法？（2）共同參加一次數(shù)學競賽，有多少種不同的選法？提示1：：注意分清排列問題和組合問題提示2：（1）選出正副組長，有正副之分，也就是從8人中選2人后，要進一步確認正副組長，因此是個排列問題（2）題選人參加數(shù)學競賽沒有順序，因此是個組合問題。提示3：（1）利用排列公式，共有=8×7=56種選法。（2）利用組合公式，共有==28種選法。在一個圓周上有10個點，以這些點為端點或頂點，可以畫出多少不同的：直線段三角形（3）四邊形？提示1：首先觀察是組合問題還是排列問題，那就要看你取的點是否與順序有關？提示2：很明顯，你要畫的三個圖形都與取出點的順序無關，所以三個問題都應該是組合問題。由于10個點都在圓周上，因此任意三點都不共線，故只要在10個點中任取2點，就可畫出一條線段；在10個點中任取3個點，就可畫出一個三角形；在10個點中任取4個點就可畫出一個四邊形。提示3：由組合數(shù)公式：（1），可畫出45條線段；（2），可畫120個三角形；（3），畫210個四邊形。七個人排成一排照相，其中甲、乙、丙三人必須排在一起，有多少種不同的排法？提示1：首先看是排列還是組合？這道題明顯是排列問題，然后你再看所要排列的各個元素之間的關系，利用排列公式就可以了。提示2：甲乙丙三人必須排在一起，可以用分類的方法，考慮三人在七個位置中的不同情況，如：甲乙丙此時甲乙丙占了頭三個位置，然后再排其他四個人，最后再考慮甲乙丙三人的順序，這種方法比較復雜，我們可以換一種方法來考慮這個問題，由于甲乙丙要拍在一起，因此我們可以先將這三個人看作一個元素，將這個元素與其他四個元素進行排序，最后將這三個元素排序，用這種方法大大簡化了思維過程。第一步：甲、乙、丙看作一個元素與其他四個元素排列，即五個元素進行排序：；第二步：甲乙丙三個元素排序：提示3：不同的排法數(shù)有：×=5×4×3×2×1×3×2×1=720.（1）把八本書排在上下兩格書架上，每格四本，求有多少種不同的排法？（2）把八本書放在書架上，上格一本，中格三本，下格四本，求有多少種排法？提示1：書放在上層和下層是否相同？弄清楚是排列還是組合？提示2：很明顯，書放在上層和下層不相同，應該用乘法原理，但每層書的擺放要用排列原理，（1）八本書中先選四本排在第一格，有種排法，再將剩下4本書排在第二格，有種排法（2）八本書選一本放在上格有種排法，再從剩下的7本中選三本放中格，有種排法，最后四本書放下格，有種方法提示3：根據(jù)乘法原理：（1）不同的排法數(shù)是×=8×7×6×5×4×3×2×1=40320種（2）不同的排法是××=8×7×6×5×4×3×2×1=40320種。注意：從上兩小題發(fā)現(xiàn)，無論放幾層，分幾本放，結果都是一樣的，都是40320，若分成4層呢？是不是還是40320？學校乒乓球隊有10名男生，8名女生，現(xiàn)要選8人參加區(qū)里比賽，在下列的條件下，分別有多少種排法？（1）恰有3名女生入選；（2）至少有2名女生入選；（3）最多有3名女生入選；（4）某2名女生，某2名男生必須入選。提示1：此題是個典型的組合問題，元素之間沒有順序，第二三小題中涉及至少至多的問題，一般可分類來解決，而至少有2名女生入選的情況有：2名，3名，4名，5名……8名女生入選，情況較多，因此考慮從全部選法中除去沒有女生的選法和恰有1名女生的選法，這種方法稱為間接法。提示2：（1）先選3名女生，，再從10名男生中選5人：（2）從全部選法中除去沒有女生的選法和恰有1名女生的選法全部選法數(shù)恰有1名女生入選的選法：×沒有女生入選的選法：分四類，第一類沒有女生入選，;第二類，恰有一女生入選，；×第三類，恰有二女生入選；第四類，恰有三名女生入選；（4）某2名女生，某2名男生必須入選，說明有4人已選定，只須從剩下的14人中再選4人提示3：（1）恰有3名女生入選共有：×=14112種選法（2）至少有2名女生入選的方法：-×-=42753種（3）最多有三名女生入選的選法數(shù)：+×++=45+960+5880+14112=20997從剩下的14人中再選4人，共有選法=1001種。某運輸公司有7個車隊，每個車隊的車均多于4輛，現(xiàn)從這個車隊中抽調(diào)出10輛車，并且每個車隊至少抽調(diào)一輛，那么共有多少種不同的抽調(diào)方法？解：在每個車隊抽調(diào)一輛車的基礎上，還須抽調(diào)的3輛車可分成三類：從一個車隊中抽調(diào)，有＝7種；從兩個車隊中抽調(diào)，一個車隊抽1輛，另一個車隊抽兩輛，有＝42種；從三個車隊中抽調(diào)，每個車隊抽調(diào)一輛，有＝35輛.由分類計數(shù)原理知，共有7＋42＋35＝84種抽調(diào)方法.本題可用檔板法來解決：由于每個車隊的車均多于4輛，只需將10個份額分成7份.具體來講，相當于將10個相同的小球，放在7個不同的盒子中，且每個盒子均不空.可將10個小球排成一排，在相互之間的九個空檔中插入6個檔板，即可將小球分成7份，因而有＝84種抽調(diào)方法.補充題目1．某一天的課程表要排入語文、數(shù)學、英語、物理、體育、音樂6節(jié)課，如果第一節(jié)不排體育，最后一節(jié)不排數(shù)學，一共有多少種不同的排法？2.在7名運動員中選出4人組成接力隊，參加4×100米接力賽，那么甲、乙兩人都不跑中間兩棒的安排方法有多少種？3．有5雙不同型號的皮鞋，從中任取4只有多少種不同的取法？所取的4只中沒有2只是同型號的取法有多少種？所取的4只中有一雙是同型號的取法有多少種？4.4名男生5名女生，一共9名實習生分配到高一的四個班級擔任見習班主任，每班至少有男、女實習生各1名的不同分配方案共有多少種？5.有6本不同的書，分給甲、乙、丙三人.（1）甲、乙、丙三人各得2本，有多少種分法？（2）一人得1本，一人得2本，一人得3本，有多少種分法？（3）甲得1本，乙得2本，丙得3本，有多少種分法？（4）平均分成三堆，每堆2本，有多少種分法？家庭作業(yè)（1）有4名學生報名參加數(shù)學、物理、化學競賽，每人限報一科，有多少種不同的報名方法？（2）有4名學生參加爭奪數(shù)學、物理、化學競賽冠軍，有多少種不同的結果？（3）將3封不同的信投入4個不同的郵筒，則有多少種不同投法？【解析】：（1）（2）（3）把6名實習生分配到7個車間實習共有多少種不同方法？【解析】：完成此事共分6步，第一步；將第一名實習生分配到車間有7種不同方案，第二步：將第二名實習生分配到車間也有7種不同方案，依次類推，由分步計數(shù)原理知共有種不同方案.8名同學爭奪3項冠軍，獲得冠軍的可能性有（）A、B、C、D、【解析】：冠軍不能重復，但同一個學生可獲得多項冠軍，把8名學生看作8家“店”，3項冠軍看作3個“客”，他們都可能住進任意一家“店”，每個“客”有8種可能，因此共有種不同的結果。所以選A有甲乙丙三項任務，甲需2人承擔，乙丙各需一人承擔，從1