第三章排列與組合

1、第三章第三章排列與組合排列與組合3.1兩個基本的計數(shù)原理兩個基本的計數(shù)原理例3：有6個桔子和個桔子和9個蘋果，要求藍子中至少有一個水果，問可以裝配成多少種不同的水個蘋果，要求藍子中至少有一個水果，問可以裝配成多少種不同的水果藍？果藍？區(qū)分兩種不同的計數(shù)類型：區(qū)分兩種不同的計數(shù)類型：（1）對元素的有序擺放數(shù)或選擇數(shù)的計數(shù)。）對元素的有序擺放數(shù)或選擇數(shù)的計數(shù)。a)沒有重復的元素沒有重復的元素b)有重復的元素（無限重復或有限重復）有重復的元素

2、（無限重復或有限重復）（2）對元素的無序擺放數(shù)或選擇數(shù)的計數(shù)。）對元素的無序擺放數(shù)或選擇數(shù)的計數(shù)。a)沒有重復的元素沒有重復的元素b)有重復的元素（無限重復或有限重復）有重復的元素（無限重復或有限重復）定義：與順序有關的擺放或選擇稱定義：與順序有關的擺放或選擇稱排列。與順序無關的擺放或選擇稱排列。與順序無關的擺放或選擇稱組合。組合。3.2集合的排列集合的排列（一）線性排列（一）線性排列定義：定義：從n個元素中取出個元素中取出r個元素的有

3、序擺放，稱個元素的有序擺放，稱n元素集合的元素集合的r排列。排列。用P（nr）表示）表示n元素集合的全部元素集合的全部r排列數(shù)。排列數(shù)。定理定理3.2.1：對于整數(shù)對于整數(shù)n和rr?n有：有：P（nr）=n?(n1)?(n2)、、、?(nr1)=n!(nr)!其中：定義其中：定義n!=n?(n1)?(n2)、、、?2?1約定：（約定：（1）0！=1（2）當）當rn時，時，P（nr）=0例1：將數(shù)字將數(shù)字1，2，、、、，15放入一個放入一

4、個4?4的方陣中，問共有多少種擺放方法？若放入的方陣中，問共有多少種擺放方法？若放入6?6的方陣中，共有多少種擺放方法？的方陣中，共有多少種擺放方法？推論推論3.3.1：對于整數(shù)對于整數(shù)r，0?r?n，=????????rn????????rnn例1：平面上平面上25個點，假設不存在個點，假設不存在3點共線情況，問這些點可以組成多少條直線？多少個三點共線情況，問這些點可以組成多少條直線？多少個三角形？角形？例2：如果每個詞都包含如果每個

5、詞都包含3，4或5個元音，那么字母表中個元音，那么字母表中26個字母可以構(gòu)造多少個個字母可以構(gòu)造多少個8字母字母詞？（假設每個詞中的字母使用次數(shù)沒有限制）詞？（假設每個詞中的字母使用次數(shù)沒有限制）定理定理3.3.2：下述公式成立：下述公式成立：…=2n.????????0n????????1n????????nn例3：用不同計數(shù)法證明：用不同計數(shù)法證明：=n(n1)2????????rn34多重集的排列多重集的排列定理定理3.4.1：令

6、S是多重集，它有是多重集，它有k個不同的元素，每個元素都有無限重復次數(shù)，那么，個不同的元素，每個元素都有無限重復次數(shù)，那么，S的r排列個數(shù)為列個數(shù)為kr.例1：具有具有4位數(shù)字的三進制數(shù)的個數(shù)是多少？位數(shù)字的三進制數(shù)的個數(shù)是多少？定理定理3.4.2：令S是多重集，它有是多重集，它有k個不同的元素，每個元素的重復數(shù)分別為個不同的元素，每個元素的重復數(shù)分別為n1，n2，、、、，nk，那，那么，么，S的排列數(shù)的排列數(shù)=，其中，其中n=n1n2