发布时间 : 星期四 文章《组合数学》测试题含答案更新完毕开始阅读
1.证明：{1,2,?,n}的全排列的最大逆序数是n(n-1)/2。试确定具有n(n-1)/2个逆序的唯一排列。
2.证nc?n?1,r???r?1?c?n,r?1?．并给出组合意义.
3.n个完全一样的球，放到r个有标志的盒子，n≥r，要求无一空盒，试证其方案数为c?n?1,r?1?.
4. 试证一整数是另一个整数的平方的必要条件是除尽它的数目为奇数． 5. 试证明：c?0,m??c?1,m?????c?n,m??c?n?1,m?1? 6. 证明：(C(n,0))2+(C(n,1))2+?+(C(n,n))2 = C(2n,n) 7. 证明：若F1?F2?1, Fn?Fn?1?Fn?2 (n>2)，则
nnFn???1?5/2?1?5/2??/5?? ??n??n/5??????????其中α=（1+√5）/2，β=（1-√5）/2
8. N个代表参加会议，试证其中至少有两个人各自的朋友数相等。 9. 证明：12?22??n2?n?n?1??2n?1?/6 10. 证明：?2n?!/2n是整数。
11. 证明：在边长为1的等边三角形内任取5点，试证至少有两点的距离小于1/2。
?112.证明： ??1?1??Fn?1?????F0??nnFn?? Fn?1?? 其中Fn定义为：F1?F2?1，Fn?Fn?1?Fn?2
13.任取11个整数，求证其中至少有两个数它们的差是10的倍数。
14.在边长为1的正方形内任取5点，试证其中至少有两点，其间距离小于2/2。 15.若H是群G的子群，试证：|xH|=K, 其中K＝|H|，x∈G。
16.二维空间的点（x,y）的坐标x和y都是整数的点称为格点。任意5个格点的
集合A，试证A中至少存在两个点，它们的中点也是格点。 17.证明：在由字母表{0，1，2}生成的长度为n的字符串中，0出现偶数次的字符串有（3n+1）/2个。 18.试证任意r个相邻的正整数的连乘积（n+1）(n+2)?(n+r)必被r!除尽。 19.证明：c?m,0?c?m,n??c?m,1?c?m?1,n?1?????c?m,n?c?m?n,0??2nc?m,n? 20.证明c?n,1??2c?n,2?????nc?n,n??n2n?1
21. 任取5个整数，试求其中必存在3个数，其和能被3整除。
22. 若H是群G的子群，x和y 是G的元素。试证xH∩yH或为空集，或xH=yH. 23. 令S={1，2，?，n+1},n≥2,T???x,y,z??S,x?z,y?z?
试证：T?12?22?......?n2?C?n?1,2??2C?n?1,3?。
24. 证明：任何K个相继的正整数之积，必是r的倍数，其中r=1，2，?，K。
n?22n2n2n25. 求证：?2n?1?=?n?1??2?n???n?1?。
k26. 使用二项式定理证明????2,试推广到任意实数r，求??nk?r。
nnk?0nkknk?027. 证明A?B?C?A?B?C?A?B?A?C?B?C?A?B?C
28. 证明任何k个相继正整数中，有一个必能被k整除。
29. 证明在小于或等于2n的任意n+1个不同的正整数中，必有两个是互等的。 30. 证任一正整数n可唯一地表成如下形式:31. 对于给定的正整数n,证明当
,0≤ai≤i,i＝1,2,?。
时，C?n,k?是最大值。
32. 证明在由字母表{0,1,2}生成的长度为n的字符串中,0出现偶数次的字符串
有
个；
33. 设有三个7位的二进制数：a1a2a3a4a5a6a7，b1b2b3b4b5b6b7，c1c2c3c4c5c6c7。
试证存在整数i和j，1?i?j?7，使得下列之一必定成立，
ai?aj?bi?bj,ai?aj?ci?cj,bi?bj?ci?cj。
34.证明：在n阶幻方中将每个数码a换成n2?1?a，所得的阵列仍是一个n
阶幻方。（注：所谓幻方是指一个n?n方阵，其中的元素分别是1,2??n2，且每列的元素和均相等）
35.证明：把有n个元素的集合s划分为k个有序集合的个数等于kn
36.试证明：1/?1?x?????1?c?n?k?1,k?xk,x?1
nk?0?k 37.证明：如果在边长为1的等边三角形内任取10个点，则必有2个点，它们
的距离不大于1/3。
测 试 题 答 案
——组合数学
一、选择题
1.D 2.C 3.A 4.C 5.A 6.D 7.A 8.B 9.C 10.C 11.B 12.C 13.C 14.A 15.C 16.B 17.D 18.A 19.D 20.C 21.C 22.B 23.D 24.B 25.D 二、填空题 1. 267
4n?2n2.
2n3. an?c1?2n?c2???2??c3?3n?n?0,1,2,???
4. 3?3?2?3
5.
nn1?7t?14t2?8t3?t4
6. 210 7. 0 8. 420 9. 2
10.
2n3?5n2?3n?1
n?111. 2?n?1
?n2?3??n?k?12. ? ????122????13. 23
三、计算题
1、 在1000至9999之间的数都是4位数。我们可以先选个位，再选千位，百位和十位。因
为我们要的数是奇数，所以个位数字可以是1，3，5，7，9中的任何一个，即有5种选择。选定个位数之后，十位就只有8种选择了。百位也只有8种选择，而十位则只有7种选择，因此应用乘法原则，问题的答案是5×8×8×7=2240种。
2、 在这个问题中，我们要计算的是组合数，因为粉笔的特性与上面三种数的顺序无关，利
用乘法法则可知共有3×8×4=96种不同种类的粉笔。
3、 因为2进制数必须考虑其数字的次序，故要计算的是排列问题。有4种选择要做，并且
每种都可以独立地选择0或1，于是有2×2×2×2=24=16种至多4位数字的2进制数，