組合數(shù)學(xué)在奧林匹克數(shù)學(xué)中的應(yīng)用

..目錄摘要⑶的8-排列,有因此,S的8-排列的個數(shù)為2.3.2多重集的組合如果S是一個多重集,那么S的一個-組合是S的個元素的一個無序選擇．因此,S的一個-組合本身就是一個多重集——S的一個子多重集．如果S有個元素,那么S只有一個-組合,即S自己．如果S含有種不同類型的元素,那么就存在S的個1-組合．定理令S為具有種類型元素的一個多重集,每種元素均具有無限重復(fù)次數(shù)．則S的-組合的個數(shù)等于證明令S的種類型的元素為,滿足S的任一個-組合均呈的形式,其中皆為非負整數(shù),且．因此,S的-組合的個數(shù)等于方程的解的個數(shù),其中皆為非負整數(shù)．而這些解的個數(shù)等于兩種不同類型元素的多重集的排列的個數(shù)．由定理2.3.1.2可知它等于例1方程的整數(shù)解的個數(shù)是多少？其中．解我們引入新的變量：此時方程變?yōu)槊總€的下界能夠滿足當(dāng)且僅當(dāng)這些是非負的．新方程的非負解的個數(shù)是．3容斥原理容斥原理是由十九世紀英國數(shù)學(xué)家西爾維斯特首先建立的．我們知道加法原理的基礎(chǔ)是分劃．但是,要找到一個分劃且使其中的所有子集都是易于計數(shù)的,有時是困難的,更何況對某些問題也并非一定要這樣去做．我們可以把加法原理加以推廣,即把有限集合分成若干個彼此相容的子集．這時顯然有對于式,在計算時,對某些元素重復(fù)計數(shù)了,為了計算,就得把上式右邊重復(fù)計數(shù)的部分減去,但是如果減得太多了,就應(yīng)設(shè)法加回去．如此,我們應(yīng)做多退少補的工作,而完成這項工作的基本思想就是容斥原理．3.1.容斥原理定理3.1.1設(shè)為有限集S的子集,,則證明：當(dāng)時,設(shè),,,由加法公式有,結(jié)論成立．若時結(jié)論成立,則由知時結(jié)論成立．由歸納原理知,對任意自然數(shù),這個公式都成立．這個公式稱為容斥公式．如果將看成具有性質(zhì)的元素的集合,那么就是至少具有個性質(zhì)之一的元素的集合,因此,容斥公式常用來計算至少具有某幾個性質(zhì)之一的元素的數(shù)目．定理3.1.2設(shè)為有限集S的子集,則這個定理由及,和式容易證明．式與式討論的計數(shù)問題相反,它是用來計算不具有某幾個性質(zhì)中的任何一個性質(zhì)的元素的個數(shù)．3.2錯位排列問題利用容斥原理可以解決這個問題：個元素依次給以標(biāo)號,個元素的全排列中,求每個元素都不在原來自己位置上的排列數(shù)．定理3.2.1設(shè)表示的錯位排列的個數(shù),對于,證明：令是的全部的排列的集合,令表示數(shù)在它的自然位置上的全體排列的集合．那么的錯位排列正是中的那些排列．因此因數(shù)字不動,所以；同理對于的任意2-組合,有；同樣對于滿足的任意整數(shù),；更一般地,對的任意k-組合由于存在的個-組合,應(yīng)用容斥原理得到由此,定理得證．3.3容斥原理在奧林匹克數(shù)學(xué)中的應(yīng)用例1數(shù)的全排列中,求偶數(shù)在原來位置上,其余都不在原來位置上的錯排列數(shù)目．解這道題實際上是五個數(shù)的錯排問題,總數(shù)為例2某校六年級二班有49人參加了數(shù)學(xué)、英語、語文學(xué)習(xí)小組,其中數(shù)學(xué)有30人參加,英語有20人參加,語文小組有10人．老師告訴同學(xué)既參加數(shù)學(xué)小組又參加語文小組的有3人,既參加數(shù)學(xué)又參加英語和既參加英語又參加語文的人數(shù)均為質(zhì)數(shù),而三種全參加的只有1人,求既參加英語又參加數(shù)學(xué)小組的人數(shù)．解：根據(jù)已知條件畫出圖數(shù)學(xué)30質(zhì)20英語 31質(zhì) 10 語文49人假設(shè)既參加數(shù)學(xué)又參加英語的有人,既參加語文又參加英語的有人,可列出這樣的方程：整理后得：由于均為質(zhì)數(shù),因而這兩個質(zhì)數(shù)中必有一個是2,另一個是7．所以既參加英語小組又參加數(shù)學(xué)小組的有2人或7人．例3求從1到1000不能被5,6和8整除的整數(shù)個數(shù)．解：令S為由前1000個正整數(shù)組成的集合,令分別表示S中不能被整除的整數(shù)的集合．另外引入表示的最小公倍數(shù)．則：由于,所以則：．結(jié)束語數(shù)學(xué)奧林匹克中不乏好題,而很多經(jīng)典好題都出自組合中．鴿巢原理是一個非常簡單但又是應(yīng)用廣泛的原理,它是證明存在性問題的有效方法．排列組合和容斥原理都可歸于組合計數(shù)問題,而組合計數(shù)問題綜合性比較強,解題過程充滿著思辨性和解法的多樣性,對運用數(shù)學(xué)思想與方法技巧的要求較高．由于組合體系龐大,本文僅簡單粗略地討論了組合數(shù)學(xué)在奧林匹克數(shù)學(xué)競賽中的應(yīng)用．組合數(shù)學(xué)已經(jīng)積累了大量漂亮的模型、原理、典型方法與技巧．在學(xué)習(xí)組合數(shù)學(xué)的過程中,要善于培養(yǎng)學(xué)生的組合性思維和組合思想,讓學(xué)生在解題中得心應(yīng)手．參考文獻：[1]〔美RichardA.Brualdi著,馮舜璽,羅平,裴偉東譯．組合數(shù)學(xué)[M]．第四版．機械工業(yè)出社；2005．[2]田秋成等編著．組合數(shù)學(xué)[M]．北京：電子工業(yè)出版社．2006．[3]何穎智．淺談抽屜原則[J]．XX科技與經(jīng)濟．1997〔2:22-23．[4]高耀華．組合數(shù)學(xué)的重要原理——抽屜原則[J]．烏魯木齊成人教育學(xué)院學(xué)報．1993〔1:34-36．[5]黃國勛．奧林匹克數(shù)學(xué)方法選講[M]．上海：上海教育出版社．2003．[6]陳傳理,張同君．競賽數(shù)學(xué)教程[M]．北京：高等教育出版社．1996．[7]崔軍．容斥原理及其簡單應(yīng)用[J]．新疆廣