§30组合数学选讲
组合数学是中学数学竞赛的“重头戏”，具有形式多样，内容广泛的特点.本讲主要围绕组合计数，组合恒等式及组合最值展开.
例题讲解
1．圆周上有800个点，依顺时针方向标号为1，2，…，800它们将圆周分成800个间隙.今选定某一点染成红色，然后按如下规则，逐次染红其余的一些点：若第k号点染成了红色，则可依顺时针方向转过k个间隙，将所到达的点染成红色，试求圆周上最多可以得到多少个红点？
[w%^ww.zzst&~ep.#com]
2．集合X的覆盖是指X的一族互不相同的非空子集A1、A2、…、Ak，它们的并集A1∪A2∪…∪Ak =X，现有集合X={1，2，…，n}，若不考虑A1， A2，…， Ak的顺序，试求X的覆盖有多少个？
来源中国%^@教育出版网
[www%.zz@s&t~ep.co^m]
3．已知集合X={1，2，…，n}，映射f：X→X，满足对所有的x∈X，均有f(f(x))=x，求这样的映射f的个数.
中%#国教育出版网~]
4．S为{1，2，…，n}的一些子集族，且S中任意两个集合互不包含，求证：S的元素个数的最
?n???大值为?n?(Sperner定理) ????2??????
第 1 页 共 7 页
5．设M={ 1，2，3，…，2mn} (m，n?N*)是连续2mn个正整数组成的集合，求最小的正整数k，使得M的任何k元子集中都存在m+1个数，a1，a2，…am+1，满足ai|ai+1 (i=1，2，…，m).
来源:z&zstep%#.co@m~]
6．计算
7．证明：
2?n?k???.k?1?k?n来源:%中国@#教育出版网
?n??m??m?n????????? (范德蒙公式)
kq?kqk?0??????q中@国教育出版网&]
8．在平面上有n(≥3)个点，设其中任意两点的距离的最大值为d，我们称距离为d的两点间的线段为该点集的直径，证明：直径的数目至多有n条.
9．已知：两个非负整数组成的不同集合{a1,aa,?,an}和{b1,b2,?,bn}.求证：集合
{ai?aj1?i?j?n}与集合{bi?bj1?i?j?n}相同的充要条件是n是2的幂次，这里允许
集合内，相同的元素重复出现.
来源#:zzst*ep.~com@^]
第 2 页 共 7 页
课后练习
1. 空间n条直线，最多能把空间分成多少块空间区域？
[www.z~^&z#step.co@m]
2
中国教&@育出版网
??n???2n?2. 证明：????????.
k?0??k???n?n中国%^@教育出版网~]
3. 证明：
4. 证明：在边长为1的等边三角形内有五个点，则这五个点中一定有距离小于
中&国教育*^~出@版网1k?n??(?1)1??????k?0?k??2n1?1????. k?n1的两点. 2
来~@源&:*中国教育出版网
第 3 页 共 7 页
例题答案
1．解：易见，第k号点能被染红的充要条件是
?j?N*?{0}，使得a0?2j?k (mod800)，1≤k≤800 ①
中&国教育~#出^%版网
这里a0是最初染的点的号码，为求最大值，不妨令a0=1.即2j?k (mod25×52).
当j=0，1，2，3，4时，k分别为1，2，4，8，16，又由于2模25的阶?25(2)?20，因此，当j≥5时
2j+20?2j=2j(220?1)?0(mod 800)，
中国教@育%#出版网
而对?k<20，k?N*，及j≥5，j?N*，由于25+(2k?1)，所以
2j+k?2j=2j(2k?1)不为800的倍数.
中国教育出版^@&网*#]
所以，共存在5+20=25个k，满足①式。
注：本题解法不止一种，但利用些同余理论，可使解法简洁许多. 2．解：首先，X的非空子集共有2n?1个，它们共组成了2族中，不合某一元素i的非空子集组成的非空子集族有22的族有22n?1-1个非空子集族.其次，这些子集
?2n?1?1?1个；不含两个元素的子集组成
??n?2?1?1个；依次类推，则由容斥原理，X的覆盖共有
?(22n?1?1)???(2n12n?1?1?1)???(2n22n?2?1?1)??=?(?1)j?nj?(22j?0nn?1?1?1)个.
注：有些组合计数问题直接计数较难，但从反面考虑简洁明了.
3．解：设n元中有j个对x、y满足f(x)=y且f(y)=x，其余的满足f(x)=x，则 当j=0时，仅一种映射，即恒等映射.
当j>0时，每次取两个作为一对，共取j对有???则不考虑j对的顺序，有
?n??n?2??22?????n?2j?2???种取法.
2??1?n??n?2? !????j?2??2??2?j2??n???2???n??2????n?2j?1 ). !!??(?2j??因此，映射f的个数为1??n?????(2j?1)!! . j?1?2j?注：这些计数问题，以多次在国际竞赛中出现，但对于一般地情况(f(n)(x)=x)下的映射计数，尚无较好的结论.
4．解：考虑n个元素1，2，…，n的全排列，显然为n!种，另一方面，全排列中前k个元素恰好组成S中的某个集Si的，有k!(n?k)!个，由于S中任意子集互不包含，所以，这种“头”
第 4 页 共 7 页
在S中的全排列互不同.
设S中有fk个Ai，满足|Ai|=k (k=1，2，…，n)，则
?n??n?f?k!(n?k)!?n!k?，又然知在时最大，因此 ?k????2k??k?1??n当S是由{1，2，…，n}中全部??元子集组成时，等号成立.
2注：Sperner定理是1928年发现，证明的方法不止一种.
5．解：记A={1，2，…，n}，任何一个以i为首项(1≤i≤n)，2为公比的等比数列与A的交集记为A.
一方面，由于M中的2mn?n个元的子集{n+1，n+2，…，2mn}中，若存在满足要求的m+1个数：n+1≤a1
另一方面，若k=2mn?n+1时，可证明M中的任何k元子集T中，此有m+1个数a1，a2，…am+1满足ai|ai+1 (i≤1≤m).
反证：假设这样的m+1个数不存在，考虑2i+1为首项?i??n?????n?1??，2为公比的等比数列，2?它与集合M的交的元素个数为|A2i+1|+m，由假设知，它至少有|A2i+1|个元素不在T中，再注意到当i≠j时，A2i+1?A2j+1=?，可知M中至少有
?1?i?|A2i+1|个元素不在T中，
n-12注意到
1?i?n?12A2??A 所以 |M\\S|?i11?i?n?12A2i+1?|A|?n，
从而 |T|≤|M|?n≤2mn?n，这与|T|=2mn?n+1矛盾.故假设不成立.
综上所述满足要求的最小正整数值k为2mn?n+1. 注：这种先确定单边界限再证明最值是经常采用的.
n?n?n2n?n?1??n?1?n6.解：?k????k????n?k??，作指标变换，令l=k?1，则1k?lk?k?1?k?1k?1?k?1??k?k?1n2n?10，
因此，
?k????k????(l?1)??，
n?1k?1n?1ln?1lk?1l?0nl?0nn?1n?1 =
?l????k??，
n?1ln?1lk?1l?0n?1第 5 页 共 7 页
相关推荐：
loading