高中奧賽數(shù)學(xué)競賽專題講座 組合數(shù)學(xué)課件

數(shù)學(xué)競賽中的組合問題

數(shù)學(xué)競賽中（一）主要類型1、組合計數(shù)問題包括有限集合元素的計算、相應(yīng)子集的計算、集合分拆方法數(shù)的計算等，表現(xiàn)為數(shù)值計算、組合恒等式或組合不等式的證明．知識基礎(chǔ)是加法原理、乘法原理和排列組合公式；常用的方法有：代數(shù)恒等變形、二項式定理、數(shù)學(xué)歸納法、遞推、組合分析、容斥原理等．一、概論（一）主要類型一、概論（一）主要類型1、組合計數(shù)問題包括：①問題類型：主要有：有限集合元素的計算、子集的計算、集合分拆的計算②解題方法：主要有：代數(shù)恒等變形、二項式定理、組合等式、遞推、組合分析、容斥原理、數(shù)學(xué)歸納法。一、概論（一）主要類型一、概論（一）主要類型2、組合設(shè)計問題其基本含義是，對有限集合，按照性質(zhì)來作出安排，有時，只是證實具有性質(zhì)的安排是否存在、或者驗證作出的安排是否具有性質(zhì)（稱為存在性問題，又可分為肯定型、否定型和探究型）；有時，則需把具體安排（或具體性質(zhì)）找出來（稱為構(gòu)造型問題）；進一步，還要找出較好的安排（稱為最優(yōu)化問題）．一、概論（一）主要類型一、概論（一）主要類型2、組合設(shè)計問題：對集合A，按照某種性質(zhì)P來作出安排，包括①問題類型主要有：存在性問題，構(gòu)造性問題，最優(yōu)化問題．②解題方法：主要有：構(gòu)造法、反證法、抽屜原理、染色方法、遞推方法一、概論（一）主要類型一、概論（二）

發(fā)展特點以組合計數(shù)、組合設(shè)計為基礎(chǔ)，與數(shù)論、幾何交叉，形成組合數(shù)論、組合幾何、集合分拆三大熱點，突出而鮮明的體現(xiàn)數(shù)學(xué)競賽的“問題解決”特征．這三方面之所以成為熱點，從思維方式、解題技巧上分析，是因為其更適宜數(shù)學(xué)尖子的脫穎而出，且常與現(xiàn)代數(shù)學(xué)思想相聯(lián)系；從技術(shù)層面上分析，還由于都能方便提供挑戰(zhàn)中學(xué)生的新穎題目．一、概論一、概論有７個定義、9個定理：定義１從n個不同的元素中取出m個，按照一定的順序排成一列，叫做從n個不同的元素中取出m個元素的一個排列．相異元素排列數(shù)的計算公式為：．二、基礎(chǔ)知識

有７個定義、9個定理：二、基礎(chǔ)知識定義２從n個不同的元素中取出m個，并成一組，叫做從n個不同的元素中取出m個元素的一個組合．相異元素組合數(shù)的計算公式為：二、基礎(chǔ)知識

定義２從n個不同的元素中取出m個，并成一組，叫做從n個不定理１（加法原理）定理2（乘法原理）定理3組合恒等式(1)(2)(3)(4)二、基礎(chǔ)知識

定理１（加法原理）二、基礎(chǔ)知識定理4（二項式定理）

定義３從n個不同的元素中取出m個，按照一定的順序排在一個封閉曲線上，叫做環(huán)形排列（或循環(huán)排列、圓排列）．相異元素的圓排列數(shù)公式為：二、基礎(chǔ)知識

定理4（二項式定理）二、基礎(chǔ)知識定義４從n個不同的元素中，允許重復(fù)取出m個元素，按照一定的順序排成一列，稱為n個相異元素允許重復(fù)的m元排列．相異元素的可重復(fù)排列數(shù)計算公式為：定義５從n個不同的元素中，允許重復(fù)取出m個元素，不管怎樣的順序并成一組，稱為n個相異元素允許重復(fù)的m元組合．相異元素的可重復(fù)組合數(shù)計算公式為：二、基礎(chǔ)知識

