【數(shù)學“多退少補”容斥原理的應用探究6800字（論文）】

數(shù)學“多退少補”容斥原理的應用研究1.緒論 11.1研究背景 11.2研究意義 11.3研究價值 12.容斥原理 22.1基本思想 22.2容斥原理的初等形式 22.3容斥原理的一般形式 33.多退少補原理的應用實例 43.1組合數(shù)學中的多退少補原理 43.2數(shù)論中的多退少補原理 83.3概率論中的多退少補原理 113.4圖論中的多退少補原理 134.結論 14參考文獻 16摘要：“多退少補”原理即容斥原理,它是組合數(shù)學的重要理論，若干個有限集合的交或并是主要研究的計數(shù)問題.運用集合的思想去解決計數(shù)問題，它就是要求某一給定集合的元素數(shù)量，通過使用集合的包含和排除關系以及集合的交集，并集和補集運算來轉換和解決計數(shù)問題.這種解決問題的策略就是容斥原理.但是，我們在劃分集合時很難保證它們兩兩不相交，若按加法原則會將集合中的元素重復計算，這時，我們希望能“多退少補”地對加法原理計算得到的結果進行改正，即重復計數(shù)（多的）部分減去，若減得太多了再補上，直至結果剛好為原集合.這就是容斥原理的基本思想.關鍵詞：容斥原理；多退少補；組合數(shù)學；組合計數(shù)關于“多退少補”原理的應用研究1.緒論1.1研究背景容斥原理又稱“多退少補”原理，是組合數(shù)學中解決計數(shù)問題的重要思想方法，組合數(shù)學又是以數(shù)論、拓撲、代數(shù)、概率論等學科為主要研究對象，以計算機科學和信息科學中的問題為研究背景，以離散結構為主要研究對象的一門學科它，不但具有久遠的歷史，而且又是隨著計算機科學的產(chǎn)生而迅速發(fā)展起來的一個數(shù)學分支，組合數(shù)學的發(fā)展改變了傳統(tǒng)數(shù)學中分析和代數(shù)占統(tǒng)治地位的局面，在基礎數(shù)學研究中具有極其重要的地位，組合數(shù)學不僅在計算機、人工智能、空間技術等學科中有著非常重要的應用，而且在許多與數(shù)學看似關系不大的社會科學中也得到了越來越廣泛的應用，這些都離不開容斥原理[1]郭燕莎.組合算法的研究與實現(xiàn)[D].天津工業(yè)大學碩士論文,2008:3-8.1].[1]郭燕莎.組合算法的研究與實現(xiàn)[D].天津工業(yè)大學碩士論文,2008:3-8.1.2研究意義組合數(shù)學和幾何學將是21世紀數(shù)學研究的前沿領域，然而容斥原理就是其中很重要的原理NOTEREF_Ref72345427\f\h[1].組合算法應用于各個學科的關鍵是運用容斥原理設計出有效的算法，目前對于許多組合理論尚未找到有效的算法，組合數(shù)學的應用依賴于組合算法.迫于中國組合數(shù)學發(fā)展自身的需要，以及中國信息產(chǎn)業(yè)發(fā)展的需要，在中國發(fā)展組合數(shù)學及組合算法己經(jīng)迫在眉睫、刻不容緩，但這還得從容斥原理研究起.1.3研究價值容斥原理是組合數(shù)學中重要的計數(shù)原理.從近幾年國家公職人員招聘考試科目行測考試情況來看，容斥原理問題一向以來都是都是公務員考試科目行測中的高頻考點.對于容斥原理問題絕大多數(shù)考生都摸不著頭腦，不知道該從哪里入手.但是它的應用并不繁瑣或難于明白，其實它所運用的理論知識都是我們生活中經(jīng)常接觸的，這與抽象數(shù)學就形成了直觀的對比.現(xiàn)在，計數(shù)問題基本都用容斥原理解決，如可以解決限制排列和限位圓排列問題等排列問題，數(shù)論中的整除問題、質數(shù)個數(shù)求解問題、歐拉函數(shù)計算公式的推導，染色問題等等.容斥原理在各數(shù)學學科中發(fā)揮著巨大的作用.2.容斥原理2.1基本思想容斥原理是由十九世紀英國數(shù)學家西爾維斯特(J.J.Sylvester)首先建[2]古傳運.容斥原理的推廣極其在奧數(shù)中的應用[J].成都師范學院學報,2014,30(1):118-121..又稱為“多退少補原理”，它是組合數(shù)學中的一個簡單的計數(shù)原則.很自然地，若用集合的觀點去看計數(shù)問題，然后計數(shù)問題就是將集合中特定元素的數(shù)量，通過使用集合的包含和排除關系以及集合的交集、并集和補集運算來轉換和解決計數(shù)問題.這種解決問題的技巧就是容斥原理.所以容斥原理主要解決的就是有限個集合的交或并的計數(shù)問題.[2]古傳運.容斥原理的推廣極其在奧數(shù)中的應用[J].成都師范學院學報,2014,30(1):118-121.我們知道加法原理的基礎是劃分，由加法原理我們得出：若是有限集，，，則有.如果條件不成立，又該如何求呢？此時我們就想到運用容斥原理來解答這一問題.若用加法原則會將中的元素計算重復.這時，我們希望能“多退少補”地對加法原理計算得到的結果進行修正，即重復計數(shù)（多的）部分減去，若減得太多了再補上，直至結果剛好為NOTEREF_Ref72345336\f\h[2].這個解題思想方法稱為容斥原理.2.2容斥原理的簡單情形對于兩個集合,的并集的元素數(shù)量的計數(shù)公式是：.同樣的三個集合,,的并集，也有對應的式子，即.類似的，對于有限集合,，也有：.對于三個有限集合,,，同樣有公式：.2.3容斥原理的一般形式定理1設,,···，是有限集合的子集，，則

