2014年國(guó)慶高中數(shù)學(xué)競(jìng)賽班型知識(shí)點(diǎn)梳理3

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