定義４從n個不同的元素中，允許重復(fù)取出m個元素，按照一定定義６若n個元素中，有n1個a1，n2個a2．．．ｎｍ個aｍ，且，則這ｎ個元素的全排列，稱為不盡相異元素的全排列．不盡相異元素的全排列公式為：定義７如果Ａ是一個ｎ元有限集合，那么，它的子集組成的集合叫做的一個子集系．二、基礎(chǔ)知識

定義６若n個元素中，有n1個a1，n2個a2．．．二、定理5ｎ元集合Ａ中含有個元素的子集有個；集合Ａ的所有子集共有個．定理6（抽屜原理）（1）把多于n個的物體放到n個抽屜里，則至少有一個抽屜里的東西不少于兩件。（2）把多于mn+1個的物體放到n個抽屜里，則至少有一個抽屜里有不少于m+1的物體。（3）把（mn－1）個物體放入n個抽屜中，其中必有一個抽屜中至多有（m—1）個物體。二、基礎(chǔ)知識

定理5ｎ元集合Ａ中含有個元素的子集有個；集舉例說明抽屜原理例1

幼兒園買來了不少白兔、熊貓、長頸鹿塑料玩具，每個小朋友任意選擇兩件，那么不管怎樣挑選，在任意七個小朋友中總有兩個彼此選的玩具都相同，試說明道理.解從三種玩具中挑選兩件，搭配方式只能是下面六種：（兔、兔），（兔、熊貓），（兔、長頸鹿），（熊貓、熊貓），（熊貓、長頸鹿），（長頸鹿、長頸鹿）把每種搭配方式看作一個抽屜，把7個小朋友看作物體，那么根據(jù)原則1，至少有兩個物體要放進同一個抽屜里，也就是說，至少兩人挑選玩具采用同一搭配方式，選的玩具相同.舉例說明抽屜原理例1

幼兒園買來了不少白兔、熊貓、長頸鹿塑舉例說明抽屜原理例2正方體各面上涂上紅色或藍色的油漆（每面只涂一種色），證明正方體一定有三個面顏色相同.證明：把兩種顏色當作兩個抽屜，把正方體六個面當作物體，那么6=2×2+2，根據(jù)原則二，至少有三個面涂上相同的顏色.舉例說明抽屜原理例2正方體各面上涂上紅色或藍色的油漆（每面只舉例說明抽屜原理例3從自然數(shù)1，2，3，…99，100這100個數(shù)中隨意取出51個數(shù)來，求證：其中一定有兩個數(shù)，，它們中的一個是另一個的倍數(shù).解設(shè)第一個抽屜里放進數(shù)：1，1×2，1×22，1×23，1×24，1×25，1×26；第二個抽屜時放進數(shù)：3，3×2，3×22，3×23，3×24，3×25；第三個抽屜里放進數(shù)：5，5×2，5×22，5×23，5×24；………………第二十五個抽屜里放進數(shù)：49，49×2；第二十六個抽屜里放進數(shù)：51.………………第五十個抽屜里放進數(shù)：99.那么隨意取出51個數(shù)中，必有兩個數(shù)同屬一個抽屜，其中一個數(shù)是另一個數(shù)的倍數(shù).舉例說明抽屜原理例3從自然數(shù)1，2，3，…99，100這1定理7（容斥原理）設(shè)集合，記為對于全集的補集，則(1)(2)定理8（自然數(shù)的良序性）自然數(shù)的任一非空子集中，必有一個元素是最小的．

二、基礎(chǔ)知識

定理7（容斥原理）設(shè)集合定理9設(shè)A,B是兩個有限元集合，分別是兩集合的元素個數(shù)，f是A到B的一個映射．（１）若f是單射，則；特別的，f是單射而非滿射，則（２）若f是滿射，則（３）若f是一一映射（雙射），則二、基礎(chǔ)知識

