1 第十章排列 組合和二項(xiàng)定理 10 1分類計(jì)數(shù)原理與分步計(jì)數(shù)原理 分類計(jì)數(shù) 分步計(jì)數(shù)原理的理解與應(yīng)用 2 做一件事情 完成它需要分成n個(gè)步驟 做第一步有m1種不同的方法 做第二步有m2種不同的方法 做第n步有mn種不同的方法 那么完成這件事有n m1 m2 mn種不同的方法 2 分步計(jì)數(shù)原理 做一件事情 完成它可以有n類辦法 在第一類辦法中有m1種不同的方法 在第二類辦法中有m2種不同的方法 在第n類辦法中有mn種不同的方法 那么完成這件事共有n m1 m2 mn種不同的方法 1 分類計(jì)數(shù)原理 復(fù)習(xí)引入 3 3 分類計(jì)數(shù)原理和分步計(jì)數(shù)原理的共同點(diǎn)是什么 不同點(diǎn)什么 答 共同點(diǎn)是 它們都是研究完成一件事情 共有多少種不同的方法 不同點(diǎn)是 它們研究完成一件事情的方式不同 分類計(jì)數(shù)原理是 分類完成 即任何一類辦法中的任何一個(gè)方法都能完成這件事 深化理解 分步計(jì)數(shù)原理是 分步完成 即這些方法需要分步 各個(gè)步驟順次相依 且每一步都完成了 才能完成這件事情 2020 3 2 4 4 何時(shí)用分類計(jì)數(shù)原理 分步計(jì)數(shù)原理呢 答 完成一件事情有n類方法 若每一類方法中的任何一種方法均能將這件事情從頭至尾完成 則計(jì)算完成這件事情的方法總數(shù)用分類計(jì)數(shù)原理 深化理解 完成一件事情有n個(gè)步驟 若每一步的任何一種方法只能完成這件事的一部分 并且必須且只需完成互相獨(dú)立的這n步后 才能完成這件事 則計(jì)算完成這件事的方法總數(shù)用分步計(jì)數(shù)原理 2020 3 2 5 例1 在所有的兩位數(shù)中 個(gè)位數(shù)字大于十位數(shù)字的兩位數(shù)共有多少個(gè) 解法1 按個(gè)位數(shù)字是2 3 4 5 6 7 8 9分成8類 在每一類中滿足條件的兩位數(shù)分別是1個(gè) 2個(gè) 3個(gè) 4個(gè) 5個(gè) 6個(gè) 7個(gè) 8個(gè) 則根據(jù)分類計(jì)數(shù)原理共有1 2 3 4 5 6 7 8 36 個(gè) 解法2 按十位數(shù)字是1 2 3 4 5 6 7 8分成8類 在每一類中滿足條件的兩位數(shù)分別是8個(gè) 7個(gè) 6個(gè) 5個(gè) 4個(gè) 3個(gè) 2個(gè) 1個(gè) 則根據(jù)分類計(jì)數(shù)原理共有8 7 6 5 4 3 2 1 36 個(gè) 例題講解 2020 3 2 6 例2 一個(gè)三位密碼鎖 各位上數(shù)字由0 1 2 3 4 5 6 7 8 9十個(gè)數(shù)字組成 可以設(shè)置多少種三位數(shù)的密碼 各位上的數(shù)字允許重復(fù) 首位數(shù)字不為0的密碼數(shù)是多少 首位數(shù)字是0的密碼數(shù)又是多少 第一步 m1 10 第二步 m2 10 第三步 m2 10 解 按密碼位數(shù) 從左到右依次設(shè)置第一位 第二位 第三位 需分為三步完成 例題講解 根據(jù)分步計(jì)數(shù)原理 共可以設(shè)置n 10 10 10 1000個(gè)三位數(shù)的密碼 2020 3 2 7 例2 一個(gè)三位密碼鎖 各位上數(shù)字由0 1 2 3 4 5 6 7 8 9十個(gè)數(shù)字組成 可以設(shè)置多少種三位數(shù)的密碼 各位上的數(shù)字允許重復(fù) 首位數(shù)字不為0的密碼數(shù)是多少 首位數(shù)字是0的密碼數(shù)又是多少 第一步 m1 9 第二步 m2 10 第三步 m3 10 解 按密碼位數(shù) 從左到右依次設(shè)置第一位 第二位 第三位 需分為三步完成 例題講解 根據(jù)分步計(jì)數(shù)原理 共可以設(shè)置n 9 10 10 900個(gè)首位數(shù)字不為0的三位數(shù)的密碼 2020 3 2 8 例2 一個(gè)三位密碼鎖 各位上數(shù)字由0 1 2 3 4 5 6 7 8 9十個(gè)數(shù)字組成 可以設(shè)置多少種三位數(shù)的密碼 各位上的數(shù)字允許重復(fù) 首位數(shù)字不為0的密碼數(shù)是多少 首位數(shù)字是0的密碼數(shù)又是多少 第一步 m1 1 第二步 m2 10 第三步 m3 10 解 按密碼位數(shù) 從左到右依次設(shè)置第一位 第二位 第三位 需分為三步完成 例題講解 根據(jù)分步計(jì)數(shù)原理 共可以設(shè)置n 1 10 10 100個(gè)首位數(shù)字是0的三位數(shù)的密碼 2020 3 2 9 若設(shè)置四位 五位 六位 十位等密碼 密碼數(shù)分別有多少種 答 它們的密碼種數(shù)依次是104 105 106 個(gè) 由此可以看出 首位數(shù)字不為0的密碼數(shù)與首位數(shù)字是0的密碼數(shù)之和等于密碼總數(shù) 綜上 可以設(shè)置各位上的數(shù)字允許重復(fù)三位數(shù)的密碼103 1000個(gè) 首位數(shù)字不為0的密碼數(shù)是9 102 900個(gè) 首位數(shù)字是0的密碼數(shù)是1 102 100個(gè) 例題變式推廣 2020 3 2 10 例3 要從甲 乙 丙3名工人中選出2名分別上日班和晚班 有多少種不同的選法 解 從3名工人中選1名上日班和1名上晚班 可以看成是經(jīng)過先選1名上日班 再選1名上晚班這兩個(gè)步驟完成 上日班的工人選定后 上晚班的工人有2種選法 n 3 2 6 答 有6種不同的選法 先選1名上日班 共有3種選法 根據(jù)分步計(jì)數(shù)原理 所求的不同的選法數(shù)是 例題講解 2020 3 2 11 例4 要將4封不同的信投遞到3個(gè)不同的信箱 有多少種不同的投送方法 解 要將4封不同的信投遞到3個(gè)不同的信箱 可以按照如下的四個(gè)步驟完成 n 3 3 3 3 34 將a信投入到一個(gè)信箱中 有3種投法 根據(jù)分步計(jì)數(shù)原理 所求的不同的投信方法數(shù)是 例題講解 將b信投入到一個(gè)信箱中 有3種投法 將c信投入到一個(gè)信箱中 有3種投法 將d信投入到一個(gè)信箱中 有3種投法 投信模型 2020 3 2 12 1 如圖 要給地圖a b c d四個(gè)區(qū)域分別涂上3種不同顏色中的某一種 允許同一種顏色使用多次 但相鄰區(qū)域必須涂不同的顏色 不同的涂色方案有多少種 染色問題 課堂練習(xí) 2020 3 2 13 1 如圖 要給地圖a b c d四個(gè)區(qū)域分別涂上3種不同顏色中的某一種 允許同一種顏色使用多次 但相鄰區(qū)域必須涂不同的顏色 不同的涂色方案有多少種 染色問題 課堂練習(xí) 2020 3 2 14 第一步涂a m1 3種 第二步涂b m2 2種 第三步涂c m3 1種 第四步涂d m4 1種 1 如圖 要給地圖a b c d四個(gè)區(qū)域分別涂上3種不同顏色中的某一種 允許同一種顏色使用多次 但相鄰區(qū)域必須涂不同的顏色 不同的涂色方案有多少種 染色問題 課堂練習(xí) 所以根據(jù)分步計(jì)數(shù)原理 得到不同的涂色方案種數(shù)共有n 3 2 1 1 6種 解 按地圖a b c d四個(gè)區(qū)域依次分四步完成 注 a b c d四個(gè)區(qū)域涂法順序的設(shè)計(jì) 15 2 如圖 一螞蟻沿著長(zhǎng)方體的棱 從它的一個(gè)頂點(diǎn)爬到相對(duì)的另一個(gè)頂點(diǎn)的最近路線共有多少條 a1 b1 c1 d1 a c d b 解 如圖 從總體上看 如螞蟻從頂點(diǎn)a爬到頂點(diǎn)c1需要三步走 從局部上看每步有不同的路徑選擇 所以 第一步 m1 3種走法 第二步 m2 2種走法 第三步 m3 1種走法 所以 根據(jù)分步計(jì)數(shù)原理 從頂點(diǎn)a到頂點(diǎn)c1最近路線共有 課堂練習(xí) n 3 2 1 6條 16 關(guān)于分步計(jì)數(shù)原理的幾點(diǎn)注記 各個(gè)步驟之間相互依存 且方法總數(shù)是各個(gè)步