组合数学题目及标准答案
————————————————————————————————作者：————————————————————————————————日期：
组合数学
例1: 将8个“车”放在8×8的国际象棋棋盘上，如果它们两两均不能互吃，那么称8个“车”处于一个安全状态。问共有多少种不同的安全状态?
解：8个“车”处于安全状态当且仅当它们处于不同的8行和8列上。
用一个排列a1,a2,…,a8 ，对应于一个安全状态，使ai 表示第i 行的ai 列上放置一个“车”。这种对应显然是一对一的。因此，安全状态的总数等于这8个数的全排列总数8!＝40320。
例4：n 位客人在晚会上每人与他人握手d 次，d 是奇数。证明n 偶数。
证：由于每一次握手均使握手的两人各增加 一次与他人握手的次数，因此n 位客人与他人握手 次数的总和 nd 是偶数 — 握手次数的2倍。根据奇偶 性质，已知d 是奇数，那么n 必定是偶数。
例４ 从1到2n 的正整数中任取n +1个，则这n +1个数中，至少有一对数，其中一个是另一个的倍数。
证 设n +1个数是a 1, a 2, ···, an +1。每个数去掉一切2的因子，直至剩下一个奇数为止。组成序列r 1, r 2,, ···, rn +1。这n +1个数仍在[1 , 2n ]中，且都是奇数。而[1, 2n ]中只有n 个奇数，故必有ri =rj = r , 则ai = 2αi r , aj = 2αj r 。若ai ＞aj ，则ai 是aj 的倍数。
例5 设a 1, a 2, ···, am 是正整数，则至少存在一对k 和l , 0≤k证 设Sh = , Sh ≡rh mod m, 0≤rh ≤m -1，
h = 1 , 2 , ···, m . 若存在l , Sl ≡0 mod m 则命题成立．否则，1≤rh ≤m -1．但h = 1 , 2 , ···,m ．由 鸽巢原理，故存在rk= rl , 即Sk ≡Sl mod m ，不妨设l ＞k ．则
Sl －Sk= ak+1+ ak+2+…+ al ≡0 mod m
例6 设a 1, a 2, a3是任意三个整数，b1 b2 b3为a1, a2, a3的任一排列，则a1－b1, a2－b2 ,a3－b3中至少有一个是偶数．
证 由鸽巢原理：a1, a2, a3至少有两个奇偶性相同．则这３个数被２除的余数至少有两个是相同的，不妨设为x; 同样b1, b2, b3中被２除的余数也至少有２个x ．这样a1－b1, a2－b2 , a3－b3被２除的余数至少有一个为０．
例7 设a 1, a 2,…, a100是由数字1和２组成的序列, 已知从其任一数开始的顺序10个数的和不超过16．即
ai+ ai+1+…+ ai+9≤16，1≤i ≤91。
则存在h 和k ，k > h ，使得
ah+1+…+ ak= 39
证 令Sj= ，j =1 , 2 , …,100。显然 ∑=j
i i a 1
∑=h
i i a 1
S1根据假定有S100≤10×16 = 160
作序列S1, S2, …, S100, S1+39, …, S100+39.
共200项．其中最大项S100+39≤160+39
由鸽巢原理，必有两项相等．而且必是前
段中某项与后段中某项相等．设
Sk= Sh+ 39，k>h Sk－Sh=39 即
ah+1+ ah+2+…+ ak= 39
例：1) 求小于10000且的含1的正整数的个数
2) 求小于10000的含0的正整数的个数
解：1) 小于10000的不含1的正整数可看做4位数,
但0000除外.
故有9×9×9×9－1＝6560个.
含1的有：9999－6560=3439个
2) 上述方法不可直接套用来计算“含0”数的个数。
0019“含1”但“不含0”。
不含0的1位数有9个，2位数有92个，3位数有93个，4位数有94个
不含0小于10000的正整数有
9+92+93+94=(95－1)/(9－1)=7380个
含0小于10000的正整数有
9999－7380=2619个
多重集(Multiset)：元素可以重复出现的集合。如：
Ｍ={a,a,a,b,c,c,d,d,d,d}，
也可简记为：M={3·a, 1·b, 2·c, 4·d}
元素也可重复出现无穷次，如无穷个a记为：∞·a
例1000到9999 之间有多少个奇数，其各位数字互不相同？
答案：5×8×8×7=2240
例用数字1，1，1，3，8可以构造多少个不同的5位数？如果用1，1，1，3，3呢？
答案：5×4=20 (5,2)=10
定义：设r为正整数，从n个不同的元素的集合S中，取r个元素按次序排成一行，称为S 的一个r-排列。
例S={a,b,c}，则S有
3个1-排列：a，b，c
6个2-排列：ab，ac，ba，bc，ca，cb
6个3-排列：abc，acb，bac，bca，cab，cba
n元素集的r-排列数记为P(n,r)。若r>n，则P(n,r)=0。
n元素集S的n-排列简称为S的排列或n个元素的排列（全排列）
定义n!=n×(n-1)×…×2×1
0!=1
故P(n,r )= n!/(n-r)!
P(n,0)=1
P(n,n )= n!/0!=n!
例将26个英语字母按任意次序排成一行，不允
许a、e、i、o、u五个元音中任意两个相邻，
有多少种排法？
答案：21! ×P(22,5)
例从{1,2,… ,9} 中任意取7个不同的数字排成一
行，不允许5和6相邻，可以组成多少个不同
的7位数？
答案：P(9,7)-2×6×P(7,5) = 151,200
例10个人围圆桌入座，其中两人希望不坐在一起，有多少种方案？
答案：9！-2×8！
例5对夫妇出席一宴会，围一圆桌坐下，试问有几种不同的方案？若要求每对夫妇相邻又有多少种方案。
答案：9 ！=362880
25×4 ！=32×24=768
例20个不同颜色的珠子串成一条项链，可以串成多少种不同的项链？
答案：19!/2
设r为一非负整数，从具有n个不同元素的集合S中，取r个
元素而不考虑其次序，称为S的一个r-组合，即S的一
个r元素子集。
例如：若S={a,b,c,d}，则S有
1个0-组合：
4个1-组合：{a}，{b}，{c}，{d}
6个2-组合：{a,b}，{a,c}，{a,d}，{b,c}，{b,d}，{c,d}
4个3-组合：{a,b,c},{a,b,d},{a,c,d},{b,c,d}
1个4-组合：{a,b,c,d}
例设总共有15名同学选了数学课，但每次只有12名同学到课，教室里有25个座位，数学老师能看到学生们有多少种可能的座位坐法？
答案：C(15,12)×P(25,12)
