組合數(shù)學2

1、1,第二章鴿巢原理 2.0 和式與積式,2.0.1 和式(Sum formula） 定義 1 a0+a1+…+an稱為a0, a1, …, an的和式，常簡記為,或,(2.0.1),2,“∑”稱為和號； “ai”稱為和式的通項或累加項，“i”為通項的下標或足標，用來標識和式中不同的項。下標i的變化范圍常以邏輯表達式的形式寫在和號下面，簡單時也以羅列的形式表示在和號“∑”的上、下方，下邊指明初值，上邊指明終

2、值，其變化取由初值到終值的相繼遞增整數(shù)。  若令Nn表示前n+1個自然數(shù)所成之集，即Nn={0, 1, 2, …, n}， 則（2.0.1）式還可表示為,3,,命題 1 用和號∑表示的和式中，通項下標的改變不影響和式。 例如,都表示同一和式。  當通項下標不取連續(xù)整數(shù)時，也希望能尋找一些規(guī)律，以便于用和式寫出簡單的表示式，下面給出一些特殊和式的例子。,4,1. 奇數(shù)做下標,2. 偶數(shù)做下標,5,3

3、. 雙下標,4. 給定數(shù)42的所有因子之和:因為 42 =2×21=2×3×7=6×7=1×42=….所以42的所有因子為：1,2,3,6,7,14,21,42,6,1+2+3+6+7+14+21+42= 6. 空和（由邏輯表達式不成立所致， 約定空和的值為0）,7,命題 2（加法的交換律）如果（i1, i2, …, ii）是(1, 2, …, n)的一個置換,則:,命

4、題 3（加法的結(jié)合律）如果1≤m≤n， 則 :,,,8,命題 4（乘法交換律）,命題 5（乘法對加法的分配律）,推論,9,注意到若附加條件xi＞0(1≤i≤n)， 則,2.1.2 積式（Product formula） 與和式類似, 還可以并行的討論積式,或更一般地寫為,10,即積式可轉(zhuǎn)化為和式來處理。條件xi＞0并無實質(zhì)性的限制，因若某個xi=0，則整個積式為0，又恰有k項取負時，可先對（2.1.8）式兩邊乘(-1

5、)k，以確保xi＞0， 最后再將其恢復過來。,例如： （1） n的階乘,11,2.1.1 鴿巢原理（簡單形式） 若在n個盒子中放有n+1個物件，則至少有一個盒子中放有兩個或更多的物件。  證明： 若每個盒子中至多存放1個物件，則n個盒子中至多存放n個物件，但因最初已有n+1個物件，這是不可能的。,2.1 鴿巢原理,12,請注意，鴿巢原理沒有能力指出究竟哪個盒子中放有兩個或更多的物件, 若要做到這

6、一點，除非逐個檢查n個盒子。即應用鴿巢原理只能證明某種安排或某些現(xiàn)象的存在性，但卻不能用來構(gòu)造這種安排或找出某些現(xiàn)象中的具體例子。 例１　367人中至少有２人的生日相同。,13,例２ 10雙手套中任取11只，其中至少有兩只 是完整配對的。例３ 13人中至少有兩人的屬相相等。例4 為了從n對夫婦中保證選出一對夫婦，至少要從2n個人中任取n+1個人。 證明: 設先取的n個人，如果其中已經(jīng)有一對夫婦的話，問

7、題已經(jīng)解決；如果這n個人中沒有一對夫妻，那么這n個人可能的分配情況是：,14,1） n個人全部是作丈夫。 2） n個人全部是作妻子。 3） n個人中有M1,M2,…Mi位先生和 wi+1,wi+2,wn 位太太，但他們中無夫妻。 前兩種情況只要再增加余下的一個人，總能配成一對夫妻；第三種情況下再增加一位先生就能與wi+1,wi+2,wn 位太太配

8、成一對夫妻，再增加一位太太也能與M1,M2,…Mi位先生配成一對夫妻。,15,例5 給定m個整數(shù)a1, a2, …, am。則至少存在整 數(shù)k和l(1≤k≤l≤m)， 使得,證明 構(gòu)造序列s1=a1, s2=a1+a2, …, sm=a1+a2+…+am (2.3.1) 則有 s1＜ s2 ＜…＜sm 如下分兩種情況討論：,16,(a) 若有一個sh,

9、 使m|sh, 則命題已明（此時 k=1, l=h）; (b) 設若單調(diào)增序列（2.3.1）式中任何一個元素都不能被m整除。 令sh=phm + rh ( ph是整數(shù)，h= 1,2,…m,) , 則因0＜rh＜m,由鴿巢原理，序列r1, r2, …, rm 相對于序列 1, 2, …, m – 1；則在r1, r2, …, rm 中，必有兩個相同，選中i≠j（不妨設i＜j）使ri=

10、rj, 從而它們之差的余數(shù)為：,17,這時,例 6 設a1, a2, a3為任意三個整數(shù),(b1, b2, b3)為(a1, a2, a3)的一個任意置換排列，則: (ai - bi)(i=1, 2, 3) 中至少有一個是偶數(shù)。 ,18,證明: 由鴿巢原理a1, a2, a3中至少有兩個數(shù)同為 奇數(shù)或同為偶數(shù)，不妨設a1, a2同為奇數(shù)，置換a1, a2, a3 后得b1, b2中至少有一個是奇數(shù)，因為二奇數(shù)之

11、差必為偶數(shù)，從而a1-b1與a2-b2中至少有一個偶數(shù)。當a1, a2同取偶數(shù)時，討論過程類似（因二偶數(shù)之差必為偶數(shù)）。,19,例７　設a1 , a2 , ··· , a100是由 1和２組成的序列, 已知從其任一數(shù)開始的順序10個數(shù)的和 不超過16．即: ai + ai+1 +… + ai+9 ≤16，1≤ i ≤91則至少存在 h 和 k ，k

12、> h，使得　　 ah + ah+1 +… + ak = 39 證:　令　Sj = ∑ai，j=1,2,… ,100　顯然,20,S1h　Sk－Sh =39 　即 ah + ah+1 +… + ak = 39,21,例8 試證在邊長為 √2的正方形里任取5點,至少有2點的距離不超過1. 如右下圖所示,將邊長為√2的正方形劃為4個全等的小正方形.設置相隔距離最遠的點在四個角，顯然中心位置安

13、排第五點到其他A B 四個點距離相等，而且是 最大距離，等于1。C D,,,,,E,22,例9（中國余數(shù)定理）令m和n為二互質(zhì)的 正整 數(shù)，并令a和b為二整數(shù)，且: 0≤a≤m-1 以及 0≤b≤n

14、-1 。 于是，存在一個正整數(shù)x，使得x除以m的余數(shù)為a，并且x除以n的余數(shù)為b；即x可以寫成:x=pm+a的同時又可以寫成x=qn+b的形式，s說明余數(shù)不同；這里p和q是兩個整數(shù)。 證明：用反證法：我們考慮n個整數(shù),23,0m+a, 1m+a, 2m+a, ….., (n-1)m+a; 這些整數(shù)中每個除以m都余a。假設其中的兩個除以n有相同的余數(shù)r。令這兩個數(shù)表示形式為im+a和jm+a，其中0≤i＜

15、j≤n-1。因此，存在兩個整數(shù)qi和qj，使得： im+a = qin +r 　及 jm+a = qjn +r 　　從第二個方程減去第一個方程得：　　　　 (j – i)m= ( qj – qi)n,24,由上式可以看出，由于n與m沒有除1外 的公因子，因此n是(j – i)的一個因子。然而， 0≤i＜j≤n-1, 意味著: 0 ＜j-i≤n-1＜n,也就是說n不可能是j

16、 - i的因子。該矛盾產(chǎn)生于我們的假設： n個整數(shù) 0m+a, 1m+a, 2m+a, ….., (n-1)m+a中有兩個除以n有相同的余數(shù)r的數(shù)。因此我們斷言：這個n數(shù)中的每一個數(shù)除以n都有不同的余數(shù)。,25,根據(jù)鴿巢原理：n個數(shù)，0,1,2,3,…n-1中的每 個數(shù)作為余數(shù)都要出現(xiàn)；其中特殊的數(shù)b也是如此。令p為整數(shù)，滿足0≤p≤n-1 ，且使數(shù)x = pm + a除以n余數(shù)為b。則對于某個適當?shù)?/p>

