第八讲-组合数学

1、第八讲-组合数学第八讲组合数学组合数学是中学数学竞赛的“重头戏”，具有形式多样，内容广泛的特点.本讲主 要围绕组合计数，组合包等式及组合最值展开例1.圆周上有800个点，依顺时针方向标号为1,2,800它们将圆周分成800 个间隙.今选定某一点染成红色，然后按如下规则，逐次染红其余的一些点：若第 k号 点染成了红色，则可依顺时针方向转过 k个间隙，将所到达的点染成红色，试求圆周 上最多可以得到多少个红点？解：易见，第k号点能被染红的充要条件是三jwN10,使得 a0x2j=k (mod800), 1<k<800这里a0是最初染的点的号码，为求最大值，不妨令a0=1.即2j=k (m

2、od25X52).当j=0,1,2,3,4时，k分别为1,2,4,8,16,又由于2模25的阶625(2)= 20 ,因此，当j5时2j+20 -2j=2j(220-1)=0(mod 800),而对Vk<20,kWN*,及 j>5,jWN*,由于 25+(2k1),所以2j+k -2j=2j(2k-1)不为 800 的倍数.所以，共存在5+20=25个k,满足式。注：本题解法不止一种，但利用些同余理论，可使解法简洁许多.例2.集合X的覆盖是指X的一族互不相同的非空子集 A1、A2、Ak,它们 的并集A1U A2UU Ak =X,现有集合X=1,2，,n,若不考虑A1, A2,，Ak

3、的顺序， 试求X的覆盖有多少个？解：首先，X的非空子集共有2n-1个，它们共组成了 22n-1个非空子集族.其次,n 1这些子集族中，不合某一元素i的非空子集组成的非空子集族有(22"-1)个；不含两个元素的子集组成的族有 匕2©-1)个；依次类推，则由容斥原理，X的覆盖共有nn_L(21-1) -(n (22"4 -1) +(2 (22 J - 1)-=£ (-1)"n (22n ' -1)个.j=0注：有些组合计数问题直接计数较难，但从反面考虑简洁明了例3.已知集合X=1,2, m,映射f: X-X,满足对所有的xCX,均有f(f(

4、x)=x , 求这样的映射f的个数.解：设n元中有j个对x、y满足f(x)=y且f(y)=x ,其余的满足f(x)=x ,则当j=0时，仅一种映射，即包等映射.当j>0时，每次取两个作为一对，共取j对有n "n2 i|n2"2 j种取法. l2 A 2 rL 2则不考虑j对的顺序，有n因此，映射f的个数为i -y in/j(2j -1)!9 / 9(f(n)(x)=x)下的注：这些计数问题，以多次在国际竞赛中出现，但对于一般地情况 映射计数，尚无较好的结论.例1.圆周上有800个点，依顺时针方向标号为1,2,800它们将圆周分成800 个间隙.今选定某一点染成红色，然

5、后按如下规则，逐次染红其余的一些点：若第 k号 点染成了红色，则可依顺时针方向转过 k个间隙，将所到达的点染成红色，试求圆周 上最多可以得到多少个红点？解：易见，第k号点能被染红的充要条件是三jWN10,使得 a0M2j三k (mod800), 1<k<800这里a。是最初染的点的号码，为求最大值，不妨令m=1.即2j三k (mod25X52).当j=0,1,2,3,4时，k分别为1,2,4,8,16,又由于2模25的阶625(2) = 20 ,因此，当j5时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 的倍数.所以，共存在5+20=25个k,满足式。注：本题解法不止一种，但利用些同余理论，可使解法简洁许多例4. S为1,2，,n的一些子集族，且S中任意两个集合互不包含，求证：S的，n元素个数的最大值为 -n (Sperner定理)解：考虑n个元素1,2，,n的全排列，显然为n!种，另一方面，全排列中前k个 元素恰好组成S中的某个集Si的，有k!(n-k)!个，由于S中任意子集互不包含，所以， 这种“头”在S中的全排列互不同.设S中有fk个Ai,满足|Ai|=k (k=1,2,n),则nn).一nl 一一 .一Z fk

