清北學(xué)堂 2014年寒假數(shù)學(xué)聯(lián)賽提高班導(dǎo)學(xué)3-數(shù)學(xué)組合部分

2014 年寒假 數(shù)學(xué)聯(lián)賽 提高 班 導(dǎo)學(xué) （第 三 次） 資料 說明 本 導(dǎo)學(xué)用于學(xué)員在實(shí)際授課 之 前 ，了解授課方向及重難點(diǎn)。 同時(shí) 還 附上部分知識(shí)點(diǎn) 的詳細(xì)解讀。每個(gè)班型導(dǎo)學(xué)共由 4 次書面資料構(gòu)成。此次發(fā)布的為第 三 次導(dǎo)學(xué)，后面的第 四次導(dǎo)學(xué) ， 將于 2013 年 12 月 25 日發(fā)布。在 2013 年 12 月 20 日，公司 還 會(huì)發(fā)布 相應(yīng)班型的詳細(xì)授課大綱，敬請(qǐng)關(guān)注。 自主招生郵箱： 數(shù)學(xué)競(jìng)賽郵箱： 物理競(jìng)賽郵箱： 化學(xué)競(jìng)賽郵箱： 生物競(jìng)賽郵箱： 理科精英郵箱： 2013-12-15 發(fā)布 清北學(xué)堂教學(xué)研究部 清北學(xué)堂集中 培訓(xùn)課程 導(dǎo)學(xué)資料 （ 2014 年寒假集中培訓(xùn) 課程 使用 ） QBXT/JY/DX2013/12-3-4 清北學(xué)堂集中培訓(xùn)課程導(dǎo)學(xué)資料 北京清北學(xué)堂教育科技有限公司 第 1 頁 2014 年寒假 數(shù)學(xué)聯(lián)賽 提高 班 導(dǎo)學(xué) (組合數(shù)學(xué)部分 ) 目錄 一、 課程重點(diǎn)及難點(diǎn)概述 . 2 二、 清北導(dǎo)學(xué) . 3 排列與組合 . 3 知識(shí)點(diǎn) . 3 組合恒等式 . 5 重點(diǎn)及難點(diǎn) . 5 知識(shí)點(diǎn) . 5 思考題 . 6 常用排列組合思想 . 7 知識(shí)點(diǎn) . 7 抽屜原理、容斥原理、極端原理 . 8 知識(shí)點(diǎn) . 8 思考題 . 9 清北學(xué)堂集中培訓(xùn)課程導(dǎo)學(xué)資料 北京清北學(xué)堂教育科技有限公司 第 2 頁 一、 課程重點(diǎn)及難點(diǎn)概述 本次 課程 的重點(diǎn) 為組合計(jì)數(shù) 。 應(yīng)用基本組合計(jì)數(shù)原理和組合恒等式來解決實(shí)際問題是本次課程的難點(diǎn)。集訓(xùn)二 以真題講解為主，穿插相關(guān)知識(shí)點(diǎn)，訓(xùn)練同學(xué)的解題思路。 清北學(xué)堂集中培訓(xùn)課程導(dǎo)學(xué)資料 北京清北學(xué)堂教育科技有限公司 第 3 頁 二、 清北導(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)課程導(dǎo)學(xué)資料 北京清北學(xué)堂教育科技有限公司 第 4 頁 5. 分步計(jì)數(shù)原理 ：完成一件事，有幾個(gè)步驟，第一步有 m 種方法，第二步有 n 種方法，最后一步有 r 種方法，要完成這件事，必須通過每一步，則完成這件事的方法總數(shù)為 rnm 。應(yīng)用分步計(jì)數(shù)原理的關(guān)鍵在于分解。 清北學(xué)堂集中培訓(xùn)課程導(dǎo)學(xué)資料 北京清北學(xué)堂教育科技有限公司 第 5 頁 組合恒等式 重點(diǎn)及難點(diǎn) 掌握基本的排列組合恒等式、學(xué)會(huì)組合表達(dá)式的化簡(jiǎn)是本次課程的重點(diǎn)。綜合應(yīng)用組合恒等式和排列組合數(shù)學(xué)意義來證明某些組合恒等式是本次課程的難點(diǎn)。 知識(shí)點(diǎn) 1. 常用 排列組合公式 ： 0)1(212)1()1()1()!(!)1()1()!(!321021011111nnnnnnnnnnnnnmrmnmnmnrnrnrnrnrnrnrnnrnmnmnCCCCCCCCCCCCCCrnCCCCCCmmmnnnmnmnCmnnnmnnA 2. 母函數(shù)法 把離散數(shù)列和冪級(jí)數(shù)一一對(duì)應(yīng)起來，把離散數(shù)列間的相互結(jié)合關(guān)系對(duì)應(yīng)成冪級(jí)數(shù)間的運(yùn)算關(guān)系，最后由冪級(jí)數(shù)來確定離散數(shù)列的構(gòu)造。 簡(jiǎn)要地說，母函數(shù)方法是將一個(gè)有限或無限的數(shù)列 , 210 kk aaaaa 和如下形式的多項(xiàng)式 kk xaxaxaaxf 2210)( 聯(lián)系起來，構(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)課程導(dǎo)學(xué)資料 北京清北學(xué)堂教育科技有限公司 第 6 頁 例如：組合數(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)課程導(dǎo)學(xué)資料 北京清北學(xué)堂教育科技有限公司 第 7 頁 常用排列組合思想 知識(shí)點(diǎn) （ 1）排除：對(duì)有限條件的問題，先從總體考慮，再把不符合條件的所有情況排除，這是解決排列組合題的常用策略 。 （ 2）分類與分步 :有些問題的處理可分成若干類，用加法原理，要注意每?jī)深惖慕患癁榭占懈黝惖牟⒓侨?；有些問題的處理分成 幾個(gè)步驟，把各個(gè)步驟的方法數(shù)相乘，即得總的方法數(shù)，這是乘法原理。 （ 3）對(duì) 稱思想：兩類情形出現(xiàn)的機(jī)會(huì)均等，可用總數(shù)取半得每種情形的方法數(shù)。 （ 4）插空：某些元素不能相鄰或某些元素在特殊位置時(shí)可采用插空法。 即先安排好沒有限制條件的元素， 然后將有限制條件的元素按要求插入到排好的元素之間。 （ 5）捆綁：把相鄰的若干特殊元素 “ 捆綁 ” 為一個(gè) “ 大元素 ” ，然后與其它 “ 普通元素 ” 全排列，然后再 “ 松綁 ” ，將這些特殊元素在這些位置上全 排列。 （ 6）隔板模型： 類似求解不定方程 ),( NMwzyxMwzyx 的非負(fù)整數(shù)解的個(gè)數(shù)的問題，可以采用隔板法。將 M 個(gè)相同的小球與 3 個(gè)隔板進(jìn)行排列，第一個(gè)隔板之前的小球數(shù)為 x 值，第一個(gè)隔板與第二個(gè)隔板之前的小球數(shù)為 y 值，第二個(gè)隔板與第三個(gè)隔板之前的小球數(shù)為 z 值，第三個(gè)隔板之前的小球數(shù)為 w 值。 清北學(xué)堂集中培訓(xùn)課程導(dǎo)學(xué)資料 北京清北學(xué)堂教育科技有限公司 第 8 頁 抽屜原理、容斥原理、極端原理 知識(shí)點(diǎn) 1. 抽屜原理 表述一： 把多于 n 個(gè)的物體放到 n 個(gè) 抽屜 里，則至少有一個(gè)抽屜里的東西不少于兩件 。 表述二： 把多于 )0( kkmn 個(gè)的物體放到 n 個(gè)抽屜里，則至少有一個(gè)抽屜里有不少于 1m 個(gè) 的物體。 表述三： 把無窮多件物體放入 n 個(gè)抽屜，則至少有一個(gè)抽屜里 有無窮個(gè)物體。 抽屜原理為解決一些存在性問題提供了一種巧妙的方法。 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ì)無窮多個(gè)實(shí)數(shù)可能不成立，例如對(duì)于集合 2-n|n N，其中就沒有最小的數(shù)。對(duì)于自然數(shù)集，有最小數(shù)原理：若 M 是自然數(shù)集 N 的任一非空子集（有限或無限均可），則 M 中必有最小的數(shù)。 清北學(xué)堂集中培訓(xùn)課程導(dǎo)學(xué)資料 北京清北學(xué)堂教育科技有限公司 第 9 頁 2 最短長(zhǎng)度原理 、 最短長(zhǎng)度原理 1：任意給定兩點(diǎn)，所有連接這兩點(diǎn)的線中，以直線段的長(zhǎng)度為最短。 2：在連接一已知點(diǎn)和已知直線或已知平面的點(diǎn)的所