第八講-組合數(shù)學(xué)

1、第八講-組合數(shù)學(xué)第八講組合數(shù)學(xué)組合數(shù)學(xué)是中學(xué)數(shù)學(xué)競賽的“重頭戲”，具有形式多樣，內(nèi)容廣泛的特點(diǎn).本講主 要圍繞組合計(jì)數(shù)，組合包等式及組合最值展開例1.圓周上有800個(gè)點(diǎn)，依順時(shí)針方向標(biāo)號為1,2,800它們將圓周分成800 個(gè)間隙.今選定某一點(diǎn)染成紅色，然后按如下規(guī)則，逐次染紅其余的一些點(diǎn)：若第 k號 點(diǎn)染成了紅色，則可依順時(shí)針方向轉(zhuǎn)過 k個(gè)間隙，將所到達(dá)的點(diǎn)染成紅色，試求圓周 上最多可以得到多少個(gè)紅點(diǎn)？解：易見，第k號點(diǎn)能被染紅的充要條件是三jwN10,使得 a0x2j=k (mod800), 1<k<800這里a0是最初染的點(diǎn)的號碼，為求最大值，不妨令a0=1.即2j=k (m

2、od25X52).當(dāng)j=0,1,2,3,4時(shí)，k分別為1,2,4,8,16,又由于2模25的階625(2)= 20 ,因此，當(dāng)j5時(shí)2j+20 -2j=2j(220-1)=0(mod 800),而對Vk<20,kWN*,及 j>5,jWN*,由于 25+(2k1),所以2j+k -2j=2j(2k-1)不為 800 的倍數(shù).所以，共存在5+20=25個(gè)k,滿足式。注：本題解法不止一種，但利用些同余理論，可使解法簡潔許多.例2.集合X的覆蓋是指X的一族互不相同的非空子集 A1、A2、Ak,它們 的并集A1U A2UU Ak =X,現(xiàn)有集合X=1,2，,n,若不考慮A1, A2,，Ak

3、的順序， 試求X的覆蓋有多少個(gè)？解：首先，X的非空子集共有2n-1個(gè)，它們共組成了 22n-1個(gè)非空子集族.其次,n 1這些子集族中，不合某一元素i的非空子集組成的非空子集族有(22"-1)個(gè)；不含兩個(gè)元素的子集組成的族有 匕2©-1)個(gè)；依次類推，則由容斥原理，X的覆蓋共有nn_L(21-1) -(n (22"4 -1) +(2 (22 J - 1)-=£ (-1)"n (22n ' -1)個(gè).j=0注：有些組合計(jì)數(shù)問題直接計(jì)數(shù)較難，但從反面考慮簡潔明了例3.已知集合X=1,2, m,映射f: X-X,滿足對所有的xCX,均有f(f(

4、x)=x , 求這樣的映射f的個(gè)數(shù).解：設(shè)n元中有j個(gè)對x、y滿足f(x)=y且f(y)=x ,其余的滿足f(x)=x ,則當(dāng)j=0時(shí)，僅一種映射，即包等映射.當(dāng)j>0時(shí)，每次取兩個(gè)作為一對，共取j對有n "n2 i|n2"2 j種取法. l2 A 2 rL 2則不考慮j對的順序，有n因此，映射f的個(gè)數(shù)為i -y in/j(2j -1)!9 / 9(f(n)(x)=x)下的注：這些計(jì)數(shù)問題，以多次在國際競賽中出現(xiàn)，但對于一般地情況 映射計(jì)數(shù)，尚無較好的結(jié)論.例1.圓周上有800個(gè)點(diǎn)，依順時(shí)針方向標(biāo)號為1,2,800它們將圓周分成800 個(gè)間隙.今選定某一點(diǎn)染成紅色，然

5、后按如下規(guī)則，逐次染紅其余的一些點(diǎn)：若第 k號 點(diǎn)染成了紅色，則可依順時(shí)針方向轉(zhuǎn)過 k個(gè)間隙，將所到達(dá)的點(diǎn)染成紅色，試求圓周 上最多可以得到多少個(gè)紅點(diǎn)？解：易見，第k號點(diǎn)能被染紅的充要條件是三jWN10,使得 a0M2j三k (mod800), 1<k<800這里a。是最初染的點(diǎn)的號碼，為求最大值，不妨令m=1.即2j三k (mod25X52).當(dāng)j=0,1,2,3,4時(shí)，k分別為1,2,4,8,16,又由于2模25的階625(2) = 20 ,因此，當(dāng)j5時(shí)2j+20 -2j=2j(220-1)=0(mod 800),而對Vk<20,k三N*,及 j>5,jWN*,由

