組合問(wèn)題競(jìng)賽二試

組合問(wèn)題大綱要求:圓排列，有重復(fù)元素的排列與組合，組合恒等式。組合計(jì)數(shù)，組合幾何。抽屜原理。容斥原理。極端原理

圖論問(wèn)題。集合的劃分。覆蓋。平面凸集、凸包及應(yīng)用*。（注：有*號(hào)的內(nèi)容加試中暫不考，但在冬令營(yíng)中可能考。）一、計(jì)數(shù)原理、排列、組合基本定義與性質(zhì)（一）分類(lèi)計(jì)數(shù)加法原理、分步計(jì)數(shù)乘法原理（二）排列和排列數(shù)三）組合和組合數(shù)四）二項(xiàng)式定理二、組合恒等式競(jìng)賽數(shù)學(xué)中的組合恒等式是以高中排列組合、二項(xiàng)式定理為基礎(chǔ)，加以推廣、補(bǔ)充而形成的一類(lèi)組合問(wèn)題.組合恒等式的證明要借助于高中常見(jiàn)的基礎(chǔ)組合等式.例如Cr=Cn-rnnCr+1=Cr+1+CrTOC\o"1-5"\h\zn+1 n nCr=-Cr-1nr--1CrCm=Cm?Cr-mnr n n-mC0+C1+C2+ +Cn=2n\o"CurrentDocument"nnn nC0-C1+C2-C3+ +（-1）nCn=0\o"CurrentDocument"nnnn nCr+Cr+ +Cr=Cr+1r r+1 r+k..z+k+1范德蒙恒等式：丈CiCk-i=Ckmn m+ni=0組合恒等式的證明方法有：①恒等變形，變換求和指標(biāo)；②建立遞推關(guān)系；③數(shù)學(xué)歸納法；④考慮組合意義；⑤母函數(shù).三、組合不等式例1：對(duì)n>2證明（1）2n<Cn<4n；（2）Cn<4n-12n 2n-1證明：（1）當(dāng)n=2時(shí)，22<6=C2<42不等式成立

