2014 年 國慶 高中數學競賽班型知識點梳理 （第 三 次） 資料 說明 本 導學用于學員在實際授課之前，了解授課方向及重難點。同時還附上部分知識點的詳細解讀。 本 班型導學共由 4 份 書面資料構成。 清北學堂集中培訓課程知識點梳 理 （ 2014 年 國慶 集中培訓課程使用） QBXT/JY/ZSD2014/9-1-3 2014-9-20 發布 清北學堂教學研究部 清北學堂學科郵箱 自主招生郵箱 數學競賽郵箱 物理競賽郵箱 化學競賽郵箱 生物競賽郵箱 理科精英郵箱 清北學堂官方博客 /tsba 清北學堂微信訂閱號 學習資料最新資訊 清北學堂集中培訓課程知識點梳理 北京清北學堂教育科技有限公司 第 2 頁 2014 年 國慶 高中數學競賽班型知識點梳理 (組合數學部分 ) 目錄 一、 課程重點及難點概述 . 3 二、 清北導學 . 4 排列與組合 . 4 知識點 . 4 組合恒等式 . 6 重點及難點 . 6 知識點 . 6 思考題 . 7 常用排列組合思想 . 8 知識點 . 8 抽屜原理、容斥原理、極端原理 . 9 知識點 . 9 思考題 . 10 清北學堂集中培訓課程知識點梳理 北京清北學堂教育科技有限公司 第 3 頁 一、 課程重點及難點概述 本次 課程 的重點 為組合計數 。 應用基本組合計數原理和組合恒等式來解決實際問題是本次課程的難點。 清北學堂集中培訓課程知識點梳理 北京清北學堂教育科技有限公司 第 4 頁 二、 清北導學 排列與組合 知識點 1. 排列 ： 從 n 個不同元素中，任取 ),( 均為自然數與 nmnmm 個元素按照一定的順序排成一列，叫做從 n 個不同的元素中取出 m 個元素的一個排列。從 n 個不同的元素中取出 )( nmm 個元素的所有排列的個數，叫做從 n 個不同元素中取出 m 個元素的排列數，用符號 mnA 表示。 123)2()1(! nnnn )!( !)1()2)(1( mn nmnnnnA mn 2. 組合： 從 n 個不同元素中，任取 ),( 均為自然數與 nmnmm 個元素并成一組，叫做從 n 個不同的元素中取出 m 個元素的一個組合。從 n 個不同的元素中取出)( nmm 個元素的所有組合的個數，叫做從 n 個不同元素中取出 m 個元素的組合數，用符號 mnC 表示。!)!( !123)2()1( )1()2)(1( mmn nmmm mnnnnC mn 3. 二項式定理 ： ni iininn baCba 0)( 常用形式 nnnnnnn CCCC 1102 nnnnnnnn CCCC )1()1(0 1110 4. 分類 計數 原理 ： 完成一件事，有幾種方式，第一種方式有 m 種方法，第二種方式有n 種方法，最后一種方式有 r 種方法 .不管采取哪一種方法都能完成這件事，則完成這件事的方法總數為 rnm 。應用分類計數原理的關鍵在于分劃。 清北學堂集中培訓課程知識點梳理 北京清北學堂教育科技有限公司 第 5 頁 5. 分步計數原理 ：完成一件事，有幾個步驟，第一步有 m 種方法，第二步有 n 種方法，最后一步有 r 種方法，要完成這件事，必須通過每一步，則完成這件事的方法總數為 rnm 。應用分步計數原理的關鍵在于分解。 清北學堂集中培訓課程知識點梳理 北京清北學堂教育科技有限公司 第 6 頁 組合恒等式 重點及難點 掌握基本的排列組合恒等式、學會組合表達式的化簡是本次課程的重點。綜合應用組合恒等式和排列組合數學意義來證明某些組合恒等式是本次課程的難點。 知識點 1. 常用 排列組合公式 ： 0)1(212)1()1()1()!(!)1()1()!(!321021011111nnnnnnnnnnnnnmrmnmnmnrnrnrnrnrnrnrnnrnmnmnCCCCCCCCCCCCCCrnCCCCCCmmmnnnmnmnCmnnnmnnA 2. 母函數法 把離散數列和冪級數一一對應起來，把離散數列間的相互結合關系對應成冪級數間的運算關系，最后由冪級數來確定離散數列的構造。 簡要地說，母函數方法是將一個有限或無限的數列 , 210 kk aaaaa 和如下形式的多項式 kk xaxaxaaxf 2210)( 聯系起來，構成對應關系 ka )(xf 。 這個 )(xf 就稱為 ka 的母函數或生產函數 。 意思是這個數列 ka 是由多項式 )(xf產生的 。 清北學堂集中培訓課程知識點梳理 北京清北學堂教育科技有限公司 第 7 頁 例如：組合數列 nnnn CCC , 10 的母函數是 nx)1( 因為由二項式定理可得 nnnnnn xCxCCx 10)1( nx)1( 是最常見的母函數 . 設 ka 與 kb 是兩個 給定 的數列，為了確定它們之間的某種關系，可分別寫出二者所對應的母函數，再研究這兩個母函數間的某種關系從而確定兩個數列之間的關系，這便是母函數方法解題的基本思想 。母函數的思想還在很多其他領域有所應用，如概率論中常用的矩母函數法。 思考題 一、求證： nknk n nnnC0122 !2 )!2(2 二、求證： nkk knknk nC0 1222 12)1( 三、設 1n ，且兩個自然數的集合滿足 , 2121 nn bbbaaa ，其合集滿足 1|1| njibbnjiaa jiji （集合相等包括元素重數相等）。求證：存在自然數 h ，使得 hn 2 （提示：利用母函數法） 四、求證： !1 )!2()()()( 22120 nn nCCC nnnn 清北學堂集中培訓課程知識點梳理 北京清北學堂教育科技有限公司 第 8 頁 常用排列組合思想 知識點 （ 1）排除：對有限條件的問題，先從總體考慮，再把不符合條件的所有情況排除，這是解決排列組合題的常用策略 。 （ 2）分類與分步 :有些問題的處理可分成若干類，用加法原理，要注意每兩類的交集為空集，所有各類的并集是全集；有些問題的處理分成 幾個步驟，把各個步驟的方法數相乘，即得總的方法數，這是乘法原理。 （ 3）對 稱思想：兩類情形出現的機會均等，可用總數取半得每種情形的方法數。 （ 4）插空：某些元素不能相鄰或某些元素在特殊位置時可采用插空法。 即先安排好沒有限制條件的元素， 然后將有限制條件的元素按要求插入到排好的元素之間。 （ 5）捆綁：把相鄰的若干特殊元素 “ 捆綁 ” 為一個 “ 大元素 ” ，然后與其它 “ 普通元素 ” 全排列，然后再 “ 松綁 ” ，將這些特殊元素在這些位置上全 排列。 （ 6）隔板模型： 類似求解不定方程 ),( NMwzyxMwzyx 的非負整數解的個數的問題，可以采用隔板法。將 M 個相同的小球與 3 個隔板進行排列，第一個隔板之前的小球數為 x 值，第一個隔板與第二個隔板之前的小球數為 y 值，第二個隔板與第三個隔板之前的小球數為 z 值，第三個隔板之前的小球數為 w 值。 清北學堂集中培訓課程知識點梳理 北京清北學堂教育科技有限公司 第 9 頁 抽屜原理、容斥原理、極端原理 知識點 1. 抽屜原理 表述一： 把多于 n 個的物體放到 n 個 抽屜 里，則至少有一個抽屜里的東西不少于兩件 。 表述二： 把多于 )0( kkmn 個的物體放到 n 個抽屜里，則至少有一個抽屜里有不少于 1m 個 的物體。 表述三： 把無窮多件物體放入 n 個抽屜，則至少有一個抽屜里有無窮個物體。 抽屜原理為解決一些存在性問題提供了一種巧妙的方法。 2. 容斥原理 簡單集合運算后集合元素的計數比較簡單，但對于復雜結構集合，情況遠非如此。 )()()()( BAC a r dBC a r dAC a r dBAC a r d )()()()()()()()(CBAC a r dCBC a r dCAC a r dBAC a r dCC a r dBC a r dAC a r dCBAC a r d )()1()()()()(1111inikjinkjini jijiiiniAC a r dAAAC a r dAAC a r dAC a r dAC a r d 容斥的思想除了在計數方面有所應用外，在求解傳遞函數的 Mason 公式中也有所體現。 3. 極端原理 1. 最小數原理、最大數原理 命題一有限個實數中，必有一個最小數（也必有一個最大數）。 命題二任意有限個兩兩不同的實數可以從小到大排列順序。上述兩個命題對無窮多個實數可能不成立，例如對于集合 2-n|n N，其中就沒有最小的數。對于自然數集，有最小數原理：若 M 是自然數集 N 的任一非空子集（有限或無限均可），則 M 中必有最小的數。 2 最短長度原理 、 最短長度原理 清北學堂集中培訓課程知識點梳理 北京清北學堂教育科技有限公司 第 10 頁 1：任意給定兩點，所有連接這兩點的線中，以直線段的長度為最短。 2：在連接一已知點和已知直線或已知平面的點的所有線