數(shù)學(xué)競(jìng)賽專(zhuān)題講座組合數(shù)學(xué)課件

1、數(shù)學(xué)競(jìng)賽專(zhuān)題講座組合數(shù)學(xué)數(shù)學(xué)競(jìng)賽專(zhuān)題講座組合數(shù)學(xué)數(shù)學(xué)競(jìng)賽專(zhuān)題講座組合數(shù)學(xué) 數(shù)學(xué)競(jìng)賽中 的組合問(wèn)題 數(shù)學(xué)競(jìng)賽中 的組合問(wèn)題 （一）主要類(lèi)型1、組合計(jì)數(shù)問(wèn)題 包括有限集合元素的計(jì)算、相應(yīng)子集的計(jì)算、集合分拆方法數(shù)的計(jì)算等，表現(xiàn)為數(shù)值計(jì)算、組合恒等式或組合不等式的證明知識(shí)基礎(chǔ)是加法原理、乘法原理和排列組合公式；常用的方法有：代數(shù)恒等變形、二項(xiàng)式定理、數(shù)學(xué)歸納法、遞推、組合分析、容斥原理等一、概論（一）主要類(lèi)型1、組合計(jì)數(shù)問(wèn)題包括： 問(wèn)題類(lèi)型：主要有：有限集合元素的計(jì)算、子集的計(jì)算、集合分拆的計(jì)算解題方法：主要有：代數(shù)恒等變形、二項(xiàng)式定理、組合等式、遞推、組合分析、容斥原理、數(shù)學(xué)歸納法。一、概論（一）

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

3、點(diǎn) ，突出而鮮明的體現(xiàn)數(shù)學(xué)競(jìng)賽的“問(wèn)題解決”特征這三方面之所以成為熱點(diǎn)，從思維方式、解題技巧上分析，是因?yàn)槠涓m宜數(shù)學(xué)尖子的脫穎而出，且常與現(xiàn)代數(shù)學(xué)思想相聯(lián)系；從技術(shù)層面上分析，還由于都能方便提供挑戰(zhàn)中學(xué)生的新穎題目一、概論有個(gè)定義、9個(gè)定理：定義 從n個(gè)不同的元素中取出m個(gè)，按照一定的順序排成一列，叫做從n個(gè)不同的元素中取出m個(gè)元素的一個(gè)排列相異元素排列數(shù)的計(jì)算公式為： 二、基礎(chǔ)知識(shí) 定義 從n個(gè)不同的元素中取出m個(gè)，并成一組，叫做從n個(gè)不同的元素中取出m個(gè)元素的一個(gè)組合相異元素組合數(shù)的計(jì)算公式為：二、基礎(chǔ)知識(shí) 定理 （加法原理）定理2 （乘法原理）定理3 組合恒等式(1)(2)(3)(4)

4、二、基礎(chǔ)知識(shí) 定理4 （二項(xiàng)式定理） 定義 從n個(gè)不同的元素中取出m個(gè)，按照一定的順序排在一個(gè)封閉曲線上，叫做環(huán)形排列（或循環(huán)排列、圓排列）相異元素的 圓排列數(shù)公式為：二、基礎(chǔ)知識(shí) 定義 從n個(gè)不同的元素中，允許重復(fù)取出m個(gè)元素，按照一定的順序排成一列，稱(chēng)為n個(gè)相異元素允許重復(fù)的m元排列相異元素的可重復(fù)排列數(shù)計(jì)算公式為：定義 從n個(gè)不同的元素中，允許重復(fù)取出m個(gè)元素，不管怎樣的順序并成一組，稱(chēng)為n個(gè)相異元素允許重復(fù)的m元組合 相異元素的可重復(fù)組合數(shù)計(jì)算公式為：二、基礎(chǔ)知識(shí) 定義 若n個(gè)元素中，有n1個(gè)a1， n2個(gè)a2個(gè)a，且，則這個(gè)元素的全排列，稱(chēng)為不盡相異元素的全排列不盡相異元素的全排列公

5、式為：定義 如果是一個(gè)元有限集合，那么，它的子集組成的集合叫做的一個(gè)子集系二、基礎(chǔ)知識(shí) 定理5 元集合中含有個(gè)元素的子集有個(gè)；集合的所有子集共有個(gè)定理6 （抽屜原理）（1）把多于n個(gè)的物體放到n個(gè)抽屜里，則至少有一個(gè)抽屜里的東西不少于兩件。 （2）把多于mn+1個(gè)的物體放到n個(gè)抽屜里，則至少有一個(gè)抽屜里有不少于m+1的物體。 （3）把（mn1）個(gè)物體放入n個(gè)抽屜中，其中必有一個(gè)抽屜中至多有（m1）個(gè)物體。 二、基礎(chǔ)知識(shí) 舉例說(shuō)明抽屜原理例1 幼兒園買(mǎi)來(lái)了不少白兔、熊貓、長(zhǎng)頸鹿塑料玩具，每個(gè)小朋友任意選擇兩件，那么不管怎樣挑選，在任意七個(gè)小朋友中總有兩個(gè)彼此選的玩具都相同，試說(shuō)明道理.解 從三種