定理9設(shè)A,B是兩個有限元集合，分別是兩集合的元（二）、《高中數(shù)學(xué)競賽大綱》中組合問題的要求1、圓排列，有重復(fù)元素的排列與組合，組合恒等式．2、組合計數(shù)，組合幾何．3、抽屜原理．4、容斥原理．5、極端原理．6、圖論問題．7、集合的劃分．8、覆蓋．9、平面凸集、凸包及應(yīng)用*．（加試中暫不考，但在冬令營中可能考）．二、基礎(chǔ)知識

（二）、《高中數(shù)學(xué)競賽大綱》中組合問題的要求二、基礎(chǔ)知識1、計數(shù)問題三、題型舉例1、計數(shù)問題三、題型舉例1、計數(shù)問題三、題型舉例1、計數(shù)問題三、題型舉例2、染色問題三、題型舉例2、染色問題三、題型舉例高中奧賽數(shù)學(xué)競賽專題講座組合數(shù)學(xué)課件3、存在性問題三、題型舉例3、存在性問題三、題型舉例高中奧賽數(shù)學(xué)競賽專題講座組合數(shù)學(xué)課件4、組合構(gòu)造三、題型舉例4、組合構(gòu)造三、題型舉例高中奧賽數(shù)學(xué)競賽專題講座組合數(shù)學(xué)課件5、組合數(shù)論三、題型舉例5、組合數(shù)論三、題型舉例高中奧賽數(shù)學(xué)競賽專題講座組合數(shù)學(xué)課件6、操作性問題三、題型舉例6、操作性問題三、題型舉例高中奧賽數(shù)學(xué)競賽專題講座組合數(shù)學(xué)課件7、最值性問題三、題型舉例7、最值性問題三、題型舉例高中奧賽數(shù)學(xué)競賽專題講座組合數(shù)學(xué)課件8、圖論9、組合方法10、綜合問題三、題型舉例8、圖論三、題型舉例在高中數(shù)學(xué)聯(lián)賽的所有題目中，相信最讓大家頭痛的莫過于組合題了，有些同學(xué)覺得做組合題很容易就繞暈了，不知道如何下手；有些同學(xué)看了答案總是會說，這個題想法太怪了，不可能想不出來；有些同學(xué)好不容易想出了答案，卻經(jīng)常因為表達不清楚而得不到分。確實，組合題對數(shù)學(xué)思維的要求非常高，它經(jīng)常作為聯(lián)賽二試的最后一題出現(xiàn)，會比另外幾塊內(nèi)容難上很多，但也并不是無跡可尋的。

組合問題的知識點并不多，主要在于對問題性質(zhì)的探索與思考。聯(lián)賽中組合題以存在性問題和最值問題以及組合數(shù)論問題為主，這類問題的關(guān)鍵常常在于構(gòu)造例子或反例。因此，只要我們多加練習(xí)這兩類問題，在聯(lián)賽中還是可以拿到滿意的分數(shù)的。四、結(jié)束語在高中數(shù)學(xué)聯(lián)賽的所有題目中，相信最謝謝各位!2016-07-23謝謝各位!2016-07-23數(shù)學(xué)競賽中的組合問題

