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

《高中奧賽數(shù)學(xué)競賽專題講座-組合數(shù)學(xué)課件》由會員分享，可在線閱讀，更多相關(guān)《高中奧賽數(shù)學(xué)競賽專題講座-組合數(shù)學(xué)課件（36頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四

2、級,第五級,*,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,數(shù)學(xué)競賽中,的組合問題,數(shù)學(xué)競賽中,（一）主要類型,1,

3、、組合計數(shù)問題,包括有限集合元素的計算、相應(yīng)子集的計算、集合分拆方法數(shù)的計算等，表現(xiàn)為數(shù)值計算、組合恒等式或組合不等式的證明知識基礎(chǔ)是加法原理、乘法原理和排列組合公式；常用的方法有：代數(shù)恒等變形、二項式定理、數(shù)學(xué)歸納法、遞推、組合分析、容斥原理等,一、概論,（一）主要類型一、概論,（一）主要類型,1,、組合計數(shù)問題包括：,問題類型：,主要有：有限集合元素的計算、子集的計算、集合分拆的計算,解題方法：,主要有：代數(shù)恒等變形、二項式定理、組合等式、遞推、組合分析、容斥原理、數(shù)學(xué)歸納法。,一、概論,（一）主要類型一、概論,（一）主要類型,2,、組合設(shè)計問題,其基本含義是，對有限集合，按照性質(zhì)來作出安

4、排，有時，只是證實具有性質(zhì)的安排是否存在、或者驗證作出的安排是否具有性質(zhì)（稱為存在性問題，又可分為肯定型、否定型和探究型）；有時，則需把具體安排（或具體性質(zhì)）找出來（稱為構(gòu)造型問題）；進一步，還要找出較好的安排（稱為最優(yōu)化問題）,一、概論,（一）主要類型一、概論,（一）主要類型,2,、組合設(shè)計問題：對集合,A,，按照某種性質(zhì),P,來作出安排，包括,問題類型,主要有：存在性問題，構(gòu)造性問題，最優(yōu)化問題,解題方法：,主要有：構(gòu)造法、反證法、抽屜原理、染色方法、,遞推方法,一、概論,（一）主要類型一、概論,（二）,發(fā)展特點,以組合計數(shù)、組合設(shè)計為基礎(chǔ)，與數(shù)論、幾何交叉，形成組合數(shù)論、組合幾何、集合分

5、拆三大熱點，突出而鮮明的體現(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ù)的

6、計算公式為：,二、,基礎(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ù)

7、計算公式為：,定義 從,n,個不同的元素中，允許重復(fù)取出,m,個元素，不管怎樣的順序并成一組，稱為,n,個相異元素允許重復(fù)的,m,元組合,相異元素的可重復(fù)組合數(shù)計算公式為：,二、,基礎(chǔ)知識,定義 從n個不同的元素中，允許重復(fù)取出m個元素，按照一定,定義 若,n,個元素中，有,n,1,個,a,1,，,n,2,個,a,2,個,a,，,且，則這個元素的,全排列，稱為不盡相異元素的全排列,不盡相異元素的全排列公式為：,定義 如果是一個元有限集合，那么，它,的子集組成的集合,叫做的一個子集系,二、,基礎(chǔ)知識,定義 若n個元素中，有n1個a1，n2個a2二、,定理,5,元集合中含有個元素的子集有個；集合的

8、所有子集共有個,定理,6,（抽屜原理）,（,1,）,把多于,n,個的物體放到,n,個抽屜里，則至少有一個抽屜里的東西不少于兩件。,（,2,）,把多于,mn+1,個的物體放到,n,個抽屜里，則至少有一個抽屜里有不少于,m+1,的物體。,（,3,）,把（,mn,1,）個物體放入,n,個抽屜中，其中必有一個抽屜中至多有（,m,1,）個物體。,二、,基礎(chǔ)知識,定理5 元集合中含有個元素的子集有個；集,舉例說明,抽屜原理,例,1,幼兒園買來了不少白兔、熊貓、長頸鹿塑料玩具，每個小朋友任意選擇兩件，那么不管怎樣挑選，在任意七個小朋友中總有兩個彼此選的玩具都相同，試說明道理,.,解 從三種玩具中挑選兩件，搭

9、配方式只能是下面六種：,（兔、兔），（兔、熊貓），（兔、長頸鹿），（熊貓、熊貓），（熊貓、長頸鹿），（長頸鹿、長頸鹿）,把每種搭配方式看作一個抽屜，把,7,個小朋友看作物體，那么根據(jù)原則,1,，至少有兩個物體要放進同一個抽屜里，也就是說，至少兩人挑選玩具采用同一搭配方式，選的玩具相同,.,舉例說明抽屜原理例1 幼兒園買來了不少白兔、熊貓、長頸鹿塑,舉例說明,抽屜原理,例,2,正方體各面上涂上紅色或藍色的油漆（每面只涂一種色），證明正方體一定有三個面顏色相同,.,證明：把兩種顏色當作兩個抽屜，把正方體六個面當作物體，那么,6=22+2,，根據(jù)原則二，至少有三個面涂上相同的顏色,.,舉例說明抽屜原

10、理例2正方體各面上涂上紅色或藍色的油漆（每面只,舉例說明,抽屜原理,例,3,從自然數(shù),1,，,2,，,3,，,99,，,100,這,100,個數(shù)中隨意取出,51,個數(shù)來，求證：其中一定有兩個數(shù)，它們中的一個是另一個的倍數(shù),.,解設(shè)第一個抽屜里放進數(shù)：,1,，,12,，,12,2,，,12,3,，,12,4,，,12,5,，,12,6,；,第二個抽屜時放進數(shù)：,3,，,32,，,32,2,，,32,3,，,32,4,，,32,5,；,第三個抽屜里放進數(shù)：,5,，,52,，,52,2,，,52,3,，,52,4,；,第二十五個抽屜里放進數(shù)：,49,，,492,；,第二十六個抽屜里放進數(shù)：,51.,

11、第五十個抽屜里放進數(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ǔ)知識

12、,定理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é)競賽專題講座

13、-組合數(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é)

14、聯(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,