組合數(shù)學(xué)在數(shù)學(xué)競(jìng)賽中的應(yīng)用-畢業(yè)論文

目錄1.引言 12組合數(shù)學(xué)與數(shù)學(xué)競(jìng)賽簡(jiǎn)介. 12.1組合數(shù)學(xué) 12.2數(shù)學(xué)競(jìng)賽 13組合數(shù)學(xué)的幾種方法在數(shù)學(xué)競(jìng)賽中的應(yīng)用 23.1抽屜原理 23.2容斥原理 23.3排列組合 84.探索高中數(shù)學(xué)競(jìng)賽中的組合問(wèn)題 104.1熟練掌握四個(gè)基本的技術(shù)原理 104.2學(xué)習(xí)組合數(shù)學(xué)的幾點(diǎn)建議 104.3培養(yǎng)學(xué)生的組合性思維和組合思想 114.4常見排列組合的解題策略 11參考文獻(xiàn) 12致謝 12組合數(shù)學(xué)在數(shù)學(xué)競(jìng)賽中的應(yīng)用CombinatorialMathematicsinAppliedMathematics(0521110329Class2Grade2005Mathematics&AppliedMathematicsSchoolofMathematics&Information)Abstract:Mathematicalcompetitionsinhighschoolandjuniorhighschoolareverypopularinwhichtheportfolioproblemaccountsforalargeproportion.Asforthisissue,thewritercombineswiththeportfoliomathematicsandcompetitivemathematicsinuniversity,andadoptsthedrawerprinciple,exclusionprincipleandpermutationandcombinationmethodstomaketheresearchanddiscussion.Importantly,thewritercarriesnewresearchontheproblemsofcombinationinmathematicalcompetition.Keywords:order;combination;drawerprinciple;Exclusionprinciple1.引言組合數(shù)學(xué)是可以追溯到公元前2200既古老而又年輕的數(shù)學(xué)分支,它的源泉可以追溯到公元前2200年的大禹時(shí)期，中外歷史上許多著名的數(shù)字游戲是它古典部分的主要內(nèi)容.公元1666年，德國(guó)著名數(shù)學(xué)家萊布尼茨為它請(qǐng)名為“組合學(xué)”(Combinatorics),并預(yù)言了這一數(shù)學(xué)分支的誕生.隨著科學(xué)技術(shù)的發(fā)展，組合數(shù)學(xué)這門歷史悠久的學(xué)科得到了迅速發(fā)展．?dāng)?shù)學(xué)活動(dòng)離不開解題，掌握數(shù)學(xué)的一個(gè)重要標(biāo)志就是善于解題．現(xiàn)在專門以中學(xué)生為對(duì)象的數(shù)學(xué)競(jìng)賽成為時(shí)代的時(shí)尚，本論文希望結(jié)合組合數(shù)學(xué)和數(shù)學(xué)競(jìng)賽有關(guān)理論知識(shí)，針對(duì)在數(shù)學(xué)競(jìng)賽中占很大比例的組合問(wèn)題，利用大學(xué)組合數(shù)學(xué)理論給出解釋，并結(jié)合初等數(shù)學(xué)向?qū)W生滲透和合理講解．在此過(guò)程中，提出自己直接的見解和總結(jié)．2.組合數(shù)學(xué)與數(shù)學(xué)競(jìng)賽簡(jiǎn)介2.1組合數(shù)學(xué)組合數(shù)學(xué)歷史悠久，幾千年前，我國(guó)的《河圖》、《洛書》就已涉及一些簡(jiǎn)單有趣的組合問(wèn)題．組合問(wèn)題在日常生活中也隨處可見．例如，在玩撲克牌游戲中計(jì)算“同花順”的概率、一筆畫和幻方等都是組合數(shù)學(xué)問(wèn)題．組合數(shù)學(xué)自20世紀(jì)60年代急速發(fā)展的部分原因在于計(jì)算機(jī)在我們的生活中所發(fā)揮的重要影響，而且這種影響還在繼續(xù)發(fā)揮．由于遠(yuǎn)算速度的持續(xù)增加，計(jì)算機(jī)已經(jīng)能夠解決大型問(wèn)題，這在以前是不可能做到的．近年來(lái)，由于計(jì)算機(jī)科學(xué)、編碼理論、規(guī)劃論、數(shù)字通訊、試驗(yàn)設(shè)計(jì)、社會(huì)科學(xué)、生物科學(xué)等學(xué)科的迅猛發(fā)展，大大促進(jìn)了組合數(shù)學(xué)的研究，使這一古老的數(shù)學(xué)分支成為了一門充滿活力的數(shù)學(xué)學(xué)科．組合數(shù)學(xué)可以一般地描述為：組合數(shù)學(xué)是研究離散結(jié)構(gòu)的存在、計(jì)數(shù)、分析和優(yōu)化等問(wèn)題的一門學(xué)科．現(xiàn)代的組合數(shù)學(xué)幾乎是與圖論不可分割的．圖論是數(shù)學(xué)的一個(gè)分支，它以圖為研究對(duì)象，研究頂點(diǎn)和邊組成的圖形的數(shù)學(xué)理論和方法．有關(guān)圖論的第一篇文章是由著名瑞士學(xué)家歐拉寫于1736年，他探討的是著名的哥尼斯堡七橋問(wèn)題，圖論在智力難題和游戲方面有著歷史根源，而今天它為許多學(xué)科的研究提供了一種非常重要的語(yǔ)言和框架．2.2數(shù)學(xué)競(jìng)賽圍繞著數(shù)學(xué)競(jìng)賽而開展的各種活動(dòng)已經(jīng)搭起了一個(gè)數(shù)學(xué)教育新分支的框架，其特點(diǎn)是以開發(fā)智力為根本目的、以問(wèn)題解決為基本形式、以競(jìng)賽數(shù)學(xué)為主要內(nèi)容．最本質(zhì)的是對(duì)中學(xué)生進(jìn)行“競(jìng)賽數(shù)學(xué)”的教育，這種教育的性質(zhì)是：較高層次的基礎(chǔ)教育、開發(fā)智力的素質(zhì)教育、生動(dòng)活潑的業(yè)余教育、現(xiàn)代教學(xué)的普及教育．競(jìng)賽數(shù)學(xué)是一中“中間數(shù)學(xué)”，介乎于中小學(xué)與大學(xué)數(shù)學(xué)之間；競(jìng)賽數(shù)學(xué)是一種“前沿?cái)?shù)學(xué)”，追求內(nèi)容的新穎性，不斷推陳出新，時(shí)刻涌現(xiàn)出新問(wèn)題新方法和新結(jié)果；競(jìng)賽數(shù)學(xué)是一種“藝術(shù)數(shù)學(xué)”，它把現(xiàn)代化的內(nèi)容與趣味性的問(wèn)題有機(jī)結(jié)合，把普遍性的問(wèn)題與獨(dú)創(chuàng)性的技巧有機(jī)結(jié)合，展示出數(shù)學(xué)美的魅力；競(jìng)賽數(shù)學(xué)是一種“教育數(shù)學(xué)”，它稱為教育數(shù)學(xué)中最接近研究數(shù)學(xué)的“先頭部隊(duì)”，利用自己所處的地位，大量地、方便地吸收著前沿成果初等化，也把古典問(wèn)題高等化．3.組合數(shù)學(xué)的幾種方法在數(shù)學(xué)競(jìng)賽中的應(yīng)用3.1抽屜原理抽屜原理又稱鴿巢原理或重疊原理，是組合數(shù)學(xué)的兩大基本原理之一，是一個(gè)極其初等而又應(yīng)用較廣的數(shù)學(xué)原理．抽屜原理要解決的是存在性問(wèn)題，即在具體的組合問(wèn)題中，要解決某些特定問(wèn)題求解的方案數(shù)，其前提就是要知道這些方案的存在性．定理3.1.1（基本形式）將SKIPIF1<0個(gè)物品放入SKIPIF1<0個(gè)抽屜，則至少有一個(gè)抽屜中的物品數(shù)不少于兩個(gè)．證反證之．將抽屜編號(hào)為：SKIPIF1<0，設(shè)第SKIPIF1<0個(gè)抽屜放有SKIPIF1<0個(gè)物品，則SKIPIF1<0但若定理結(jié)論不成立，即SKIPIF1<0，亦有SKIPIF1<0，從而有SKIPIF1<0矛盾．定理3.1.2（推廣形式）將SKIPIF1<0個(gè)物品放入SKIPIF1<0個(gè)抽屜，則下列事件至少有一個(gè)成立：即第SKIPIF1<0個(gè)抽屜的物品數(shù)不少于SKIPIF1<0個(gè)，SKIPIF1<0．證反證．不然，設(shè)第SKIPIF1<0個(gè)抽屜的物品數(shù)小于SKIPIF1<0（即該抽屜最多有SKIPIF1<0個(gè)物品），則有SKIPIF1<0物品總數(shù)SKIPIF1<0與假設(shè)矛盾．根據(jù)定理的結(jié)果，不難得出下述結(jié)論．推論3.1.1將SKIPIF1<0個(gè)物品放入SKIPIF1<0個(gè)抽屜，則至少有一個(gè)抽屜中的物品個(gè)數(shù)不少于SKIPIF1<0個(gè)．推論3.1.2將SKIPIF1<0個(gè)物品放入SKIPIF1<0個(gè)抽屜，則至少有一個(gè)抽屜中的物品個(gè)數(shù)不少于SKIPIF1<0個(gè)．其中SKIPIF1<0表示取正數(shù)SKIPIF1<0的整數(shù)部分，SKIPIF1<0表示不小于SKIPIF1<0的最小整數(shù)．推論3.1.3若SKIPIF1<0個(gè)正整數(shù)SKIPIF1<0滿足SKIPIF1<0則至少有一個(gè)SKIPIF1<0，滿足SKIPIF1<0．利用抽屜原理可以得到下面兩個(gè)性質(zhì)：性質(zhì)1任意三個(gè)整數(shù)中，必有兩個(gè)整數(shù)的和是2的倍數(shù)．性質(zhì)2任意五個(gè)整數(shù)中，必有三個(gè)整數(shù)的和是3的倍數(shù)．例1任意15個(gè)整數(shù)中，必有8個(gè)整數(shù)的和是8的倍數(shù)．證SKIPIF1<0個(gè)整數(shù)是任意的，所以我們用SKIPIF1<0這15個(gè)字母來(lái)表示，有性質(zhì)1，SKIPIF1<0中SKIPIF1<0（a為整數(shù)），同理可得，SKIPIF1<0中有SKIPIF1<0（b為整數(shù)），SKIPIF1<0中SKIPIF1<0（c為整數(shù)），SKIPIF1<0中SKIPIF1<0（d為整數(shù)）。有性質(zhì)1得SKIPIF1<0（m為整數(shù)）SKIPIF1<0（n為整數(shù)），SKIPIF1<0中SKIPIF1<0（e為整數(shù)）SKIPIF1<0．證畢例2任意三個(gè)整數(shù)，必有兩個(gè)之和為偶數(shù)（其差也為偶數(shù)）．證制造兩個(gè)抽屜：“奇數(shù)”和“偶數(shù)”，3個(gè)數(shù)放入兩個(gè)抽屜，必有一個(gè)抽屜中至少有兩個(gè)數(shù)．有整數(shù)求和的奇、偶性質(zhì)，即知此二數(shù)之和比為偶數(shù)．同理可知，二者之差也為偶數(shù)．例3某俱樂(lè)部有SKIPIF1<0名成員．對(duì)每一個(gè)人，其余的人中恰好有SKIPIF1<0個(gè)愿與他打網(wǎng)球，SKIPIF1<0個(gè)愿與他下象棋，SKIPIF1<0個(gè)愿與他打乒乓球．證明該俱樂(lè)部至少有3個(gè)人，他們之間玩的游戲三種俱全．證將每個(gè)人作為平面上的一個(gè)點(diǎn)，且任何三點(diǎn)不共線．由每一點(diǎn)引出SKIPIF1<0條紅邊、SKIPIF1<0條藍(lán)邊、SKIPIF1<0條黑邊，分別代表打網(wǎng)球、下象棋及打乒乓球．問(wèn)題等價(jià)于要證明圖中至少有一個(gè)三邊顏色全部相同的三角形．考慮有這個(gè)SKIPIF1<0點(diǎn)的所有連邊構(gòu)成的異色角（即兩條異色的邊所構(gòu)成的角）的總數(shù)．每個(gè)頂點(diǎn)處有SKIPIF1<0個(gè)異色角，所以SKIPIF1<0平均每個(gè)三角形有SKIPIF1<0個(gè)異色角．因此，至少有一個(gè)三角形有3個(gè)異色角，那么，這個(gè)三角形的三條邊當(dāng)然互不同色．證畢．例4設(shè)SKIPIF1<0為一等邊三角形，SKIPIF1<0是三邊上點(diǎn)的全體．對(duì)于每一個(gè)把SKIPIF1<0分成兩個(gè)不交子集的劃分，問(wèn)這兩個(gè)子集中是否至少有一個(gè)子集包含著一個(gè)直角三角形的三個(gè)頂點(diǎn)證如下圖，在邊SKIPIF1<0上分別取三點(diǎn)P、Q、R，顯然△ARQ，△BPR，△CQP都是直角三角形．它們的銳角是30°及60°．設(shè)E1，E2是E的兩個(gè)非空子集，且SKIPIF1<0由抽屜原則P、Q、R中至少有兩點(diǎn)屬于同一子集，不妨設(shè)P、Q∈E1．如果BC邊上除P之外還有屬于E1的點(diǎn)，那么結(jié)論已證明．設(shè)BC的點(diǎn)除P之外全屬于E2，那么只要AB上有異于B的點(diǎn)S屬于E2，設(shè)S在BC上的投影點(diǎn)為S′，則△SS′B為直角三角形．再設(shè)AB內(nèi)的每一點(diǎn)均不屬于E2，即除B之外全屬于E1，特別，R、A∈E1，于是A、Q、R∈E1，且AQR為一直角三角形，從而命題得證．【評(píng)述】此例通過(guò)分割圖形構(gòu)造抽屜．在一個(gè)幾何圖形內(nèi)有若干已知點(diǎn)，我們可以根據(jù)問(wèn)題的要求把圖形進(jìn)行適當(dāng)?shù)姆指?，用這些分割成的圖形作為抽屜，再對(duì)已知點(diǎn)進(jìn)行分類，集中對(duì)某一個(gè)或幾個(gè)抽屜進(jìn)行討論，使問(wèn)題得到解決．例5：在SKIPIF1<0中任選出20個(gè)數(shù)，其中至少有不同的兩組數(shù)，和都等于104，試證明之．（第39屆美國(guó)普特南數(shù)學(xué)競(jìng)賽題）證給定的數(shù)共有34個(gè)，其相鄰兩數(shù)的差均為3，我們把這些數(shù)分成如下18個(gè)不相交的集合．SKIPIF1<0．且把它們分作是18個(gè)抽屜，從已知的34個(gè)數(shù)中任取20個(gè)數(shù)，即把前面兩個(gè)抽屜中的數(shù)1和52都取出，則剩下的18個(gè)數(shù)在后面的16個(gè)抽屜中至少有不同的兩個(gè)抽屜中的數(shù)全被取出，這兩個(gè)抽屜中的數(shù)互不相同，每個(gè)抽屜中的兩個(gè)數(shù)的和都是104．【評(píng)述】此例是根據(jù)某兩個(gè)數(shù)的和為104來(lái)構(gòu)造抽屜．一般地，與整數(shù)集有關(guān)的存在性問(wèn)題也可根據(jù)不同的需要利用整數(shù)間的倍數(shù)關(guān)系、同余關(guān)系來(lái)適當(dāng)分組而構(gòu)成抽屜．小結(jié)：用抽屜原則解題的本質(zhì)是把所要討論的問(wèn)題利用抽屜原則縮小范圍，使之在一個(gè)特定的小范圍內(nèi)考慮問(wèn)題，從而使問(wèn)題變得簡(jiǎn)單明確． 用抽屜原則解題的基本思想是根據(jù)問(wèn)題的自身特點(diǎn)和本質(zhì)，弄清對(duì)哪些元素進(jìn)行分類，找出分類的規(guī)律． 用抽屜原則解題的基本思想是根據(jù)問(wèn)題的自身特點(diǎn)和本質(zhì)，找出分類的規(guī)律． 用抽屜原則解題的關(guān)鍵是利用題目中的條件構(gòu)造出與題設(shè)相關(guān)的“抽屜”．3.2容斥原理當(dāng)我們?cè)噲D對(duì)某些對(duì)象的數(shù)目從整體上計(jì)數(shù)碰到困難時(shí)，考慮將整體分解為部分，通過(guò)對(duì)每個(gè)部分的計(jì)數(shù)來(lái)實(shí)現(xiàn)對(duì)整體的計(jì)數(shù)是一種明智的選擇．將整體分解為部分也就是將有限集X表示成它的一組兩兩互異的非空真子集A1，A2，…An的并集，即SKIPIF1<0叫做集合X的一個(gè)覆蓋。一個(gè)特殊情況是，集族SKIPIF1<0中的任意兩個(gè)集合都不相交，這時(shí)我們稱集族SKIPIF1<0為集合X的一個(gè)（完全）劃分．如SKIPIF1<0為集合X的劃分，則對(duì)集合X的計(jì)數(shù)可通過(guò)熟知的加法公式 SKIPIF1<0①進(jìn)行，但是，要找到一個(gè)劃分并且其中所有子集易于計(jì)數(shù)的有時(shí)并非易事．我們可以考慮通過(guò)對(duì)任意的集族中的子集的計(jì)數(shù)來(lái)計(jì)算|X|，當(dāng)集族SKIPIF1<0中至少存在兩個(gè)集合的交非空時(shí)，我們稱這個(gè)覆蓋為集合X的不完全劃分．對(duì)于集合X的不完全劃分，顯然有有SKIPIF1<0②因?yàn)樵谟?jì)算|Ai|時(shí)出現(xiàn)了對(duì)某些元素的重復(fù)計(jì)數(shù)，為了計(jì)算|X|，就得將②式右邊重復(fù)計(jì)算的部分減去，如果減得超出了，還得再加上，也就是說(shuō)我們要做“多退少補(bǔ)”的工作．完成這項(xiàng)工作的準(zhǔn)則就是容斥原理，是十九世紀(jì)英國(guó)數(shù)學(xué)家西爾維斯提出的．容斥原理有兩個(gè)公式．1、容斥公式定理1設(shè)SKIPIF1<0 SKIPIF1<0③證明：當(dāng)SKIPIF1<0由加法公式有 SKIPIF1<0結(jié)論成立．若n=k時(shí)結(jié)論成立，則由 SKIPIF1<0SKIPIF1<0SKIPIF1<0知，SKIPIF1<0時(shí)結(jié)論成立．由歸納原理知，對(duì)任意自然數(shù)n，公式③成立．公式③稱為容斥公式，顯然它是公式①的推廣． 如果將SKIPIF1<0看成具有性質(zhì)SKIPIF1<0的元素的集合，那么SKIPIF1<0就是至少具有n個(gè)性質(zhì)SKIPIF1<0之一的元素的集合．因此，容斥公式常用來(lái)計(jì)算至少具有某幾個(gè)性質(zhì)之一的元素的數(shù)目．容斥原理用法總結(jié)：在應(yīng)用容斥原理求解計(jì)數(shù)問(wèn)題時(shí)，可按下列步驟進(jìn)行：（1）根據(jù)問(wèn)題的實(shí)際情況，構(gòu)造一個(gè)有限集SKIPIF1<0和一個(gè)性質(zhì)集SKIPIF1<0，SKIPIF1<0是SKIPIF1<0中具有性質(zhì)SKIPIF1<0的所有元素的子集，問(wèn)題的關(guān)鍵是構(gòu)造的性質(zhì)集SKIPIF1<0，要使得SKIPIF1<0容易計(jì)算出來(lái)SKIPIF1<0．（2）當(dāng)統(tǒng)計(jì)SKIPIF1<0中恰好具有SKIPIF1<0種特征的元素的個(gè)數(shù)時(shí)，將問(wèn)題轉(zhuǎn)化為求SKIPIF1<0中恰好具有SKIPIF1<0種SKIPIF1<0個(gè)性質(zhì)的元素個(gè)數(shù)SKIPIF1<0，可利用逐步淘汰原理或一般公式．（3）當(dāng)統(tǒng)計(jì)SKIPIF1<0中至少有SKIPIF1<0中一種性質(zhì)的元素個(gè)數(shù)SKIPIF1<0時(shí)，利用容斥原理，或由SKIPIF1<0求得．（4）注意SKIPIF1<0，故可由此求得SKIPIF1<0中至少具有SKIPIF1<0種特征的元素個(gè)數(shù)SKIPIF1<0如SKIPIF1<0時(shí)，有SKIPIF1<0．2．篩法公式與容斥公式討論的計(jì)數(shù)問(wèn)題相反，有時(shí)需要計(jì)算不具有某幾個(gè)性質(zhì)中的任何一個(gè)性質(zhì)的元素的個(gè)數(shù)，為此，我們先引入下面的引理．引理1設(shè)A關(guān)于全集I的補(bǔ)集為SKIPIF1<0，則SKIPIF1<0每個(gè)元素引理2SKIPIF1<0SKIPIF1<0引理簡(jiǎn)單證略．利用二引理改寫公式③便是定理2設(shè)SKIPIF1<0為有限集I的子集，則SKIPIF1<0SKIPIF1<03.錯(cuò)排問(wèn)題利用容斥原理可以輕而易舉地得出同一個(gè)公式．SKIPIF1<0個(gè)元素依次給以標(biāo)號(hào)SKIPIF1<0,SKIPIF1<0個(gè)元素的全排列中，求每個(gè)元素都不在原來(lái)自己位置上的排列數(shù)．設(shè)SKIPIF1<0為數(shù)SKIPIF1<0在第SKIPIF1<0位上的全體排列，SKIPIF1<0．因數(shù)字SKIPIF1<0不動(dòng),故SKIPIF1<0同理SKIPIF1<0．每個(gè)元素都不在原來(lái)位置上的排列數(shù)為SKIPIF1<0例1數(shù)SKIPIF1<0的全排列中，求偶數(shù)在原來(lái)位置上，其余都不在原來(lái)位置上的錯(cuò)排列數(shù)目，實(shí)際上是SKIPIF1<0五個(gè)數(shù)的錯(cuò)排問(wèn)題，總數(shù)為SKIPIF1<0．例2某校六年級(jí)二班有49人參加了數(shù)學(xué)、英語(yǔ)、語(yǔ)文學(xué)習(xí)小組，其中數(shù)學(xué)有30人參加，英語(yǔ)有20人參加，語(yǔ)文小組有10人．老師告訴同學(xué)既參加數(shù)學(xué)小組又參加語(yǔ)文小組的有3人，既參加數(shù)學(xué)又參加英語(yǔ)和既參加英語(yǔ)又參加語(yǔ)文的人數(shù)均為質(zhì)數(shù)，而三種全參加的只有1人，求既參加英語(yǔ)又參加數(shù)學(xué)小組的人數(shù)．分析與解：根據(jù)已知條件畫出圖．SKIPIF1<0三圓蓋住的總體為49人，假設(shè)既參加數(shù)學(xué)又參加英語(yǔ)的有x人，既參加語(yǔ)文又參加英語(yǔ)的有y人，可以列出這樣的方程：SKIPIF1<0整理后得：SKIPIF1<0由于x、y均為質(zhì)數(shù)，因而這兩個(gè)質(zhì)數(shù)中必有一個(gè)偶質(zhì)數(shù)2，另一個(gè)質(zhì)數(shù)為7．例3求1到100的自然數(shù)中，所有既不是2的倍數(shù)又不是3的倍數(shù)的整數(shù)之和S．解：1到100的自然數(shù)中，所有自然數(shù)的和是：SKIPIF1<01到100的自然數(shù)中，所有2的倍數(shù)的自然數(shù)和是：SKIPIF1<01到100的自然數(shù)中，所有3的倍數(shù)的自然數(shù)和是：SKIPIF1<01到100的自然數(shù)中，所有既是2的倍數(shù)又是3的倍數(shù)，即是6的倍數(shù)的自然數(shù)和是：SKIPIF1<0所以，1到100的自然數(shù)中，所有既不是2的倍數(shù)又不是3的倍數(shù)的整數(shù)之和SKIPIF1<03.3排列組合定義一（排列Permutation）設(shè)SKIPIF1<0元集SKIPIF1<0，從SKIPIF1<0中取出SKIPIF1<0個(gè)不同元素按次序排列，稱為SKIPIF1<0的一個(gè)SKIPIF1<0排列，其個(gè)數(shù)稱為SKIPIF1<0排列數(shù)，記作SKIPIF1<0或SKIPIF1<0．當(dāng)SKIPIF1<0時(shí)．SKIPIF1<0的SKIPIF1<0排列又稱為SKIPIF1<0的全排列，其個(gè)數(shù)SKIPIF1<0又稱全排列數(shù)．命題1SKIPIF1<0．證明SKIPIF1<0的一個(gè)SKIPIF1<0排列由SKIPIF1<0個(gè)不同的元素組成，其中第一位有SKIPIF1<0種可能．第二位有SKIPIF1<0種可能；·······第SKIPIF1<0位有SKIPIF1<0種可能。由乘法原理,SKIPIF1<0元集SKIPIF1<0的不同排列數(shù)為SKIPIF1<0推論SKIPIF1<0例1從SKIPIF1<0中任取兩個(gè)不同的字母構(gòu)成的字共有SKIPIF1<0個(gè)．羅列如下：SKIPIF1<0定義2（組合Combination）設(shè)SKIPIF1<0元集SKIPIF1<0，從SKIPIF1<0中取出SKIPIF1<0個(gè)不同元素構(gòu)成一組，稱為SKIPIF1<0的一個(gè)SKIPIF1<0組合，其個(gè)數(shù)稱為SKIPIF1<0組合數(shù)，記作SKIPIF1<0，或SKIPIF1<0．命題2有SKIPIF1<0個(gè)不同的元素共可構(gòu)成SKIPIF1<0種組合，即SKIPIF1<0．證明由定義SKIPIF1<0組合與SKIPIF1<0排列的區(qū)別在于前者不計(jì)較元素的先后順序，因此由每個(gè)SKIPIF1<0組合可以作出SKIPIF1<0個(gè)不同的SKIPIF1<0排列．于是若有SKIPIF1<0種SKIPIF1<0組合，則有SKIPIF1<0種排列，因此SKIPIF1<0．推論1任意SKIPIF1<0個(gè)相繼的正整數(shù)之積可被SKIPIF1<0整除形成多少條，即有SKIPIF1<0．推論2SKIPIF1<0．推論3SKIPIF1<0．推論4SKIPIF1<0元集SKIPIF1<0的SKIPIF1<0元子集的個(gè)數(shù)等于SKIPIF1<0．推論5設(shè)SKIPIF1<0元集SKIPIF1<0，其字典序如下標(biāo)所示，則從SKIPIF1<0中每次取出滿足條件SKIPIF1<0的SKIPIF1<0個(gè)元的方式數(shù)等于SKIPIF1<0．證明SKIPIF1<0的任一組合都可調(diào)整為SKIPIF1<0并使其滿足SKIPIF1<0；另一方面，任一滿足條件SKIPIF1<0的SKIPIF1<0個(gè)元都是SKIPIF1<0的一個(gè)SKIPIF1<0組合．例2平面上任三點(diǎn)都不共線的25個(gè)點(diǎn)，可形成多少條直線？可形成多少個(gè)三角形？解25點(diǎn)中任取2點(diǎn)即可惟一確定一條直線，故可形成SKIPIF1<0條直線；同理，任取3點(diǎn)即可惟一確定一個(gè)三角形，故三角形的數(shù)目等于SKIPIF1<0．例3把SKIPIF1<0個(gè)有標(biāo)號(hào)的珠子排成一個(gè)圓圈，共有多少種不同的排法？解這是典型的圓排列問(wèn)題對(duì)于圍成圓圈的SKIPIF1<0個(gè)元素，同時(shí)按同一方向旋轉(zhuǎn)，即每個(gè)元素都向左（或向右）轉(zhuǎn)動(dòng)一個(gè)位置，雖然元素的絕對(duì)位置發(fā)生了變化．但相對(duì)位置未變，即元素之間的相鄰關(guān)系未變，這樣的圓排列認(rèn)為是同一種，否則便是不同的圓排列．下面從兩種角度推導(dǎo)圓排列數(shù)的計(jì)算公式．方法一：先令SKIPIF1<0個(gè)相異元素任意排成一行（稱為線排列），共有種SKIPIF1<0排法，再將其首位相接圍成一個(gè)圓，當(dāng)圓轉(zhuǎn)動(dòng)一個(gè)角度時(shí)，對(duì)應(yīng)另一個(gè)線排列，當(dāng)每個(gè)元素又轉(zhuǎn)回到原先的位置時(shí)，相當(dāng)于SKIPIF1<0個(gè)不同的線排列，故圓排列數(shù)為SKIPIF1<0.方法二：先取出某一元素SKIPIF1<0，放于圓上某確定位置，再另余下的SKIPIF1<0個(gè)元素作為一個(gè)線排列，首尾置于SKIPIF1<0的兩側(cè)構(gòu)成一個(gè)圓排列同樣可得到SKIPIF1<0.4.探究高中數(shù)學(xué)競(jìng)賽中的組合問(wèn)題4.1掌握四個(gè)基本的計(jì)數(shù)原理4.1.1加法原理設(shè)SKIPIF1<0集合劃分為部分SKIPIF1<0．則SKIPIF1<0的元素個(gè)數(shù)可以通過(guò)找出它的每一個(gè)部分的元素的個(gè)數(shù)來(lái)確定，我們把這些數(shù)相加，得到SKIPIF1<0如果集合SKIPIF1<0可以重疊，我們能夠使用一個(gè)跟深刻的原理來(lái)計(jì)數(shù)SKIPIF1<0中元素的個(gè)數(shù)—容斥原理．4.1.2乘法原理令SKIPIF1<0是元素的序偶SKIPIF1<0的集合，其中第一個(gè)元素SKIPIF1<0來(lái)自大小為SKIPIF1<0的一個(gè)集合，而對(duì)于SKIPIF1<0的每個(gè)選擇，元素SKIPIF1<0存在著SKIPIF1<0種選擇．于是，SKIPIF1<0的大小為SKIPIF1<0:SKIPIF1<0.4.1.3減法原理令SKIPIF1<0是一個(gè)集合，而是包含SKIPIF1<0的更大的集合．設(shè)SKIPIF1<0是SKIPIF1<0在SKIPIF1<0中的補(bǔ),那么SKIPIF1<0中的元素個(gè)數(shù)SKIPIF1<0有下列法則給出：SKIPIF1<0.4.1.3除法原理令SKIPIF1<0是一個(gè)有限集，它以下述方式被劃分成SKIPIF1<0部分，每一部分SKIPIF1<0包含相同數(shù)目的元素．此時(shí)，劃分中的部分的數(shù)目由下述公式給出．SKIPIF1<0于是，如果我們知道元素個(gè)數(shù)以及各部分所含元素的個(gè)數(shù)相同，則可以確定部分的數(shù)目．4.2學(xué)習(xí)組合數(shù)學(xué)的幾點(diǎn)建議1提倡一題多解,使學(xué)生善于從不同角度思考問(wèn)題,做到思維起點(diǎn)靈活．思維起點(diǎn)靈活,就是能從不同角度、方向、方面思考問(wèn)題,從同一信息源產(chǎn)生多種多樣的聯(lián)想,形成多個(gè)起點(diǎn),用多種方法解決問(wèn)題．一題多解正好適應(yīng)這一要求,因此,加強(qiáng)一題多解的訓(xùn)練是達(dá)到這一目的的有效方法．2剖析解題過(guò)程,使學(xué)生善于克服思維定勢(shì),做到思維過(guò)程靈活．思維過(guò)程靈活,就是要善于從分析到綜合,從綜合到分析,能根據(jù)客觀情況的變化而變化,隨機(jī)應(yīng)變地調(diào)整解題策略．在學(xué)習(xí)中,若知識(shí)和經(jīng)驗(yàn)按著一定的“現(xiàn)成途經(jīng)”反復(fù)認(rèn)識(shí),就容易使思維產(chǎn)生一種先入之見或固定模式,在解題時(shí),只知道按熟悉的規(guī)律、方式、方法來(lái)思考,形成思維定勢(shì)．此時(shí)若碰到形式類同,但本質(zhì)不同的問(wèn)題,往往感到束手無(wú)策,思維顯得比較呆板．競(jìng)賽中的組合問(wèn)題,往往沒(méi)有一個(gè)固定的解題模式,許多題形式上十分相似,而解題過(guò)程卻大不相同,需要根據(jù)具體情況,采取不同的對(duì)策．這些題目正是訓(xùn)練學(xué)生克服呆板性,增強(qiáng)靈活性的極好材料．3鼓勵(lì)大膽聯(lián)想,使學(xué)生善于引申、推廣,做到接受和運(yùn)用知識(shí)靈活．接受和運(yùn)用知識(shí)靈活,就是要提倡發(fā)展學(xué)生的發(fā)散思維,使學(xué)生在面對(duì)一個(gè)問(wèn)題時(shí),能產(chǎn)生各種各樣的聯(lián)想,從而得到各種合理的結(jié)論,或者把許多有關(guān)問(wèn)題聯(lián)系起來(lái)．4強(qiáng)調(diào)新舊知識(shí)的聯(lián)系,使學(xué)生善于形成新的認(rèn)知結(jié)構(gòu),做到概括靈活．概括是一種思維過(guò)程,它包括兩種意義:其一,指