kk
设
2
k
C
2
成立，则
nk 1
时
4
k
nk1kkkk1
由
C
22
n

n
C
2k2
2C
2k12C
2k
222
nk
C
2n
2C
2 k1
=2
2k1
kkkkk1
C
2k
22C< br>2
4
n

k
4C
2k
444
k1
知不等式成立
nn
由归纳原理，对n≥2不等式
2
n
C
2n
4
恒成立
n1
1
2n1
1
2n1
k
kn 1n
2

C
2n1


C
2n 1
C
2n1
C
2n1

22
k0
k0
（2）
4
n1
2
2n2
四、有重复元素的排 列与组合
1、可重复的排列：从
n
个不同元素中取m个元素（同一元素允许重复取出 ），按照一定的顺序排成一列，叫做从
n
个
不同元素中取m个元素的可重复的排列，这 种排列的个数为
n
。
2、可重复的组合：从
n
个不同元素中取m个 元素（同一元素允许重复取出）并成一组，叫做从
n
个不同元素中取m
m
个元 素的可重复组合，这种组合的个数为
C
nm1
。
m
例2：从银 行中取出伍角、一元、贰元、伍元、十元、五十元、一百元的纸币共10张，共有多少种不同的取法？

3、不全相异元素的全排列：如果
n
个元素中，分别有
n
1
,n
2
,n
k
个元素相同，且
n
1
n
2


n

n
1
n
2

n
，则

n
k

n
1
n
2< br>n
k
n
，则这n个元

n!

。 
n
k

n
1
!n
2
!n
k
!
素的全排列称为不全相异元素的全排列，其不同的排列个数记为

例3：将 3面红旗、4面蓝旗、2面黄旗依次悬挂在旗杆上，问可以组成多少种不同的标志？

4、相 异元素的圆排列：将
n
个不同元素不分首尾排成一圈，称为n个相异元素的圆排列，其排列种数 为（n-1）！。
例4:6为女同学和15位男同学围成一圈跳集体舞，要求每两名女同学之间至少有 两名男同学，那么共有多少种不同的
围圈跳舞的方法？

五、集合与容斥原理 引入集合的交集、并集、补集概念后，研究它们之间的关系，由概念本身的内涵和集合意义有计算集合元素个 数
的公式：
⑴
n(AB)n(A)n(B)n(AB)
; ⑵ n
(A)
=1-n(A)；
⑶
n(ABC)n(A)n(B )n(C)n(AB)n(BC)n(CA)n(BC).
这三个公式简称“容斥 原理”，其意义可用集合的图
形语言表示. 于是，应用“容斥原理”在解决实际计数问题中的操作方法 为：文字语言翻译成集合语言，用集合将同
类元素分组；正确的使用容斥原理公式或其容斥原理的图形语 言进行计数。复杂问题注意补集思想的应用，可以做到
分类“既不重复又不遗漏”.
此结论可以推广到
n
个集合的情况，即

A
i1
n
i


A
i


A
i

A
j

i1ij
n
1ijkn

A
i

A
j

A
k


(1)
n1

A
i1
n
i
.

例5 、开运动会时，高一某班共有28名学生参加比赛，有15人参加游泳比赛，有 8人参加田径比赛，有14人参
加球类比赛，同时参加游泳和田径比赛的有3人，同时参加游泳和球类比 赛的有3人，没有人同时三项比赛.问同时参
加田径和球类比赛的有多少人？只参加一项比赛的有多少人 ？
简析：将文字语言翻译成集合语言，用“容斥原理”公式求解，可做到“分类完备”.设同时参加田 径和球类比赛共

有x人，参加游泳为A=｛15人｝，参加田径为B=｛8人｝，参加球 类为C=｛14人｝.由条件知，A
B
=｛3人｝,A
C
=
｛3 人｝,A
BC

,由“容斥原理”构建方程有，15+8+14-3-3-x= 28,解得 x=3.因此，同时参加田径和球类比赛
共有3人.同理只参加游泳的人有15-3-3=9人.
例6、 求1，2，3，…，100中不能被2，3，5整除的数的个数。
【解】 记I{1,2,3,,100},A{x1x100,且x能被2整除（记为2x）}
，< br>B{x1x100,3x},C{x1x100,5x}
，由容斥原理，

100

100

ABCABCABBCC AABC






2
 
3


100

100

100< br>
100

100


5



6



10



15



30

74
，所以不能被2，3，5 整除的数有
IABC26
个。

五、抽屉原理
抽屉原理：将
mn1
个元素放入
n(n1)
个抽屉，必有一个抽 屉放有不少于
m1
个元素，也必有一个抽屉放有不
多于
m
个元素； 将无穷多个元素放入
n
个抽屉必有一个抽屉放有无穷多个元素。
抽屉原理有时也被称 为鸽笼原理，它由德国数学家狄利克雷首先明确提出来并用来证明一些数论中的问题，因此，
也被称为狄 利克雷原则．抽屉原理是组合数学中一个重要而又基本的数学原理，利用它可以解决很多有趣的问题，并
且常常能够起到令人惊奇的作用．
认识——抽屉原理解决的是存在性问题
操作——构造抽屉的方法：从问题出发，相同即为抽屉；从数量出发：少的就是抽屉。
抽屉原理1：将n+1个物品任意放到n个抽屉中，那么至少有一个抽屉中的物品不少于2件。
原理要点:（1） 物品数比抽屉数多1。只有物品数比抽屉数多时抽屉原理才会成立。
（2） 物品是“任意放”到抽屉中。
（3） 其中“物品不少于2件”的抽屉是一定存在的，但是不确定是哪一个。
（4） 原理的结论是：“至少 有一个抽屉中的物品数不少于2件”，也可以这么说，“至少有2件物品在同一个抽屉
中”。
例7：人的头发平均有12万根。假设最多不超过20万根。13亿人中至少有多少人的头发根数相同？
分析：从问题出发，抽屉就是头发根数。头发根数最多不超20万，那么抽屉数为20万。物品为13亿 人。
1300000000÷200000=6500 ，由抽屉原理2，至少有6500人的头发根数相同。
例8：新年晚会上，老师让每个同学从一个装有 许多玻璃球的口袋中摸两个球，这些球给人的手感相同。只有红、
黄、白、蓝、绿五色之分（摸时看不到 颜色），结果发现总有两个人取的球相同，由此可知，参加取球的至少有多少人？
分析：取两个球，颜色搭配有15 种可能。15个抽屉，本题中物品即为取球的人。
物品数至少为15+1=16个。
【第一抽屉原理】：如果将
m
个物件放入
n
个抽屉内，那么必有一个抽屉内至少有

【推广】：如果将
m
1
m
2


m1


1
个物件。
n

m
n
1
（均为正整数）个物 件放入
n
个抽屉内，那么或者第一个抽屉内至少有
。。。。。或者第
n
个抽屉内至少有
m
n
1
个物件。
m
1
1< br>个，或者第二个抽屉内至少有
m
2
1
个物件。
【第二抽 屉原理】：如果将
m
个物件放入
n
个抽屉内，那么必有一个抽屉内至多有
【推广】如果将
m
1
m
2


m


个物件。
n

个物件放入
n
个抽 屉内，那么或者第一个抽屉内至多有
m
1
1m
n
1
（ 均为正整数）
个，或者第二个抽屉内至多有
m
2
1
个物件。。。。 。。或者第
n
个抽屉内至多有
m
n
1
个物件。