數(shù)學(xué)競賽中（一）主要類型1、組合計數(shù)問題包括有限集合元素的計算、相應(yīng)子集的計算、集合分拆方法數(shù)的計算等，表現(xiàn)為數(shù)值計算、組合恒等式或組合不等式的證明．知識基礎(chǔ)是加法原理、乘法原理和排列組合公式；常用的方法有：代數(shù)恒等變形、二項式定理、數(shù)學(xué)歸納法、遞推、組合分析、容斥原理等．一、概論（一）主要類型一、概論（一）主要類型1、組合計數(shù)問題包括：①問題類型：主要有：有限集合元素的計算、子集的計算、集合分拆的計算②解題方法：主要有：代數(shù)恒等變形、二項式定理、組合等式、遞推、組合分析、容斥原理、數(shù)學(xué)歸納法。一、概論（一）主要類型一、概論（一）主要類型2、組合設(shè)計問題其基本含義是，對有限集合，按照性質(zhì)來作出安排，有時，只是證實具有性質(zhì)的安排是否存在、或者驗證作出的安排是否具有性質(zhì)（稱為存在性問題，又可分為肯定型、否定型和探究型）；有時，則需把具體安排（或具體性質(zhì)）找出來（稱為構(gòu)造型問題）；進一步，還要找出較好的安排（稱為最優(yōu)化問題）．一、概論（一）主要類型一、概論（一）主要類型2、組合設(shè)計問題：對集合A，按照某種性質(zhì)P來作出安排，包括①問題類型主要有：存在性問題，構(gòu)造性問題，最優(yōu)化問題．②解題方法：主要有：構(gòu)造法、反證法、抽屜原理、染色方法、遞推方法一、概論（一）主要類型一、概論（二）

發(fā)展特點以組合計數(shù)、組合設(shè)計為基礎(chǔ)，與數(shù)論、幾何交叉，形成組合數(shù)論、組合幾何、集合分拆三大熱點，突出而鮮明的體現(xiàn)數(shù)學(xué)競賽的“問題解決”特征．這三方面之所以成為熱點，從思維方式、解題技巧上分析，是因為其更適宜數(shù)學(xué)尖子的脫穎而出，且常與現(xiàn)代數(shù)學(xué)思想相聯(lián)系；從技術(shù)層面上分析，還由于都能方便提供挑戰(zhàn)中學(xué)生的新穎題目．一、概論一、概論有７個定義、9個定理：定義１從n個不同的元素中取出m個，按照一定的順序排成一列，叫做從n個不同的元素中取出m個元素的一個排列．相異元素排列數(shù)的計算公式為：．二、基礎(chǔ)知識

有７個定義、9個定理：二、基礎(chǔ)知識定義２從n個不同的元素中取出m個，并成一組，叫做從n個不同的元素中取出m個元素的一個組合．相異元素組合數(shù)的計算公式為：二、基礎(chǔ)知識

定義２從n個不同的元素中取出m個，并成一組，叫做從n個不定理１（加法原理）定理2（乘法原理）定理3組合恒等式(1)(2)(3)(4)二、基礎(chǔ)知識

定理１（加法原理）二、基礎(chǔ)知識定理4（二項式定理）

定義３從n個不同的元素中取出m個，按照一定的順序排在一個封閉曲線上，叫做環(huán)形排列（或循環(huán)排列、圓排列）．相異元素的圓排列數(shù)公式為：二、基礎(chǔ)知識

定理4（二項式定理）二、基礎(chǔ)知識定義４從n個不同的元素中，允許重復(fù)取出m個元素，按照一定的順序排成一列，稱為n個相異元素允許重復(fù)的m元排列．相異元素的可重復(fù)排列數(shù)計算公式為：定義５從n個不同的元素中，允許重復(fù)取出m個元素，不管怎樣的順序并成一組，稱為n個相異元素允許重復(fù)的m元組合．相異元素的可重復(fù)組合數(shù)計算公式為：二、基礎(chǔ)知識

定義４從n個不同的元素中，允許重復(fù)取出m個元素，按照一定定義６若n個元素中，有n1個a1，n2個a2．．．ｎｍ個aｍ，且，則這ｎ個元素的全排列，稱為不盡相異元素的全排列．不盡相異元素的全排列公式為：定義７如果Ａ是一個ｎ元有限集合，那么，它的子集組成的集合叫做的一個子集系．二、基礎(chǔ)知識