6、于 25+(2k1),所以2j+k -2j=2j(2k-1)不為 800 的倍數(shù).所以，共存在5+20=25個(gè)k,滿足式。注：本題解法不止一種，但利用些同余理論，可使解法簡潔許多例4. S為1,2，,n的一些子集族，且S中任意兩個(gè)集合互不包含，求證：S的，n元素個(gè)數(shù)的最大值為 -n (Sperner定理)解：考慮n個(gè)元素1,2，,n的全排列，顯然為n!種，另一方面，全排列中前k個(gè) 元素恰好組成S中的某個(gè)集Si的，有k!(n-k)!個(gè)，由于S中任意子集互不包含，所以， 這種“頭”在S中的全排列互不同.設(shè)S中有fk個(gè)Ai,滿足|Ai|=k (k=1,2,n),則nn).一nl 一一 .一Z fk

7、k!(n -k)! <n!，又然知在k = jn時(shí)最大，因此«<k；12 當(dāng)S是由1,2,n中全部口 元子集組成時(shí)，等號成立._2注：Sperner定理是1928年發(fā)現(xiàn)，證明的方法不止一種.例5.設(shè)M= 1,2,3,/網(wǎng)亡/)是連續(xù)2mn個(gè)正整數(shù)組成的集合，求最小的 正整數(shù)k,使得M的任何k元子集中都存在 m+1個(gè)數(shù)，a1,a2,-am+1,滿足ai|a+1 (i=1,2，,m).解：記A=1,2，,n,任何一個(gè)以i為首項(xiàng)(1&i&n), 2為公比的等比數(shù)列與 A的 交集記為A.一方面，由于M中的2mn-n個(gè)元的子集n+1,n+2, Zmn中，若存在滿足要

8、求的 m+1 個(gè)數(shù)：n+1 0 a<a2<3 <am+1 02mn,使得 a|a+1 (1< i < m),貝U a+1>2a,從而 am+1 >2am > - > 2ma1 >2m(n+1)>2mn,矛盾，故不存在滿足要求的 m+1個(gè)數(shù)，因此所求的 k>2mn-n+1.另一方面，若k=2mn-n+1時(shí)，可證明M中的任何k元子集T中，此有m+1個(gè)數(shù) ai,戈, am+1 滿足 a|a+1 (i< 1 <m).反證：假設(shè)這樣的m+1個(gè)數(shù)不存在，考慮2i+1為首項(xiàng)J <n1 j, 2為公比的等 2比數(shù)列，它與

9、集合M的交的元素個(gè)數(shù)為|A2i+1|+m,由假設(shè)知，它至少有|A2i+1|個(gè)元素不 在T中，冉注意到當(dāng)iwj時(shí)，A2i+1A2j+1=*,可知M中至少有£ |A2i+1|個(gè)元素不在 1上£一一2T中,注意到 | A2i A所以|M S上U A2i+11«n.2=|A |= n ,從而|T|< |M|-n< 2mn-n,這與|T|=2mn-n+1矛盾.故假設(shè)不成立.綜上所述滿足要求的最小正整數(shù)值k為2mn-n+1.注：這種先確定單邊界限再證明最值是經(jīng)常采用的.n例6.計(jì)算Z k2k 1n解：z k2k 1k <k-1y,作指標(biāo)變換，令1 =k-1

10、,則0，因此,喉；）=£ k）=£（1 +i）c）1 =01 =0=V11n 一. kr，1 =0再次用n n -1k <k-1>n 1n 11 ：.2n4 =i " n; - 2nJ101 =012n作指標(biāo)變換,n 4= (n-1)n:1 =12n。令 1 -1=S,n -411 i：< 吧一一2n-2(n-1廣：2n4=(n-1尸0'二(n- 1 )n22吃1n所以 -k2k 4= n(n -1)2n- 2 n 2n(n 1)2 - n 2注：用利基本的組合包等式及指標(biāo)變換，是證明組合恒等式的重要方法之一q例7.證明：£k

11、=0nY他德蒙公式）In? Tml 證明：t:小1i 11kzi Ak>J，因?yàn)榈哪负瘮?shù)分別為（1+x）n和（1+x）"Y m i是這兩個(gè)母函數(shù)（1+x）m（1+x）n=（1+x）m+n中xq項(xiàng)的系數(shù)，又由于（1+x）m+n 也人q-kj中xq的系數(shù)為,因此命題成立.=(-If，其中 6mn0, m# nJ,m = n證明：當(dāng)m=n時(shí)，上面和式僅有一項(xiàng)，所以n”(-1)kk mYk1kAm= (-1)m.當(dāng)m<n時(shí)，n1-1)kk mYk<k 人 m Jn八(-1)kk =m'n -m、m人k -m7l 也人 mJ 1m1k m(-1)kn -m<k-