定理2設,,···，是有限集合的子集，則定理3設,,···，是有限集合的子集，則定理4設,,···，是有限集合的子集，則在實際應用中，利用容斥原理解題的思想和步驟：(1)根據(jù)問題的實際情況，構造一個有限集合和一個性質集合,是里含有屬性的全部元素構成的子集，但關鍵是我們構造的性質集，要達到，，，容易計算出來的目的.(2)由題意求出，，，.(3)若要計算中具有至少某一個屬性的所有元素的數(shù)量時，則利用定理1求得；若需要計算中沒有具有任意一種屬性的所有元素的數(shù)量時，則利用定理2求得，而且這種逆向思維在計數(shù)問題中是很常見的解題思維方式.3.多退少補原理的應用實例3.1組合數(shù)學中的多退少補原理組合數(shù)學中常見的組合計數(shù)問題我們通常用集合的觀點去研究它，這個方法的關鍵在于對集合的劃分，但在對集合劃分時我們是很難保證它們兩兩沒有交集的，此時容斥原理多退少補這一性質就很好的幫我們解決了這一問題.具體見以下幾個問題.1.錯位排列錯位排列問題在人類發(fā)展史上具有極其重要的歷史地位，人們通常運用遞歸法和多退少補原理來研究它.在1708年，尼古拉·伯努利對這一問題展開過研究，最終用遞歸法得出了公式：錯位排列問題，又稱為“伯努利-歐拉錯裝信封問題”，我們一般把它描述為：小明寫了封信，并且在個信封上寫下了相對應的地址.而他把這封信都裝錯了信封，問一共有多少種裝法？把它用數(shù)學語言表述為：若集合的沒有重復的排列為符合條件，則稱它為集合的錯位排列.大家都用表示集合的錯位排列個數(shù)，簡稱錯排數(shù).它在我們各學科領域被廣泛運用.錯位排列問題我們用遞推關系的方法得到錯排數(shù)：在錯位排列問題中，我們利用多退少補原理同樣可以得到.設表示的沒有重復排列的集合，則數(shù)量為集合的個數(shù).假設是含有屬性的排列，是集合的具有屬性的排列的全體構成的集合，則由多退少補原理得：這樣，我們利用多退少補原理同樣推出了錯排數(shù)的計算公式.例1（1960年—1961年波蘭數(shù)學競賽題）：某人給6個不同的收信人寫了6封信，并且準備了6個寫有收信人地址的信封.問有多少種投放信箋的方法，使每份信箋與信封上的收信地址都不相符[3]夏婧.容斥原理及其應用[[3]夏婧.容斥原理及其應用[J].武漢職業(yè)技術學院學報,2019.4:39-40.解設為所有的裝法構成的集合，則顯然有,我們用1,2,3,4,5,6分別對信和信封編號，記（）為第封信恰好裝進第個信封的所有裝法構成的集合，則為第封信裝不進第個信封的所有裝法構成的集合，即為.由多退少補原理有：，，，所以.故，滿足題意的排列數(shù)共有256種.2.圓排列從個不同元素中取出個元素，按照他們之間的相對位置不分首尾的將他們排成一個圓圈，這種排列方式叫做個不同元素圓排列.圓排列問題的一個典例應用就是“夫妻圍圓桌入座問題”：宴會上，對夫妻圍圓桌入座個座位，要求：男女相間，夫婦不相鄰，問這樣的入座方式有多少種[4]張深林.夫妻排列問題的推廣與證明[J].閩江學院學報,2018,39(5):18-21.？此問題從誕生到現(xiàn)在都被很多的數(shù)學學者所探討.具體如下例.[4]張深林.夫妻排列問題的推廣與證明[J].閩江學院學報,2018,39(5):18-21.例2六對夫婦坐在一個圓桌旁，有多少種排列方式可以使得沒有一個妻子坐在她的丈夫旁邊[5]林永鋼.離散數(shù)學與組合數(shù)學[M].[5]林永鋼.離散數(shù)學與組合數(shù)學[M].北京:清華大學出版社,2007:339-349.解設表示12個人的全排列數(shù)，則，對于，我們令代表第對夫婦坐一起的條件.為了求得，考慮排列11個不同的物品—即，第一對夫婦（作為第一個物品）和其余的10個人.11個不同的物品可以按種不同的方式安排在圓桌上.但是，這里，其中乘以2是因為對于在一起的第一對夫婦，既可以坐在丈夫的左邊又可以坐在丈夫的右邊.同理，對于，.接著，對于，下面計算.這里要排列10個不同的物品—第對夫婦（視為一個物品）和第對夫婦（同樣視為一個物品），以及其余8個人.10個不同的物品的沿圓桌排列有種方式.于是有，因為對于第對夫婦中的妻子有兩種方式與丈夫相鄰，同樣，第對夫婦中的妻子也有兩種方式與丈夫相鄰.類似的可以得到：于是由多退少補原理得沒有一個妻子坐在她的丈夫旁邊的排列個數(shù)為所以，滿足題意的排列數(shù)共有12771840種.多退少補原理不僅僅在關于計數(shù)的問題解決中有廣泛的應用，在許多數(shù)學競賽證明題中將多退少補原理與數(shù)學推理有效地結合起來證明問題，也有很好的效果.3.利用多退少補原理證明數(shù)學競賽問題組合數(shù)學中計數(shù)問題，是歷年來各級數(shù)學競賽命題的熱點之一，同時容斥原理方法是解決數(shù)學競賽中計數(shù)問題的重要工具[6]唐善鋼.容斥原理及在環(huán)形錯排計數(shù)中的應用[J].[6]唐善鋼.容斥原理及在環(huán)形錯排計數(shù)中的應用[J].云南大學學報,2018,40(3):405-414.例1有1990個人參與的活動，每人至少和1327人見過面，證明其中有4個人，他們中每兩人都見過面.（第31屆IMO預選題）證明：設和見過，與見過的人的集合記為,與見過的人的集合記為，則有多退少補原理有，所以從而非空.即存在人.設與見過的人的集合記為，我們有所以非空，即至少有一個人.故，，，，即為所求的滿足兩個人都合作過的思維數(shù)學家.例2在一次文學演講中，有五個文學家打瞌睡，沒有一個文學家剛好睡了兩次，每兩個文學家都在某個時刻一起睡著了.證明一定在某時刻有三個文學家一起睡著[7]周春荔.例談容斥原理證明問題[J].數(shù)學通訊,2002,2:86-87.[7]周春荔.例談容斥原理證明問題[J].數(shù)學通訊,2002,2:86-87.證明設文學家打瞌睡時的集合為.文學家打瞌睡時的集合為.文學家打瞌睡時的集合為.文學家打瞌睡時的集合為.文學家打瞌睡時的集合為.所以，，由于每兩個人都在某一個時刻同時睡著了，即集合中它們兩兩的交集的個數(shù)都大于等于1.如果集合中隨便三個的交集為空集，則隨便四個及五個的交集都是空集，此時有所以矛盾.故，至少有某三個集合的交不是空集，這就表明，一定在某時刻有三個數(shù)學家同時睡著了.以下是可以用多退少補原理證明的數(shù)學競賽題：1.由數(shù)字1，2和3組成位數(shù)，要求位數(shù)中1，2和3的每一個至少出現(xiàn)一次.求所有這種位數(shù)的個數(shù)[8]陳傳理,張同君.競賽數(shù)學教程第二版[M].北京:高等教育出版社[8]陳傳理,張同君.競賽數(shù)學教程第二版[M].北京:高等教育出版社,2005:231-239.通過以上例題我們可以看到，在數(shù)學競賽題中只要是涉及組合計數(shù)問題的題目，一般都是用集合的觀點去認識它，然后運用多退少補原理再加上正確巧妙的推理就能簡潔明了地解決問題.3.2數(shù)論中的多退少補原理數(shù)論就是指研究整數(shù)性質的一門理論.數(shù)論中經(jīng)常遇到關于整除的計數(shù)問題，用其它的方法解決比較復雜、繁瑣.此時我們想到用集合的觀點去研究它，同樣對集合的劃分也是解題的關鍵，但要使集合的子集兩兩互不相交是幾乎不可能的，這時容斥原理的多退少補這一思想方法就幫我們解決了這一難題，從而使問題得到解決.1.數(shù)論中關于整除的計數(shù)問題定理1設都是正整數(shù)，則中能被整除的正整數(shù)的個數(shù)為，其中表示不大于的最大的正整數(shù)[9]周斌.組合數(shù)學的容斥原理與遞歸關系在數(shù)論中的應用研究實例[J].西安文理學院學報，2017,20(4):6-8..[9]周斌.組合數(shù)學的容斥原理與遞歸關系在數(shù)論中的應用研究實例[J].西安文理學院學報，2017,20(4):6-8.對于數(shù)論中關于整除的計數(shù)問題多退少補原理為我們計算提供了很大的方便.具體如下例：例1求不能被2，3或5整除的正整數(shù)的個數(shù)，其中.（第4屆莫斯科數(shù)學競賽題）解令并且.對于，滿足：條件：若能被2整除；條件：若能被3整除；條件：若能被5整除.于是這個問題的答案就是.（有50個正整數(shù)2，4，6，···，96，98能被2整除）（有33個正整數(shù)3，6，9，···，96，99能被3整除）（有20正整數(shù)5，10，···，95，100能被5整除）應用多退少補原理可得：（這26個數(shù)分別是1，7，11，13，17，19，23，29，31，37，41，43，47，49，53，59，61，67，71，73，77，79，83，91，97.）.2.不定方程非負整數(shù)解數(shù)目計數(shù)問題在離散數(shù)學中我們已經(jīng)找到了不定方程的非負整數(shù)解的數(shù)目.現(xiàn)在給定一個額外的條件：對所有的有，再來解答這個問題.設是方程的解組成的集合，其中對于所有有.于是.稱一組解滿足條件，如果（或者）.那么問題的答案是.由對稱性可知，為了計算，考慮方程的對所有滿足的整數(shù)解.給的值加上8就得到方程滿足條件的解.于是對每個，.同理，是方程的對每一個滿足的整數(shù)解數(shù)目.于是.因為對任意三個條件有，并且，所以由多退少補原理得所以在的1330組非負整數(shù)解中，只有246組對每個滿足.3.函數(shù)設為自然數(shù)，以表示不大于而且與互質的自然數(shù)的個數(shù)，稱為函數(shù)，它在包含計數(shù)的抽象代數(shù)的很多情況中都會用到[10]林才雄.應用容斥原理推廣歐拉函數(shù)[J].江蘇師范大學學報,2015,33(1):52-54..直接可以計算得，，，，.對于每一個素數(shù)，有.下面將導出的一個與有關的公式，使得人們不需要對滿足的每一個都逐個地與整數(shù)進行比較.[10]林才雄.應用容斥原理推廣歐拉函數(shù)[J].江蘇師范大學學報,2015,33(1):52-54.導出歐拉函數(shù)計算公式的過程就是使用多退少補原理.其過程如下：對于由算術基本定理，可寫作，其中，，···，是不同的素數(shù)，且對所有，有.下面考慮的情況.這足以說明一般思想.由于，所以，且對每一個，若能被整除則稱滿足條件.對于，若不能被任何素數(shù)整除，則有與互質，這里.于是.對于每一個有；對于所有有.而且，對所有有，并且.所以，由多退少補原理得：一般地，，其中乘積取遍所有整除的素數(shù).當是一個素數(shù)時，，這和前面觀察到的一樣.3.3概率論中的多退少補原理概率論是一門研究隨機現(xiàn)象數(shù)量規(guī)律性和應用的數(shù)學學科，它屬于隨機數(shù)學內(nèi)容.值得我們留意的是，源自機會博弈科學的概率論在很長一段時間內(nèi)應該一直是人類知識中重要的部分，但是對絕大部分人來說，生活中那些最重要的問題很大部分恰恰是概率論中的問題.在許多生活問題中，將問題劃分為有限個兩兩相互獨立的事件是一件很困難的事情，而多退少補原理能夠在一定程度上幫我們解決這一困擾.又因為古典概型和排列組合有著形影不離的關系，因此多退少補原理在概率論中也占據(jù)十分重要的地位與作用.定義1對于古典隨機試驗，稱為事件發(fā)生的古典概率.古典概率基本性質非負性：對任何事件，0；規(guī)范性:，（：實驗的樣本空間）；有限可加性：若事件，，，互斥，則；任意事件,有;對于相容的事件,有;同樣對于三個事件也有推廣到一般情形有：概率的一般加法公式（多退少補原理）對任意個事件有在概率論中求兩兩相容的事件的概率時，如果我們簡單的按照互斥事件的概率公式去計算它們的概率和，這樣就會導致事件的概率重復計算，此時我們運用多退少補原理就能把重復計數(shù)（多的）部分減去，若減得太多了再補上，直至結果剛好為相容事件的概率.從而就得到了上述相容事件的概率一般加法公式.利用多退少補原理即概率的一般加法公式，我們可以解決生活中很多常見但用其它概率論的方法不易解決的概率問題.具體見下例.例1在學校組織的有個人參加的跨年聯(lián)歡晚會上，每人準備一份簡單而有意義的賀新年禮物放在一起，然后各人從中隨機抽取一份，求各人都得到別人的禮物的概率.分析：這道題我們用古典概率的方法顯然是不好解決的，雖然它總的基本事件數(shù)容易求得，但所包含的基本事件數(shù)不好求.這時我們可以考慮將事件進行劃分，但在劃分過程中很難保證事件兩兩互斥，則用概率的一般加法公式（多退少補原理）就能解決這一難題.解記“各人都得到別人的禮物”，直接求,情況很復雜.若從考慮的對立事件=“個人至少有一個人抽到自己的禮物”著手，就很容易處理；為此，引入“個人至少有一個人抽到自己的禮物”，，，...，，對于事件它們并不是相互排斥的，則由對立事件的概率計算公式、概率的多退少補原理和古典概率的定義，得由立即可知，當充分大時，有.這個問題是整個數(shù)學歷史上非常有名且重要的匹配問題，它于1708年被蒙特摩特（Montmort）所解決，后來由拉普拉斯等數(shù)學家、天文學家加以推廣.它雖然是一個概率問題，但是我們用集合的觀點去研究它，就可以把它轉化為計數(shù)問題，然后運用多退少補原理去解決.3.4染色問題中的多退少補原理染色問題是圖論的研究問題.圖論起源于著名的柯尼斯堡的七橋問題.歐拉在1736年解決了這個問題，他把這個問題通過抽象分析的數(shù)學方法轉化為第一個圖論問題：它用一個點來代替一塊陸地，并且用連接相應的兩個點的一條線來代替每一座橋，得到了一個“圖”.這個問題被歐拉證明了是沒有辦法解的，并且推廣了這個問題[1