定義６若n個元素中，有n1個a1，n2個a2．．．二、定理5ｎ元集合Ａ中含有個元素的子集有個；集合Ａ的所有子集共有個．定理6（抽屜原理）（1）把多于n個的物體放到n個抽屜里，則至少有一個抽屜里的東西不少于兩件。（2）把多于mn+1個的物體放到n個抽屜里，則至少有一個抽屜里有不少于m+1的物體。（3）把（mn－1）個物體放入n個抽屜中，其中必有一個抽屜中至多有（m—1）個物體。二、基礎(chǔ)知識

定理5ｎ元集合Ａ中含有個元素的子集有個；集舉例說明抽屜原理例1

幼兒園買來了不少白兔、熊貓、長頸鹿塑料玩具，每個小朋友任意選擇兩件，那么不管怎樣挑選，在任意七個小朋友中總有兩個彼此選的玩具都相同，試說明道理.解從三種玩具中挑選兩件，搭配方式只能是下面六種：（兔、兔），（兔、熊貓），（兔、長頸鹿），（熊貓、熊貓），（熊貓、長頸鹿），（長頸鹿、長頸鹿）把每種搭配方式看作一個抽屜，把7個小朋友看作物體，那么根據(jù)原則1，至少有兩個物體要放進同一個抽屜里，也就是說，至少兩人挑選玩具采用同一搭配方式，選的玩具相同.舉例說明抽屜原理例1

幼兒園買來了不少白兔、熊貓、長頸鹿塑舉例說明抽屜原理例2正方體各面上涂上紅色或藍色的油漆（每面只涂一種色），證明正方體一定有三個面顏色相同.證明：把兩種顏色當作兩個抽屜，把正方體六個面當作物體，那么6=2×2+2，根據(jù)原則二，至少有三個面涂上相同的顏色.舉例說明抽屜原理例2正方體各面上涂上紅色或藍色的油漆（每面只舉例說明抽屜原理例3從自然數(shù)1，2，3，…99，100這100個數(shù)中隨意取出51個數(shù)來，求證：其中一定有兩個數(shù)，，它們中的一個是另一個的倍數(shù).解設(shè)第一個抽屜里放進數(shù)：1，1×2，1×22，1×23，1×24，1×25，1×26；第二個抽屜時放進數(shù)：3，3×2，3×22，3×23，3×24，3×25；第三個抽屜里放進數(shù)：5，5×2，5×22，5×23，5×24；………………第二十五個抽屜里放進數(shù)：49，49×2；第二十六個抽屜里放進數(shù)：51.………………第五十個抽屜里放進數(shù)：99.那么隨意取出51個數(shù)中，必有兩個數(shù)同屬一個抽屜，其中一個數(shù)是另一個數(shù)的倍數(shù).舉例說明抽屜原理例3從自然數(shù)1，2，3，…99，100這1定理7（容斥原理）設(shè)集合，記為對于全集的補集，則(1)(2)定理8（自然數(shù)的良序性）自然數(shù)的任一非空子集中，必有一個元素是最小的．

二、基礎(chǔ)知識

定理7（容斥原理）設(shè)集合定理9設(shè)A,B是兩個有限元集合，分別是兩集合的元素個數(shù)，f是A到B的一個映射．（１）若f是單射，則；特別的，f是單射而非滿射，則（２）若f是滿射，則（３）若f是一一映射（雙射），則二、基礎(chǔ)知識

定理9設(shè)A,B是兩個有限元集合，分別是兩集合的元（二）、《高中數(shù)學(xué)競賽大綱》中組合問題的要求1、圓排列，有重復(fù)元素的排列與組合，組合恒等式．2、組合計數(shù)，組合幾何．3、抽屜原理．4、容斥原理．5、極端原理．6、圖論問題．7、集合的劃分．8、覆蓋．9、平面凸集、凸包及應(yīng)用*．（加試中暫不考，但在冬令營中可能考）．二、基礎(chǔ)知識

（二）、《