設(shè)2k<Ck<4k成立，貝Un=k+1時(shí)2kTOC\o"1-5"\h\z由Cn =Ck+1 = 2Ck >2Ck >2? 2k = 2k+1 = 2"2n 2k+2 2k+1 2kCn=2Ck=2?Ck<2?2Ck=4Ck<4?4k=4k+1=4"2n 2k+1 k+12k 2k 2k知不等式成立由歸納原理，對(duì)n>2不等式2n<Cn<4n恒成立2n2)4n2)4n-1=22n-2!Sck2 2n-1k=0藝Ck >Cn-1=Cn2n-1 2n-1 2n-1k=0素的全排列稱(chēng)為不全相異元素的全排列，其不同的排列個(gè)數(shù)記為(n素的全排列稱(chēng)為不全相異元素的全排列，其不同的排列個(gè)數(shù)記為(n 、(n …、，貝innn,1 2 k、nnn丿1 2 kn!四、有重復(fù)元素的排列與組合1、可重復(fù)的排列：從n個(gè)不同元素中取m個(gè)元素(同一元素允許重復(fù)取出)，按照一定的順序排成一列，叫做從"個(gè)不同元素中取m個(gè)元素的可重復(fù)的排列，這種排列的個(gè)數(shù)為"m。2、可重復(fù)的組合：從n個(gè)不同元素中取m個(gè)元素(同一元素允許重復(fù)取出)并成一組，叫做從n個(gè)不同元素中取m個(gè)元素的可重復(fù)組合，這種組合的個(gè)數(shù)為Cm。n+m-1例2：從銀行中取出伍角、一元、貳元、伍元、十元、五十元、一百元的紙幣共10張，共有多少種不同的取法？+nk=n'則這n個(gè)元3、不全相異元素的全排列：如果“個(gè)元素中，分別有n1,+nk=n'則這n個(gè)元例3：將3面紅旗、4面藍(lán)旗、2面黃旗依次懸掛在旗桿上，問(wèn)可以組成?多少種不同的標(biāo)志???4、相異元素的圓排列：將n個(gè)不同元素不分首尾排成一圈，稱(chēng)為n個(gè)相異元素的圓排列，其排列種數(shù)為(n-1)!。例4:6為女同學(xué)和15位男同學(xué)圍成一圈跳集體舞，要求每?jī)擅瑢W(xué)之間至少有兩名男同學(xué)，那么共有多少種不同的圍圈跳舞的方法?五、集合與容斥原理引入集合的交集、并集、補(bǔ)集概念后，研究它們之間的關(guān)系，由概念本身的內(nèi)涵和集合意義有計(jì)算集合元素個(gè)數(shù)的公式： _⑴n(AUB)=n(A)+n(B)—n(AAB)；⑵n(A)=1-n(A)；⑶n(AUBUC)=n(A)+n(B)+n(C)-n(AAB)-n(BAC)-n(CAA)+n(ABAC).這二個(gè)公式簡(jiǎn)稱(chēng)“容斥原理”其意義可用集合的圖形語(yǔ)言表示.于是，應(yīng)用“容斥原理”在解決實(shí)際計(jì)數(shù)問(wèn)題中的操作方法為：文字語(yǔ)言翻譯成集合語(yǔ)言，用集合將同類(lèi)元素分組；正確的使用容斥原理公式或其容斥原理的圖形語(yǔ)言進(jìn)行計(jì)數(shù)。復(fù)雜問(wèn)題注意補(bǔ)集思想的應(yīng)用，可以做到分類(lèi)“既不重復(fù)又不遺漏”.此結(jié)論可以推廣到n個(gè)集合的情況，即Ua=Qa-工|AAAI+工IaAAAA—?…+(-1)n-1pA.i i i j i j k ii=1 i=1 i豐j 1<i<j<k<n i=1例5、開(kāi)運(yùn)動(dòng)會(huì)時(shí)，高一某班共有28名學(xué)生參加比賽，有15人參加游泳比賽，有8人參加田徑比賽，有14人參加球類(lèi)比賽，同時(shí)參加游泳和田徑比賽的有3人，同時(shí)參加游泳和球類(lèi)比賽的有3人，沒(méi)有人同時(shí)二項(xiàng)比賽.問(wèn)同時(shí)參加田徑和球類(lèi)比賽的有多少人?只參加一項(xiàng)比賽的有多少人?簡(jiǎn)析：將文字語(yǔ)言翻譯成集合語(yǔ)言，用“容斥原理”公式求解，可做到“分類(lèi)完備”.設(shè)同時(shí)參加田徑和球類(lèi)比賽共

有X人，參加游泳為A={15人},參加田徑為B={8人},參加球類(lèi)為C={14人}.由條件知，APlB={3人},APlC={3人},APBPC=0，由“容斥原理”構(gòu)建方程有，15+8+14-3-3-x=2&解得x=3.因此，同時(shí)參加田徑和球類(lèi)比賽共有3人.同理只參加游泳的人有15-3-3=9人.例6、求1，2，3，…，100中不能被2，3，5整除的數(shù)的個(gè)數(shù)。【解】記I={1,2,3,…」。。},A={x1<x<100,且x能被2整除（記為2|x）}，100TB={x1<x<100,3x},C={x1<x<100,5x}100T|AUBUC=A+B+C|—|APB|—|BPC|-|CPA|+|APBPC|「罟］-［罟］-［罟］-［罟］+［糾］=74，所以不能被2,3,5整除的數(shù)有〔/HAUBUC|=26個(gè)。_5」6」10」15」30」五、抽屜原理抽屜原理：將mn+1個(gè)元素放入n（n>1）個(gè)抽屜，必有一個(gè)抽屜放有不少于m+1個(gè)元素，也必有一個(gè)抽屜放有不多于m個(gè)元素；將無(wú)窮多個(gè)元素放入n個(gè)抽屜必有一個(gè)抽屜放有無(wú)窮多個(gè)元素。抽屜原理有時(shí)也被稱(chēng)為鴿籠原理，它由德國(guó)數(shù)學(xué)家狄利克雷首先明確提出來(lái)并用來(lái)證明一些數(shù)論中的問(wèn)題，因此，也被稱(chēng)為狄利克雷原則．抽屜原理是組合數(shù)學(xué)中一個(gè)重要而又基本的數(shù)學(xué)原理，利用它可以解決很多有趣的問(wèn)題，并且常常能夠起到令人驚奇的作用．認(rèn)識(shí)——抽屜原理解決的是存在性問(wèn)題操作——構(gòu)造抽屜的方法：從問(wèn)題出發(fā)，相同即為抽屜；從數(shù)量出發(fā)：少的就是抽屜。抽屜原理1：將n+1個(gè)物品任意放到n個(gè)抽屜中，那么至少有一個(gè)抽屜中的物品不少于2件。原理要點(diǎn):（1）物品數(shù)比抽屜數(shù)多1。只有物品數(shù)比抽屜數(shù)多時(shí)抽屜原理才會(huì)成立。（2） 物品是“任意放”到抽屜中。（3） 其中“物品不少于2件”的抽屜是一定存在的，但是不確定是哪一個(gè)。（4） 原理的結(jié)論是：“至少有一個(gè)抽屜中的物品數(shù)不少于2件”，也可以這么說(shuō)，“至少有2件物品在同一個(gè)抽屜中”。例7：人的頭發(fā)平均有12萬(wàn)根。假設(shè)最多不超過(guò)20萬(wàn)根。13億人中至少有多少人的頭發(fā)根數(shù)相同？分析：從問(wèn)題出發(fā)，抽屜就是頭發(fā)根數(shù)。頭發(fā)根數(shù)最多不超20萬(wàn)，那么抽屜數(shù)為20萬(wàn)。物品為13億人。1300000000斗200000=6500，由抽屜原理2,至少有6500人的頭發(fā)根數(shù)相同。例8：新年晚會(huì)上，老師讓每個(gè)同學(xué)從一個(gè)裝有許多玻璃球的口袋中摸兩個(gè)球，這些球給人的手感相同。只有紅、黃、白、藍(lán)、綠五色之分（摸時(shí)看不到顏色），結(jié)果發(fā)現(xiàn)總有兩個(gè)人取的球相同，由此可知，參加取球的至少有多少人？分析：取兩個(gè)球，顏色搭配有15種可能。15個(gè)抽屜，本題中物品即為取球的人。物品數(shù)至少為15+1=16個(gè)?！镜谝怀閷显怼浚喝绻麑個(gè)物件放入n個(gè)抽屜內(nèi)，那么必有一個(gè)抽屜內(nèi)至少有［午1卜1個(gè)物件?！就茝V】：如果將m+m+ +m+1（均為正整數(shù)）個(gè)物件放入n個(gè)抽屜內(nèi)，那么或者第一個(gè)抽屜內(nèi)至少有TOC\o"1-5"\h\z1 2 nm+1個(gè)，或者第二個(gè)抽屜內(nèi)至少有m+1個(gè)物件。。。。。。或者第n個(gè)抽屜內(nèi)至少有m+1個(gè)物件。1 2 n【第二抽屜原理】：如果將m個(gè)物件放入n個(gè)抽屜內(nèi)，那么必有一個(gè)抽屜內(nèi)至多有［扌］個(gè)物件?！就茝V】如果將m+m++m-1（均為正整數(shù)）個(gè)物件放入n個(gè)抽屜內(nèi)，那么或者第一個(gè)抽屜內(nèi)至多有m-11 2 n 1個(gè)，或者第二個(gè)抽屜內(nèi)至多有m-1個(gè)物件oooooo或者第n個(gè)抽屜內(nèi)至多有m-1個(gè)物件。2n例9：已知A與B是集合｛1,2,3?。。100｝的兩個(gè)子集，滿(mǎn)足：A與B的元素個(gè)數(shù)相同，且A與B的交集為空集，若neA時(shí)總有2n+2gB，則集合A^B的元素個(gè)數(shù)最多為（）A、62 B、66 C、68 D、74六、極端原理：直接抓住全體對(duì)象中的極端情形或它們所具有的某種極端性質(zhì)加以研究、解決問(wèn)題的思想方法稱(chēng)為極端性原則。1．最小數(shù)原理、最大數(shù)原理命題一有限個(gè)實(shí)數(shù)中，必有一個(gè)最小數(shù)（也必有一個(gè)最大數(shù)）．命題二任意有限個(gè)兩兩不同的實(shí)數(shù)可以從小到大排列順序．上述兩個(gè)命題對(duì)無(wú)窮多個(gè)實(shí)數(shù)可能不成立，例如對(duì)于集合｛2—nln^N｝，其中就沒(méi)有最小的數(shù).對(duì)于自然數(shù)集，有最小數(shù)原理若M是自然數(shù)集N的任一非空子集（有限或無(wú)限均可），則M中必有最小的數(shù).2.最短長(zhǎng)度原理最短長(zhǎng)度原理1：任意給定兩點(diǎn)，所有連接這兩點(diǎn)的線(xiàn)中，以直線(xiàn)段的長(zhǎng)度為最短；最短長(zhǎng)度原理2：在連接一已知點(diǎn)和已知直線(xiàn)或已知平面的點(diǎn)的所有線(xiàn)中，以垂線(xiàn)段的長(zhǎng)度為最短。七、離散最值在國(guó)內(nèi)外數(shù)學(xué)競(jìng)賽中，常出現(xiàn)一些在自然數(shù)范圍內(nèi)變化的量的最值問(wèn)題，我們稱(chēng)之為離散最值問(wèn)題。解決這類(lèi)非常規(guī)問(wèn)題，尚無(wú)統(tǒng)一的方法，對(duì)不同的題目要用不同的策略和方法，就具體的題目而言，大致可從以下幾個(gè)方面著手：1?著眼于極端情形；2?分析推理——確定最值；3?枚舉比較——確定最值例10：一把鑰匙只能開(kāi)一把鎖，現(xiàn)在有4把鑰匙4把鎖，但不知哪把鑰匙開(kāi)哪把鎖，最少試多少次，就一定能使全部的鑰匙和鎖相匹配？解：開(kāi)第1把鎖，若不湊巧，試3把鑰匙還沒(méi)有成功，則第4把不用再試了，它一定能打開(kāi)這把鎖。同理，開(kāi)第2把鎖最多試2次，開(kāi)第3把鎖最多試1次，最后剩下的1把鑰匙一定能打開(kāi)剩下的第4把鎖，而用不著再試。這樣最多要試的次數(shù)為3＋2＋1=6（次）。說(shuō)明：在“最湊巧”的情況下，只需試3次就可使全部的鑰匙和鎖相匹配。本題中要求滿(mǎn)足任何情況，所以應(yīng)從“最不湊巧”的情況考慮問(wèn)題。例11：一個(gè)布袋中有紅、黃、綠三種顏色的小球各10個(gè)，這些小球的大小均相同，紅色小球上標(biāo)有數(shù)字“4”，黃色小球上標(biāo)有數(shù)字“5”，綠色小球上標(biāo)有數(shù)字“6”。小明從袋中摸出8個(gè)球，它們的數(shù)字和是39，其中最多可能有多少個(gè)球是紅色的？解：假設(shè)摸出的8個(gè)球全是紅球，則數(shù)字之和為（4X8=）32,與實(shí)際的和39相差7,這是因?yàn)閷⒚龅狞S球、綠球都當(dāng)成是紅球的緣故。用一個(gè)綠球換一個(gè)紅球，數(shù)字和可增加（6－4=）2，用一個(gè)黃球換一個(gè)紅球，數(shù)字和可增加（5-4=）1。為了使紅球盡可能地多，應(yīng)該多用綠球換紅球，現(xiàn)在7一2=3,,,,1,因此可用3個(gè)綠球換紅球，再用一個(gè)黃球換紅球，這樣8個(gè)球的數(shù)字之和正好等于39。所以要使8個(gè)球的數(shù)字之和為39，其中最多可能有（8-3-1=）4個(gè)是紅球。覆蓋1?最簡(jiǎn)單情形一一用一個(gè)圓覆蓋一個(gè)圖形?首先根據(jù)覆蓋和圓的定義及性質(zhì)即可得到：定理1如果能在圖形F所在平面上找到一點(diǎn)O,使得圖形F中的每一點(diǎn)與O的距離都不大于定長(zhǎng)r,貝IJF可被