6、玩具中挑選兩件，搭配方式只能是下面六種：（兔、兔），（兔、熊貓），（兔、長(zhǎng)頸鹿），（熊貓、熊貓），（熊貓、長(zhǎng)頸鹿），（長(zhǎng)頸鹿、長(zhǎng)頸鹿）把每種搭配方式看作一個(gè)抽屜，把7個(gè)小朋友看作物體，那么根據(jù)原則1，至少有兩個(gè)物體要放進(jìn)同一個(gè)抽屜里，也就是說(shuō)，至少兩人挑選玩具采用同一搭配方式，選的玩具相同.舉例說(shuō)明抽屜原理例2正方體各面上涂上紅色或藍(lán)色的油漆（每面只涂一種色），證明正方體一定有三個(gè)面顏色相同.證明：把兩種顏色當(dāng)作兩個(gè)抽屜，把正方體六個(gè)面當(dāng)作物體，那么6=22+2，根據(jù)原則二，至少有三個(gè)面涂上相同的顏色.舉例說(shuō)明抽屜原理例3 從自然數(shù)1，2，3，99，100這100個(gè)數(shù)中隨意取出51個(gè)數(shù)來(lái)，求證

7、：其中一定有兩個(gè)數(shù)，它們中的一個(gè)是另一個(gè)的倍數(shù).解設(shè)第一個(gè)抽屜里放進(jìn)數(shù)：1，12，122，123，124，125，126；第二個(gè)抽屜時(shí)放進(jìn)數(shù)：3，32，322，323，324，325；第三個(gè)抽屜里放進(jìn)數(shù)：5，52，522，523，524；第二十五個(gè)抽屜里放進(jìn)數(shù)：49，492；第二十六個(gè)抽屜里放進(jìn)數(shù)：51.第五十個(gè)抽屜里放進(jìn)數(shù)：99.那么隨意取出51個(gè)數(shù)中，必有兩個(gè)數(shù)同屬一個(gè)抽屜，其中一個(gè)數(shù)是另一個(gè)數(shù)的倍數(shù).定理7 （容斥原理）設(shè)集合 ，記 為 對(duì)于全集的補(bǔ)集，則(1)(2)定理8 （自然數(shù)的良序性）自然數(shù)的任一非空子集中，必有一個(gè)元素是最小的 二、基礎(chǔ)知識(shí) 定理9 設(shè)A,B是兩個(gè)有限元集合，

8、分別是兩集合的元素個(gè)數(shù)，f是A到B的一個(gè)映射（）若f是單射，則 ；特別的，f是單射而非滿(mǎn)射，則 （）若f是滿(mǎn)射，則 （）若f是一一映射（雙射），則 二、基礎(chǔ)知識(shí) （二）、高中數(shù)學(xué)競(jìng)賽大綱 中組合問(wèn)題的要求1、圓排列，有重復(fù)元素的排列與組合，組合恒等式2、組合計(jì)數(shù)，組合幾何 3、抽屜原理4、容斥原理 5、極端原理6、圖論問(wèn)題 7、集合的劃分8、覆蓋9、平面凸集、凸包及應(yīng)用*（加試中暫不考，但在冬令營(yíng)中可能考）二、基礎(chǔ)知識(shí) 1、計(jì)數(shù)問(wèn)題三、題型舉例 1、計(jì)數(shù)問(wèn)題三、題型舉例 2、染色問(wèn)題三、題型舉例 3、存在性問(wèn)題三、題型舉例 4、組合構(gòu)造三、題型舉例 5、組合數(shù)論三、題型舉例 6、操作性問(wèn)題三、題型舉例 7、最值性問(wèn)題三、題型舉例 8、圖論9、組合方法10、綜合問(wèn)題三、題型舉例 在高中數(shù)學(xué)聯(lián)賽的所有題目中，相信最讓大家頭痛的莫過(guò)于組合題了，有些同學(xué)覺(jué)得做組合題很容易就繞暈了，不知道如何下手；有些同學(xué)看了答案總是會(huì)說(shuō)，這個(gè)題想法太怪了，不可能想不出來(lái)；有些同學(xué)好不容易想出了答案，卻經(jīng)常因?yàn)楸磉_(dá)不清楚而得不到分。確實(shí)，組合題對(duì)數(shù)學(xué)思維的要求非常高，它經(jīng)常作為聯(lián)賽二試的最后一題出現(xiàn)，會(huì)比另外幾塊內(nèi)容難上很多，但也并不是無(wú)跡可尋的