2019-2020年高中數(shù)學競賽輔導資料組合數(shù)學選講組合數(shù)學是中學數(shù)學競賽的“重頭戲”，具有形式多樣，內(nèi)容廣泛的特點.本講主要圍繞組合計數(shù)，組合恒等式及組合最值展開例題講解1圓周上有800個點，依順時針方向標號為1,2,800它們將圓周分成800個間隙.今選定某一點染成紅色，然后按如下規(guī)則，逐次染紅其余的一些點：若第k號點染成了紅色，則可依順時針方向轉(zhuǎn)過k個間隙，將所到達的點染成紅色，試求圓周上最多可以得到多少個紅點？2集合X的覆蓋是指X的一族互不相同的非空子集A1、A2、Ak，它們的并集A1A2Ak =X，現(xiàn)有集合X=1,2,n，若不考慮A1, A2, Ak的順序，試求X的覆蓋有多少個？3已知集合X=1,2,n，映射f：XX，滿足對所有的xX，均有f(f(x)=x，求這樣的映射f的個數(shù).4S為1,2,n的一些子集族，且S中任意兩個集合互不包含，求證：S的元素個數(shù)的最大值為(Sperner定理)5設M= 1,2,3,2mn (m,nN*)是連續(xù)2mn個正整數(shù)組成的集合，求最小的正整數(shù)k，使得M的任何k元子集中都存在m+1個數(shù)，a1,a2,am+1，滿足ai|ai+1 (i=1,2,m).6計算.7證明： (范德蒙公式)8在平面上有n(3)個點，設其中任意兩點的距離的最大值為d，我們稱距離為d的兩點間的線段為該點集的直徑，證明：直徑的數(shù)目至多有n條.9已知：兩個非負整數(shù)組成的不同集合和.求證：集合與集合相同的充要條件是n是2的冪次，這里允許集合內(nèi)，相同的元素重復出現(xiàn).課后練習1. 空間n條直線，最多能把空間分成多少塊空間區(qū)域？2. 證明：.3. 證明：.4. 證明：在邊長為1的等邊三角形內(nèi)有五個點，則這五個點中一定有距離小于的兩點.例題答案：1解：易見，第k號點能被染紅的充要條件是 $jN*0，使得a02jk (mod800)，1k800 這里a0是最初染的點的號碼，為求最大值，不妨令a0=1.即2jk (mod2552).當j=0,1,2,3,4時，k分別為1,2,4,8,16，又由于2模25的階，因此，當j5時2j+20-2j=2j(220-1)0(mod 800),而對"k<20,kN*，及j5,jN*，由于25+(2k-1)，所以2j+k-2j=2j(2k-1)不為800的倍數(shù).所以，共存在5+20=25個k，滿足式。注：本題解法不止一種，但利用些同余理論，可使解法簡潔許多.2解：首先，X的非空子集共有2n-1個，它們共組成了-1個非空子集族.其次，這些子集族中，不合某一元素i的非空子集組成的非空子集族有個；不含兩個元素的子集組成的族有個；依次類推，則由容斥原理，X的覆蓋共有=個.注：有些組合計數(shù)問題直接計數(shù)較難，但從反面考慮簡潔明了.3解：設n元中有j個對x、y滿足f(x)=y且f(y)=x，其余的滿足f(x)=x，則當j=0時，僅一種映射，即恒等映射.當j>0時，每次取兩個作為一對，共取j對有種取法.則不考慮j對的順序，有 .因此，映射f的個數(shù)為 .注：這些計數(shù)問題，以多次在國際競賽中出現(xiàn)，但對于一般地情況(f(n)(x)=x)下的映射計數(shù)，尚無較好的結(jié)論.4解：考慮n個元素1,2,n的全排列，顯然為n!種，另一方面，全排列中前k個元素恰好組成S中的某個集Si的，有k!(n-k)!個，由于S中任意子集互不包含，所以，這種“頭”在S中的全排列互不同.設S中有fk個Ai，滿足|Ai|=k (k=1,2,n)，則,又然知在時最大，因此當S是由1,2,n中全部元子集組成時，等號成立.注：Sperner定理是1928年發(fā)現(xiàn)，證明的方法不止一種.5解：記A=1,2,n，任何一個以i為首項(1in)，2為公比的等比數(shù)列與A的交集記為A.一方面，由于M中的2mn-n個元的子集n+1,n+2,2mn中，若存在滿足要求的m+1個數(shù)：n+1a1<a2<<am+12mn，使得ai|ai+1 (1im)，則ai+12ai，從而am+12am2ma12m(n+1)>2mn，矛盾，故不存在滿足要求的m+1個數(shù)，因此所求的k2mn-n+1.另一方面，若k=2mn-n+1時，可證明M中的任何k元子集T中，此有m+1個數(shù)a1,a2,am+1滿足ai|ai+1 (i1m).反證：假設這樣的m+1個數(shù)不存在，考慮2i+1為首項，2為公比的等比數(shù)列，它與集合M的交的元素個數(shù)為|A2i+1|+m，由假設知，它至少有|A2i+1|個元素不在T中，再注意到當ij時，A2i+1A2j+1=f，可知M中至少有個元素不在T中，注意到 所以 ，從而 |T|M|-n2mn-n，這與|T|=2mn-n+1矛盾.故假設不成立.綜上所述滿足要求的最小正整數(shù)值k為2mn-n+1.注：這種先確定單邊界限再證明最值是經(jīng)常采用的.6.解：，作指標變換，令=k-1，則，因此，, = , = .再次用，所以 , =, =.作指標變換，令-1=S，則，所以 = .所以 .注：用利基本的組合恒等式及指標變換，是證明組合恒等式的重要方法之一.7證明：因為的母函數(shù)分別為 (1+x)n和(1+x)m而是這兩個母函數(shù)(1+x)m(1+x)n=(1+x)m+n中xq項的系數(shù)，又由于(1+x)m+n中xq的系數(shù)為，因此命題成立.注：構(gòu)造母函數(shù)法，是證明組合問題重要方法之一，但如何找到母函數(shù)，是需要長時間的體驗的.A CBD8證明：引理：平面上n(n3)個點所組成的點集S中，或者存一點至多能引出一條直徑，或者任一點至多能引出兩條直徑.引理的證明：若每一點都至少能引出兩條直徑，又有一點A能引出三條直徑AB、AC、AD，則不妨設AD在AB與AC之間，且必須BAC60o，因此A(d)、B(d)、C(d)的公共部分覆蓋了整個點集S，顯然與D能引出兩條直徑，矛盾!引理得證(如圖).下用歸納法證明原體：顯然，當n=3時，命題成立，假設命題對k個點成立，則當n=k+1時，如有一點A至多能引出一條直徑，去掉A點后，至多還有k條直徑，故S最多有k+1條直徑，否則任一點至多能引出兩條直徑，故S最多有條直徑，從而命題成立.注：組合幾何在研究點集的組合性質(zhì)時，對一般的圖形也可定義直徑、半徑等.本問題還可推廣至三維空間.9證明：必要性： 構(gòu)造母函數(shù)，.所以 ，所以 ，即.因為 ，所以.所以 存在，使得 ，所以 ，所以 ，所以 .令x=1,則，所以，即n為2的冪次.充分性：直接構(gòu)造如下中取個，其中 ，中取個,其中，則這兩個集合滿足要求.注：運用母函數(shù)處理集合問題，是常見的方法，尤其注意這種集合中出現(xiàn)在指數(shù)上而不是系數(shù)上的母函數(shù)方法.