7、k!(n -k)! <n!，又然知在k = jn时最大，因此«<k；12 当S是由1,2,n中全部口 元子集组成时，等号成立._2注：Sperner定理是1928年发现，证明的方法不止一种.例5.设M= 1,2,3,/网亡/)是连续2mn个正整数组成的集合，求最小的 正整数k,使得M的任何k元子集中都存在 m+1个数，a1,a2,-am+1,满足ai|a+1 (i=1,2，,m).解：记A=1,2，,n,任何一个以i为首项(1&i&n), 2为公比的等比数列与 A的 交集记为A.一方面，由于M中的2mn-n个元的子集n+1,n+2, Zmn中，若存在满足要

8、求的 m+1 个数：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个数，因此所求的 k>2mn-n+1.另一方面，若k=2mn-n+1时，可证明M中的任何k元子集T中，此有m+1个数 ai,戈, am+1 满足 a|a+1 (i< 1 <m).反证：假设这样的m+1个数不存在，考虑2i+1为首项J <n1 j, 2为公比的等 2比数列，它与

9、集合M的交的元素个数为|A2i+1|+m,由假设知，它至少有|A2i+1|个元素不 在T中，冉注意到当iwj时，A2i+1A2j+1=*,可知M中至少有£ |A2i+1|个元素不在 1上£一一2T中,注意到 | A2i A所以|M S上U A2i+11«n.2=|A |= n ,从而|T|< |M|-n< 2mn-n,这与|T|=2mn-n+1矛盾.故假设不成立.综上所述满足要求的最小正整数值k为2mn-n+1.注：这种先确定单边界限再证明最值是经常采用的.n例6.计算Z k2k 1n解：z k2k 1k <k-1y,作指标变换，令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作指标变换,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注：用利基本的组合包等式及指标变换，是证明组合恒等式的重要方法之一q例7.证明：£k

11、=0nY他德蒙公式）In? Tml 证明：t:小1i 11kzi Ak>J，因为的母函数分别为（1+x）n和（1+x）"Y m i是这两个母函数（1+x）m（1+x）n=（1+x）m+n中xq项的系数，又由于（1+x）m+n 也人q-kj中xq的系数为,因此命题成立.=(-If，其中 6mn0, m# nJ,m = n证明：当m=n时，上面和式仅有一项，所以n”(-1)kk mYk1kAm= (-1)m.当m<n时，n1-1)kk mYk<k 人 m Jn八(-1)kk =m'n -m、m人k -m7l 也人 mJ 1m1k m(-1)kn -m<k-

12、m>作指标变换：令l =k-m,则mk-> 1n -m0注：构造母函数法，是证明组合问题重要方法之一，但如何找到母函数，是需要 长时间的体验的.n例 8.设 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产广+(2n*/.(2n* /2n -1 13+（泮广,+（2n2n书广十（2；书）-'2n2n 12n 1(-1)kk =0町1<k) n+1注：此题关键是要找到恒等式2n 2 12n +1 n '1k )2n + 1 12n+1)1 k ) ik+1这种裂项的想法需要对组合数相当有“感觉”，也.是重要方法之一.例10.设an是一个给定的数列，若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严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)个点，设其中任意两点的距离的最大值为 d,我们称距 离为d的两点间的线段为该点集的直径，证明：直径的数目至多有 n条.证明：引理:平面上n(n>3)个点所组成的点集S中，或者存一点至多能引出一 条直径，或者任一点至多能引出两条直径.引理的证明:若每一点都至少能引出两条直径，又有一点A能引出三条直径AB、 AC、AD ,则不妨设AD在AB与AC之间，且必须/BAC060°,因此。A(d)、OB(d)、ABCDOC(d)的公共部分覆盖

16、了整个点集 S,显然与D能引出两条直径，矛盾！引理得证 (如图).下用归纳法证明原体：显然，当n=3时，命题成立，假设命题对k个点成立，则当n=k+1时，如有一点A至多能引出一条直径，去掉 A点后，至多还有k条直径，故S最多有k+1条直径，否则任一点至多能引出两条直径，故S最多有斑尸 =k+1条直径，从而命题成立.注：组合几何在研究点集的组合性质时，对一般的图形也可定义直径、半径等 . 本问题还可推广至三维空间.例12.已知:两个非负整数组成的不同集合 口自,，an和bib,，bn.求证： 集合3+aj 1 <i < j wn与集合卜+bj1 Ei < j M n相同的充要条

17、件是n是2的幕次， 这里允许集合内，相同的元素重复出现.证明：必要性：构造母函数 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 ).因为 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