《組合學(xué)初步》PPT課件.pptVIP

1/23,第 2 節(jié) 組合學(xué)初步,廣義的組合數(shù)學(xué)就是離散數(shù)學(xué)，離散數(shù)學(xué)是狹義的組合數(shù)學(xué)和圖論、代數(shù)結(jié)構(gòu)、數(shù)理邏輯等的總稱。但這只是不同學(xué)者在叫法上的區(qū)別?？傊?，組合數(shù)學(xué)是一門研究離散對(duì)象的科學(xué)。 狹義的組合數(shù)學(xué)主要研究滿足一定條件的組態(tài)（也稱組合模型）的存在、計(jì)數(shù)以及構(gòu)造等方面的問題。 組合數(shù)學(xué)的主要內(nèi)容有組合計(jì)數(shù)、組合設(shè)計(jì)、組合矩陣、組合優(yōu)化等。,2/23,第 2 節(jié) 組合學(xué)初步,主要內(nèi)容：,基本計(jì)數(shù)法則 容斥原理 抽屜原理,3/23,1 基本計(jì)數(shù)法則,如果具有性質(zhì)A的事件有m個(gè)，性質(zhì)B的事件有n個(gè)，則具有性質(zhì)A或B的事件有m+n個(gè)。,加法法則：,設(shè)A，B為兩個(gè)不相交的有限集，則 AB=A+B。,集合描述：,（A和B是性質(zhì)無關(guān)的兩個(gè)事件）,4/23,基本計(jì)數(shù)法則,通俗的語言描述：,如果有p種方法能夠從一堆物品中選擇一個(gè)物品，而有q種方法也能夠從另一堆物品中選擇一個(gè)物品，那么從這兩堆物品中選擇一個(gè)物品的方法共有p+q種。,5/23,基本計(jì)數(shù)法則,若具有性質(zhì)A的事件有m個(gè)，具有性質(zhì)B的事件有n個(gè)，則具有性質(zhì)A及B的事件有mn個(gè)。,乘法法則：,設(shè)A，B為有限集，則AB=AB。,集合描述：,6/23,基本計(jì)數(shù)法則,通俗的語言描述：,一項(xiàng)任務(wù)有p個(gè)結(jié)果，而不論第一項(xiàng)任務(wù)的結(jié)果如何，第二項(xiàng)任務(wù)都有q個(gè)結(jié)果，那么，這兩項(xiàng)任務(wù)連續(xù)執(zhí)行就有pq個(gè)結(jié)果。,一項(xiàng)任務(wù)要經(jīng)過兩個(gè)步驟，如果第一個(gè)步驟有p個(gè)結(jié)果，而不論第一步的結(jié)果如何，第二個(gè)步驟都有q個(gè)結(jié)果，那么，這項(xiàng)任務(wù)就有pq個(gè)結(jié)果。,或者,7/23,基本計(jì)數(shù)法則,例1：求小于10000的正整數(shù)中含有數(shù)字1的數(shù)的個(gè)數(shù)？,例3：確定數(shù)3452 117138的正整數(shù)因子的個(gè)數(shù)？,例2：兩位數(shù)字有多少兩個(gè)位互異且非零的兩位數(shù)？,（答案：3439）,（答案：72）,（答案：1080）,8/23,問題： 設(shè)A, B, C, D為有限集，則 AB=? ABC=? ABBC=?,2 容斥原理,9/23,定理1 容斥原理(或逐步淘汰原理)形式之一 設(shè)A1, A2 ,. , An為n個(gè)有限集，則,容斥原理,10/23,例1：在1000名大學(xué)畢業(yè)生的調(diào)查中, 有804人掌握了英語, 205人掌握了日語, 190人撐握了俄語, 125人既掌握了英語又掌握了日語, 57人既掌握了日語又掌握俄語, 85人既掌握英語又掌握俄語。 試求這1000名大學(xué)生中，英語、日語、俄語全掌握的有多少？,容斥原理,11/23,ABC=A+B+C-AB-AC-BC +ABC,1000=804+205+190-125-85-57+ABC,ABC=68,英語、日語、俄語全掌握的有68人。,則A=804，B=205，C=190，,AB=125,AC=85,BC=57,容斥原理,解:,設(shè)A為掌握了英語的人數(shù)， B為掌握了日語的人數(shù)， C為掌握了俄語的人數(shù)。,12/23,定理2 容斥原理(或逐步淘汰原理)形式之二 設(shè)A1,A2,.,An都是有限集S的子集，則,容斥原理,13/23,例2：1,2,3,4,5,6六個(gè)數(shù)的全排列中不出現(xiàn)135和46的排列有多少個(gè)？,容斥原理,例3：一個(gè)人寫了十封集和十個(gè)信封，然后隨機(jī) 地將信裝入信封，試求每封信都裝錯(cuò)了的概率。,14/23,容斥原理解決的問題:,廣義容斥原理解決的問題:,容斥原理,15/23,抽屜原理：簡(jiǎn)單形式 如果n+1個(gè)物體被放進(jìn)n個(gè)盒子中，那么至少有一個(gè)盒子包含兩只或更多的物體。 其它表述形式： 如果n+1只鴿子被放進(jìn)n個(gè)鴿巢中，那么至少有一個(gè)鴿巢包含兩只或更多的鴿子。 如果n+1個(gè)物體用n種顏色涂色，那么必然有兩個(gè)物體被涂成相同的顏色。,3 抽屜原理,16/23,4個(gè)物體,3個(gè)盒子,存放,1,2,3,4,5,抽屜原理,17/23,例1：在13個(gè)人中存在兩個(gè)人，他們的生日在同一個(gè)月 份里。,抽屜原理,考慮12個(gè)盒子，每個(gè)盒子對(duì)應(yīng)一個(gè)月份，將13 個(gè)人放到12個(gè)盒子中，則至少有一個(gè)盒子包含兩個(gè)或 兩個(gè)以上的人，即，這在13個(gè)人中存在兩個(gè)人，他們 的生日在同一個(gè)月份里。,18/23,應(yīng)至少選擇n+1個(gè)人。 考慮n個(gè)盒子，每個(gè)盒子對(duì)應(yīng)一對(duì)夫婦。如果我們選擇n+1個(gè)人并把他們中的每一個(gè)人放到他們對(duì)偶所在的那個(gè)盒子中去，那么就有同一個(gè)盒子含有兩個(gè)人，也就是說，我們選擇了一對(duì)已婚夫婦。 如果選擇n個(gè)人，可以只選擇所有丈夫或只選擇所有的妻子。,抽屜原理,例2：設(shè)有n對(duì)已婚夫婦。為保證能夠有一對(duì)夫婦被選出，至少要從這2n個(gè)人中選出多少人？,19/23,例3：給定m個(gè)整數(shù)a1, a2, , am, 存在整數(shù)k和l，0klm， 使得ak+1+ak+2+al能夠被m整除。,抽屜原理,例4：一位國(guó)際象棋大師有11周的時(shí)間備戰(zhàn)一場(chǎng)錦標(biāo)賽，他決定每天至少下一盤棋，但是為了使自己不過分疲勞他還決定在每周不能下棋超過12盤。證明存在連續(xù)若干天，期間這位大師恰好下了21盤棋。,例5：從整數(shù)1,2,3,200中我們選擇101個(gè)整數(shù)。證明，在所選擇的這些整數(shù)之間存在兩個(gè)這樣的整數(shù)，其中一個(gè)可以被另一個(gè)整除。 整數(shù)分解知識(shí)：任何一個(gè)整數(shù)都可以寫成2ka的形式，其中，k0，a為奇數(shù)。,20/23,抽屜原理：加強(qiáng)形式 令q1,q2,qn為n個(gè)正整數(shù)。如果將q1+q2+qn-n+1個(gè)物體放入n個(gè)盒子內(nèi)，那么，或者第一個(gè)盒子至少含有q1個(gè)物體，或者第二個(gè)盒子至少含有q2個(gè)物體,或者第n個(gè)盒子至少含有qn個(gè)物體。,抽屜原理,抽屜原理的簡(jiǎn)單形式是其加強(qiáng)形式通過q1=q2=qn=2來實(shí)現(xiàn)的。這時(shí)， q1+q2+qn-n+1=2n-n+1=n+1。,21/23,證明：采用反證法，設(shè)將q1+q2+qn-n+1個(gè)物體放入到n個(gè)盒子中，如果對(duì)于每個(gè)i=1,2,n，第i個(gè)盒子含有少于qi個(gè)物體，那么所有盒子中的物體總數(shù)不超過 (q1-1)+(q2-1)+(qn-1)=q1+q2+qn-n 這與物體的總數(shù)為q1+q2+qn-n+1相矛盾，所以或者第一個(gè)盒子至少含有q1個(gè)物體，或者第二個(gè)盒子至少含有q2個(gè)物體,或者第n個(gè)盒子至少含有qn個(gè)物體。,抽屜原理,22/23,推論1. m個(gè)物體，n個(gè)盒子，則至少有一個(gè)盒子里有不少于(m-1)/n+1個(gè)物體。 證明：采用反證法，設(shè)所有盒子了最多有(m-1)/n個(gè)物體，則n個(gè)盒子中的物體數(shù)最多為n(m-1)/n m-1，與假設(shè)矛盾。 推論2：若取n(m-1)+1個(gè)物體放入n個(gè)盒子中，則至少有1個(gè)盒子有m個(gè)物體。 這個(gè)推論相當(dāng)于q1=q2