兩個基本計數(shù)原理.ppt

1.1 兩個基本計數(shù)原理,高二 數(shù)學備課組,世界杯足球賽共有32個隊參賽它們先分成8個小組進行循環(huán)賽，決出16強，這16個隊按確定的程序進行淘汰賽后，最后決出冠亞軍，此外還決出了第三、第四名問一共安排了多少場比賽？前4名有多少不同的結果？,實際問題,要回答這個問題，就要用到排列、組合的知識在運用排列、組合方法時，經(jīng)常要用到分類計數(shù)原理與分步計數(shù)原理,問題1：從甲地到乙地，有3條公路，2條鐵路，某人要從甲地到乙地，共有多少種不同的走法？,問題2：從甲地到乙地，有3條道路，從乙地到丙地有2條道路，那么從甲地經(jīng)乙地到丙地共有多少種不同的走法 ？,你能說出這兩個問 題有什么區(qū)別嗎?,問題1：從甲地到乙地，有3條公路，2條鐵路，某人要從甲地到乙地，共有多少種不同的走法？,因為每一種走法都能完成從甲地到乙地這件事，有3條公路，2條鐵路，所以共有： 325 （種）,甲地,乙地,一、分類計數(shù)原理,完成一件事，有n類辦法. 在第1類辦法中有m1種不同的方法， 在第2類方法中有m2種不同的方法， 在第n類方法中有mn種不同的方法， 則完成這件事共有 :,2）首先要根據(jù)具體的問題確定一個分類標準，在分類標準下進行分類，然后對每類方法計數(shù).,1）各類辦法之間相互獨立,都能獨立的完成這件事，要計算方法種數(shù),只需將各類方法數(shù)相加,因此分類計數(shù)原理又稱加法原理,說明,N= m1+m2+ + mn 種不同的方法,問題2：從甲地到乙地，有3條道路，從乙地到丙地有2條道路，那么從甲地經(jīng)乙地到丙地共有多少種不同的走法 ？,這個問題與前一個問題不同在這個問題中，必須經(jīng)過先從甲地到乙地、再從乙地到丙地兩個步驟，才能從甲地到丙地,因為從甲地到乙地有3種走法，從乙地到丙地有2種走法，所以從甲地到丙地，共有不同的走法： 326 （種）,甲地,乙地,丙地,二、分步計數(shù)原理,完成一件事，需要分成n個步驟。 做第1步有m1種不同的方法， 做第2步有m2種不同的方法， ， 做第n步有mn種不同的方法， 則完成這件事共有,2）首先要根據(jù)具體問題的特點確定一個分步的標準，然后對每步方法計數(shù).,1）各個步驟相互依存,只有各個步驟都完成了,這件事才算完成,將各個步驟的方法數(shù)相乘得到完成這件事的方法總數(shù),又稱乘法原理,說明,N= m1m2 mn種不同的方法,例1.,書架第1層放有4本不同的計算機書,第2層放有3本不同的文藝書,第3層放有2本不同的體育書.,(1)從書架中取1本書,有多少種不同取法?,有3類方法,根據(jù)分類加法計數(shù)原理,N=4+3+2=9,(2)從書架第1,2,3層各取1本書,有多少種不同取法?,分3步完成,根據(jù)分步乘法計數(shù)原理,N=432=24,解題關鍵：從總體上看做這件事情是“分類完成”,還是“分步完成”.再根據(jù)其對應的計數(shù)原理計算.,學案P46-1,練習,要從甲、乙、丙3幅不同的畫中選出2幅,分別掛在左、右兩邊墻上的指定位置,問共有多少種不同的掛法?,分兩步完成,左邊,右邊,甲,乙,丙,3,2,第一步,第二步,學案P46-2,A,B,該電路從A到B共有多少條不同的線路可通電？,分類完成,分步完成,解: 從總體上看由A到B的通電線路可分二類, 第一類, m1 = 4 條 第二類, m3 = 22 = 4, 條 所以, 根據(jù)加法原理, 從A到B共有 N = 4 + 4 = 8 條不同的線路可通電.,點評:,乘法原理看成“串聯(lián)電路”,加法原理看成“并聯(lián)電路”;,如圖,從甲地到乙地有2條路可通,從乙地到丙地有3條路可通;從甲地到丁地有4條路可通, 從丁地到丙地有2條路可通。從甲地到丙地共有多少種不同的走法？,練習,學案P47-s4,解:從總體上看,由甲到丙有兩類不同的走法, 第一類, 由甲經(jīng)乙去丙,又需分兩步, 所以 m1 = 23 = 6 種不同的走法; 第二類, 由甲經(jīng)丁去丙,也需分兩步, 所以 m2 = 42 = 8 種不同的走法; 所以從甲地到丙地共有 N = 6 + 8 = 14 種不同的走法。,問題3：加法原理和乘法原理的共同點是什么？不同點什么？,問題4：何時用加法原理、乘法原理呢?,加法原理,完成一件事情有n類方法,若每一類方法中的任何一種方法均能將這件事情從頭至尾完成.,乘法原理,完成一件事情有n個步驟,若每一步的任何一種方法只能完成這件事的一部分,并且必須且只需完成互相獨立的這n步后,才能完成這件事.,分類要做到“不重不漏”,分步要做到“步驟完整”,練習：,三個比賽項目，六人報名參加。 ）每人參加一項有多少種不同的方法？ ）每項人，且每人至多參加一項，有多少種不同的方法？ ）每項人，每人參加的項數(shù)不限，有多少種不同的方法？,例1 用0,1,2,3,4,5這六個數(shù)字, (1)可以組成多少個各位數(shù)字不允許重復的三位的奇數(shù)? (2)可以組成多少個各位數(shù)字不重復的小于1000的自然數(shù)? (3)可以組成多少個大于3000,小于5421且各位數(shù)字不允許重復的四位數(shù)?,一、排數(shù)字問題,二、映射個數(shù)問題:,例2 設A=a,b,c,d,e,f,B=x,y,z,從A到B共有多少種不同的映射?,三、染色問題:,例3 有n種不同顏色為下列兩塊廣告牌著色,要求在四個區(qū)域中相鄰(有公共邊界)區(qū)域中不用同一種顏色. (1)若n=6,為(1)著色時共有多少種方法? (2)若為(2)著色時共有120種不同方法,求n (1) (2),、如圖,要給地圖A、B、C、D四個區(qū)域分別涂上3種不同顏色中的某一種,允許同一種顏色使用多次,但相鄰區(qū)域必須涂不同的顏色,不同的涂色方案有多少種？,解: 按地圖A、B、C、D四個區(qū)域依次分四步完成, 第一步, m1 = 3 種, 第二步, m2 = 2 種, 第三步, m3 = 1 種, 第四步, m4 = 1 種, 所以根據(jù)乘法原理, 得到不同的涂色方案種數(shù)共有 N = 3 2 11 = 6 種。,、如圖,要給地圖A、B、C、D四個區(qū)域分別涂上3種不同顏色中的某一種,允許同一種顏色使用多次,但相鄰區(qū)域必須涂不同的顏色,不同的涂色方案有多少種？,若用2色、4色、5色等,結果又怎樣呢？,答:它們的涂色方案種數(shù)分別是 0、 4322 = 48、 5433 = 180種等。,思考：,分析：如圖，A、B、C三個區(qū)域兩兩相鄰， A與D不相鄰，因此A、B、C三個區(qū)域的顏色兩兩不同，A、D兩個區(qū)域可以同色，也可以不同色，但D與B、C不同色。由此可見我們需根據(jù)A與D同色與不同色分成兩大類。,解：先分成兩類：第一類，D與A不同色，可分成四步完成。 第一步涂A有5種方法，第二步涂B有4種方法；第三步涂C 有3種方法；第四步涂D有2種方法。根據(jù)分步計數(shù)原理， 共有5432120種方法。,根據(jù)分類計數(shù)原理，共有120+60180種方法。,第二類，A、D同色，分三步完成，第一步涂A和D有5種方法，第二步涂B有4種方法；第三步涂C有3種方法。根據(jù)分步計數(shù)原理，共有54360種方法。,5、將種作物種植在如圖所示的塊試驗田里，每塊種植一種作物且相鄰的試驗田不能種植同一種作物，不同的種植方法共有 種（以數(shù)字作答）,42,4、如圖，是5個相同的正方形，用紅、黃、藍、白、黑5種顏色涂這些正方形，使每個正方形涂一種顏色，且相鄰的正方形涂不同的顏色。如果顏色可反復使用，那么共有多少種涂色方法？,四、子集問題,規(guī)律：n元集合 的不同子集有個 。,例：集合A=a,b,c,d,e,它的子集個數(shù)為 ，真子集個數(shù)為 ，非空子集個數(shù)為 ，非空真子集個數(shù)為 。,五、綜合問題:,例4 若直線方程ax+by=0中的a,b可以從0,1,2,3,4這五個數(shù)字中任取兩個不同的數(shù)字,則方程所表示的不同的直線共有多少條?,例5、75600有多少個正約數(shù)?有多少個奇約數(shù)?,解:由于 75600=2433527,75600的每個約數(shù)都可以寫成 的形式,其中 , , ,于是,要確定75600的一個約數(shù),可分四步完成,即i,j,k,l分別在各自的范圍內任取一個值,這樣i有5種取法,j有4種取法,k有3種取法,l有2種取法,根據(jù)分步計數(shù)原理得約數(shù)的個數(shù)為5432=120個.,一個三位密碼鎖,各位上數(shù)字由0,1,2,3,4,5, 6,7,8,9十個數(shù)字組成,可以設置多少種三位數(shù)的密碼(各位上的數(shù)字允許重復)?首位數(shù)字不為0的密碼數(shù)是多少?首位數(shù)字是0的密碼數(shù)又是多少?,分析: 按密碼位數(shù),從左到右 依次設置第一位、第二位、第三 位, 需分為三步完成; 第一步, m1 = 10; 第二步, m2 = 10; 第三步, m3 = 10. 根據(jù)乘法原理, 共可以設置 N = 101010 = 103 種三位數(shù)的密碼。,練習,首位數(shù)字不為0的密碼數(shù)?首位數(shù)字是0的密碼數(shù)?,一個三位密碼鎖,各位上數(shù)字由0,1,2,3,4,5, 6,7,8,9十個數(shù)字組成,可以設置多少種三位數(shù)的密碼(各位上的數(shù)字允許重復)?首位數(shù)字不為0的密碼數(shù)是多少?首位數(shù)字是0的密碼數(shù)又是多少?,分析: 按密碼位數(shù),從左到右 依次設置第一位、第二位、第三 位, 需分為三步完成; 第一步, m1 = 10; 第二步, m2 = 10; 第三步, m3 = 10. 根據(jù)乘法原理, 共可以設置 N = 101010 = 103 種三位數(shù)的密碼。,練習,變式訓練：各位上的數(shù)字不允許重復又怎樣?,答:首位數(shù)字不為0的密碼數(shù)是 N =91010 = 9102 種, 首位數(shù)字是0的密碼數(shù)是 N = 11010 = 102 種。 由此可以看出, 首位數(shù)字不為0的密碼數(shù)與首位數(shù)字是0的密碼數(shù)之和等于密碼總數(shù)。,問: 若設置四位、五位、六位、十位等密碼,密碼數(shù)分別有多少種？,答:它們的密碼種數(shù)依次是 104 , 105, 106, 種。,1、分類加法計數(shù)原理：完成一件事，有n類辦法，在第1類辦法中有m1種不同的方法,在第2類辦法中有m2種不同的方法在第n類辦法中有mn種不同的方法.那么 完成這件事共有 種不同的方法.,2、分步乘法計數(shù)原理：完成一件事，需要分成n個步驟，做第1步有m1種不同的方法,做第2步有m2種不同的方法，做第n步有mn種不同的方法.那么完成這件事共有 種不同的方法.,回答的都是有關做一件事的不同