12、m>作指標(biāo)變換：令l =k-m,則mk-> 1n -m0注：構(gòu)造母函數(shù)法，是證明組合問題重要方法之一，但如何找到母函數(shù)，是需要 長時(shí)間的體驗(yàn)的.n例 8.設(shè) m&n,證明：Z (-1)k k =mn _m所以，原式=m '()mi3, l 0n(-1)kk =01kn _m=()m m (-4 n" =0.i =0注：我們把6mn稱為克朗耐克爾 屋 在許多組合包等證明中，基本的組合包等式, 往往是有力的武器.例9.證明:2n 1(-1)kJk =0，2n <k J證明易證:2n 2 1 _112n +1 n ' 2n +1' 2n +

13、1口 1kl <k+1 /因此，由于所以,2n 2：n2n 1 ka2n11(-1f6 ) =£ (1)k(kn)k=1(2產(chǎn)廣+(2n*/.(2n* /2n -1 13+（泮廣,+（2n2n書廣十（2；書）-'2n2n 12n 1(-1)kk =0町1<k) n+1注：此題關(guān)鍵是要找到恒等式2n 2 12n +1 n '1k )2n + 1 12n+1)1 k ) ik+1這種裂項(xiàng)的想法需要對組合數(shù)相當(dāng)有“感覺”，也.是重要方法之一.例10.設(shè)an是一個(gè)給定的數(shù)列，若kbk=£ (-1)l(k ai , k=0,1,2, l fkan=Z (-

14、1)k(n bk, n=0,1,2，, k 0則稱an與bk為一對組合互逆公式,試證明之.k證明：考慮-(,1)k nk 0bk,由于k' (-1)kk 0kbk=(-i)k nk=0k k=z£ (-1嚴(yán)kz0 l =0記 Xkl =(-1)k+(n c alk k:一 .二 xklk=0 l =0n nl =0 k 土Xkl ,所以 z (-1)k(nbk=zz (-1)k+(ntkal,k =0k =0 l =0= 1-1)laL (-1)k nl =0k=” (-1)l al ( -1)l ln l =0n=' al ' ln - an . l =0因

15、此，命題成立.注：利用交換求和及克朗耐克爾 " 等證明中，十分有用.證明了組合變換的互逆公式，在許多組合包例11.在平面上有n(>3)個(gè)點(diǎn)，設(shè)其中任意兩點(diǎn)的距離的最大值為 d,我們稱距 離為d的兩點(diǎn)間的線段為該點(diǎn)集的直徑，證明：直徑的數(shù)目至多有 n條.證明：引理:平面上n(n>3)個(gè)點(diǎn)所組成的點(diǎn)集S中，或者存一點(diǎn)至多能引出一 條直徑，或者任一點(diǎn)至多能引出兩條直徑.引理的證明:若每一點(diǎn)都至少能引出兩條直徑，又有一點(diǎn)A能引出三條直徑AB、 AC、AD ,則不妨設(shè)AD在AB與AC之間，且必須/BAC060°,因此。A(d)、OB(d)、ABCDOC(d)的公共部分覆蓋

16、了整個(gè)點(diǎn)集 S,顯然與D能引出兩條直徑，矛盾！引理得證 (如圖).下用歸納法證明原體：顯然，當(dāng)n=3時(shí)，命題成立，假設(shè)命題對k個(gè)點(diǎn)成立，則當(dāng)n=k+1時(shí)，如有一點(diǎn)A至多能引出一條直徑，去掉 A點(diǎn)后，至多還有k條直徑，故S最多有k+1條直徑，否則任一點(diǎn)至多能引出兩條直徑，故S最多有斑尸 =k+1條直徑，從而命題成立.注：組合幾何在研究點(diǎn)集的組合性質(zhì)時(shí)，對一般的圖形也可定義直徑、半徑等 . 本問題還可推廣至三維空間.例12.已知:兩個(gè)非負(fù)整數(shù)組成的不同集合 口自,，an和bib,，bn.求證： 集合3+aj 1 <i < j wn與集合卜+bj1 Ei < j M n相同的充要條

17、件是n是2的幕次， 這里允許集合內(nèi)，相同的元素重復(fù)出現(xiàn).證明：必要性：構(gòu)造母函數(shù) f (x) =xa1 +xa2 + +xan , g(x) = x> +xb2 +xbn.所以 f 2(x) - f (x2) =2 工 xai'j , g2(x) 一 g(x2) = 2 Z xbi"j1 -ii< j £n1Hjiin一一9999999所以 f (x) f (x ) = g (x) g(x ),即 f (x) - g (x) = f (x )- g(x ).因?yàn)?f(1)g(1)=0,所以 x1 f(x) g(x).所以 存在 h w N *,使得 (x -1)h P(x) = f (x) g(x), P(x)豐 0 ,所以 f 2(x) - f (x2) =(x2 -1)h P(x2),所以 f (x) +g(x)(x - 1)hP(x) = (x2 -1)hP(x2),所以f(x) g(x)(x 1)hP(x2)P(x)令x=1，則2n = 2h ,所以，n=2h