17、q，有x = qn +b成立因此x = pm + a且x = qn +b ，證畢,26,,中國余數(shù)定理是說明： 一個整數(shù)x與兩個互質(zhì)的整數(shù)n,m相除，可以得到兩種表示結(jié)果： x = pm + a 和 x = qn+ b ，其中a 和 b 分別是小于除數(shù)m 和 n的余數(shù)，例如： 19 = 9×2+1 = 3×5+4；其中m=2；n=5是互質(zhì) 而選擇n=4的話： 19 = 4&

18、#215;4+3=8×2+2=pm+2 只有一種表示形式。,27,2.1.1 鴿巢原理（加強形式） 定理2.2.1 令q1,q2,…..qn為正整數(shù)。如果將q1+q2+….+qn-n+1個物體放入n個盒子內(nèi)，那么，或者第一個盒子至少含有q1個物體，或者第二個盒子至少含有q2個物體，…..或者第n個盒子至少含有qn個物體。上節(jié)鴿巢原理簡單形式只是加強形式的特殊情況，令qi = 2 那么： q1+q2+….+

19、qn-n+1= 2n-n+1 =n+1 盒子中自少有一,28,若第i個盒子中至多放進qi -1個物件(i=1, 2, …, n)，則放進n個盒子的物件總數(shù)是：,個里放的物品數(shù)量是2個。 證明：用反證法：討論每個盒子最多放物 件的數(shù)量，找出矛盾,29,在初等數(shù)學中加強形式常用于qi =r 的特殊情況： 推論 1 若n(r-1)+1個物件放進n個盒子中，則至少有一個盒子放進了r個或更多的物件。

