组合数学题目及标准答案
香港行政长官-国家公祭日是哪天
组合数学题目及标准答案
———————————————————————————————— 作者：
———————————————————————————————— 日期：
2
组合数学
例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个数是a1, a2, ···,
an+1。每个数去掉一切2的因子，直至剩下一个奇数为止。组
成序列r1, r2,, ···,
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 设a1,
a2, ···, am是正整数，则至少存在一对k和l, 0≤k
h
证 设Sh=
a
i
, Sh≡rh mod m,
0≤rh≤m-1，
i1
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
设a1, a2, 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 设a1, a2,…,
a100是由数字1和２组成的序列, 已知从其任一数开始的顺序10个数
的和不超过16．即
ai+ ai+1+…+ ai+9≤16，1≤i≤91。
则存在h
和k ，k > h，使得
ah+1+…+ ak= 39
j
证 令Sj=
a
i
，j =1
, 2 , …,100。显然
i1
3
S1
作序列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。
4
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名同学选了数学课，但每次只有1
2名同学到课，教室里有25个座位，数
学老师能看到学生们有多少种可能的座位坐 法？
答案： C(15,12)×P(25,12)
5
例 如果每个单词可以有3个或4个元音，字母可以
重复使用，用26个英文字母可以构造出
多少个8个字母的单词？
答案：
C(8,3)×5
3
×21
5
+C(8,4)×5
4
×21
4
例
求不多于四位的三进制数的个数。
解：这个问题相当于多重集{∞·0,∞·1,∞·2}
的4-排列问题，由定理3.4.1，所求的三进制数
的个数N=34=81。
例
用两面红旗，三面黄旗依次悬挂在一根旗杆上，问可以组成多少种不同的标志？
解
所求的标志数是多重集{2·红旗,3·黄旗}的排列数N, 由定理3.4.2得：
N=5!(2!3!)=10
例
MISSISSIPPI这个单词里的所有字母可以组成多少不同的排列？
答案：11!(1!4!4!2!)
定义
设S是多重集，S的含有r个元素的子多重集就叫做S的r-组合。
例如：S={2·a,
1·b,3·c}，S的2-组合有5个，它们是{a,a},{a,b},{a,c},{b,c},{c,c
}
定理3.5.1 设多重集S={∞·a1, ∞·a2,…,
∞·ak}，则S的r-组合数是C(r+k-1,r)。
从k种元素中取允许重复的r-
组合的典型模型是：取r个相同的球，放进k个不同的盒子里，
而每个盒子中的球数不加限制，允许重复
的组合数即其放法方案数。
该数为C(r+k-1,k-1)
=C(r+k-1,r)
从a,b,c 3种元素中取2个元素的多重组合，相当于将2个
相同的球放人3个不同的盒中，
每盒可多于一个球的方案。
多重组合与球放入盒子的方案的对照：
例
从为数众多的一角币、二角币、五角币和一元币中选取六枚有多少种方法？
解 这里有4种
不同的币值,每种币都可无限重复,因此本问题是多重集S={∞·1角,∞·2角,
∞·5角,∞·1
元}的6-组合，故从中选出6枚的方法种数为：
C(4+6-1,6)=C(9,6)=84
6
例
试问(x+y+z)
4
展开后有多少项？
解：这个问题相当于从3种元素
中取可重复4-组合，或4个相同的球放进3个不同的盒子
里，其组合数为：
C(3+4-1,4)=C(6,4)=15
即：(x+y+z)
4
共15项。
推论 设多重集S={n1·a1,n2·a2,…,nk·ak}，且对一切i=1,2,
…,k有ni≥r，则S的r-组合数是
C(r+k-1,r)。
推论
设多重集S={∞·a1, ∞·a2,…, ∞·ak}，r≥k，则S中每个元素至少取一个的r-
组合数
为
C(r-k+k-1,k-1)=C(r-1,k-1)。
推论
r个相同的球放到k个有标志的盒子中，不允许有空盒，共有C(r-1,k-1)种方案。
例 有一电冰箱厂生产15种电冰箱，将其装入集装箱销往外地，每个集装箱可装18台电冰
箱，要求每个集装箱内各种电冰箱至少一台，问可能有多少种不同的集装箱装法？
答案：k=15,r=18
N=C(18-1,15-1)=C(17,14)=680
例 设多重集
S={10·a,10·b,10·c,10·d} ，要求每
种元素在组合中至少出现一次，求S的满
足此条件的 10 组合的数目。
解
方程x1+x2+x3+x4=10的正整数解的个数即为
所求。
用变量代换
y1=x1-1，y2=x2-1，y3=x3-1，y4=x4-1，
变换成求 y1+y2+y3+y4=6的非负整数解的个
数。该数目为
C(6+4-1,6)=C(9,6)。
例
设方程x1+x2+x3+x4=20，求满足x1≥3, x2≥1, x3≥0, x4≥5
的整数解的个数。
解 作变量代换
y1=x1-3，y2=x2-1，y3=x3，y4=x4-5，
方程y1+y2+y3+y4=11的非负整数解的个数即为所求，该数为
C(11+4-1,11)=C(14,3)
例 某保密装置须同时使用若干把
不同的钥匙才能打开。现有７人，每人持若干钥匙。须４
人到场，所备钥匙才能开锁。问①至少有多少把
不同的钥匙？②每人至少持几把钥匙？
7
解
①每３人至少缺１把钥匙，且每３人所缺钥匙不同。故至少共有C(7,3)=35把不同的钥
匙。 <
br>任一人对于其他６人中的每３人，都至少有１把钥匙与之相配才能开锁。故每人至少持C(6,3)
＝20把不同的钥匙。
提供者：潘利强
8