20、推論 2 m個物件放進n個盒子，則至少有一個盒子里放的物件數(shù)不少于［(m-1)/n］+1。例如：將5個物件放在3個盒子里， [(m-1)/n]+1= [(5-1)/3]+1=[4/3]+1=1 + 1 = 2至少有一個盒子里放的物件數(shù)不少于2個。,30,推論3若q1, q2, …, qn是n個正整數(shù)，而且 則qi(i=1, 2, …, n)中至少有一個不小于r。 推論2、3是說明

21、平均放置物品的情況，在下面的例題中我們會多次使用。,31,例1 一籃子水果裝有蘋果、香蕉、和橘子。為了 保證籃子內(nèi)或者至少8個蘋果或者至少6個香蕉或者至少9個橘子，則放入籃子中的水果的最小數(shù)量是多少？解：由加強形式可知，無論怎么選擇， （8 + 6 + 9）－3 + 1 = 21件水果將保證籃子內(nèi)的水果數(shù)量滿足所要求的性質(zhì)。而總數(shù)20件水果則不滿足所要求的性質(zhì)。,32,例 2 把兩個大小不等的同心圓盤都劃分成

22、20個 相等的扇區(qū)。在大圓盤的20個扇區(qū)中分別填入10個0及10個1, 對小圓盤只要求用0或1兩種數(shù)字把扇區(qū)填滿而不限制雙方的個數(shù)。 斷言存在某種配合，可使小圓盤的20個扇區(qū)中至少有10個與大圓盤的對應扇區(qū)中數(shù)字相同。  證明： 固定小圓盤并讓大圓盤依次轉(zhuǎn)過20個扇面, 這使小圓盤的每個扇面恰碰到10次與自己,33,相同的數(shù)字。對整個小圓盤來說， 相同的數(shù)字總數(shù)應是20×10=200。 從而大圓盤平均轉(zhuǎn)過一

23、個扇面使大小圓盤對應扇面數(shù)字相同者應是200/20=10。 根據(jù)鴿巢原理，至少有一次，其中對應扇面數(shù)字相同者不少于10。,34,例6某班有58名學生，準備選修的課程有“數(shù)理 邏輯”，“離散數(shù)學”，“數(shù)理統(tǒng)計”，“組合數(shù)學”中的1門、 2門、 3門。求證：至少有5名學生選修的課程相同。4門選修的課程中選修1門的有C(4,1)種;選修2門的有C(4,2)種;選修3門的有C(4,3)種;共有 :C(4,1)+C(4,2)+

24、C(4,3)=4+6+4=14種,35,把14種選修課程的情況當作“鴿巢”，學生當作“鴿子”則：有58只“鴿子” 14個“鴿巢”根據(jù)鴿巢原理[(58-1)/14] +1= [4.07] +1= 5，14種選課情況中至少有一種被5個學生選中，故58個學生中至少有5名學生選修的課程相同。[ x ] 是x值的取整函數(shù)。,36,例 5（P.Erdos and A.Szekeres, 1935） 試證任意 n2+1個實數(shù)

25、所成的序列a1, a2, …, an2+1中都含有一個長為n+1的遞增子序列或遞減子序列。 證明 證明思路: 假定沒有長為n+1的遞增子序列，必可推得存在長為n+1的遞減子序列或反之。 對每個k(k=1, 2, …, n2+1)，令mk表示以ak為首的最長遞增子序列的長度。若有一個mk＞n, 則命題已證明。下設對每個k(k=1, 2, …, n2+1),,37,mk≤n，即假設不存在任何一條長度大于n的遞 增子序列。 因?qū)?/p>

26、每個k(k=1, 2, …, n2+1), mk≥1，這使n2+1個正整數(shù)m1, m2, …, mn2+1都落在1, 2, …, n之間。由鴿巢原理之二的推論2（取r=n+1的特殊形式），上述n2+1個整數(shù)中必有n+1個完全相同。不失一般性， 令：其中， 1≤k1＜k2＜…＜kn+1≤n2+1。下證：,38,ak1, ak2, …, akn+1構(gòu)成一長為n+1的遞增子序列。 用反證法:設若不然,即存在某個i(i=1,2,

27、…,n)使aki ＜ aki+1 , 則因ki＜ki+1,故可對以aki+1為首的最長遞增子序列前再置以aki而得到一條以 aki為首的最長遞增子序列，但這將導致 mki ＞ mki+1 , 與mki= mki+1 矛盾。 結(jié)論是aki ≥ aki +1,而這對每個i(i=1, 2, …, n)都是對的,從而有ak1 ≥ ak2 ≥ … ≥ akn+1,39,總 結(jié),本次課我們學習鴿巢