组合数学(2)排列组合

ACM暑期集训 组合数学（2） 排列组合

1 加法原理

若事件A1有m1种选取方法，事件A2有m2种选取方法， ，事件An有mn种选取方法，则事件A1或事件A2 或事件An共有m m1 m2 mn种选取方法。（注意，事件A1,A2, ,An应是互不相交的）

完成事件A有n类不同的方法（两两互斥），完成第i类有mi种方法，则完成事件A有m m

1 m2 mn种方法。

2 乘法原理

若事件A1有m1种选取方法，事件A2有m2种选取方法， ，事件An有mn种选取方法，则事件A1,A2, An依次连接选取共有m m1 m2 mn种选取方法。

乘法原理的另一种表述方式：

完成事件A需要依次完成事件A1,A2, An。完成事件Ai有mi种方法，则n

完成事件A共有m m1 m2 mn mi种方法。

i 1例：有一4×4 个格子的棋盘，将15只不同的棋子置入棋盘，且留有一个空格，问有多少种方案？ 解：16×15×14× ×2×1＝16！

3 配对原理（一一对应原理、相等原理）

如果可建立两个有限集合A和BA B例：20个乒乓球运动员进行淘汰赛产生一个冠军，要进行几场比赛？解1：

1052（一人轮空）（一人轮空）1

1

10 5 2 1 1 19

解2：设A表示比赛的集合，B表示被淘汰的运动员的集合，A与B显然存在双射，而被淘汰的运动员共19人，由配对原理，A B 19

4 无重集的排列组合 无重集：集合中的不同元素只出现一次，指在选取过程中每个元素不可重复选取，也就是至多选取一次。记作S a1,a2, ,ak 重集：集合中的不同元素可出现多次，指在选取过程中每个元素可重复选取。

有限重集：第i个元素ai至多选取ni次。记作S n1 a1,n2 a2, ,nk ak 其中ni称作ai的重数。

无限重集：不同元素可以选取任意次。记作S a1, a2, , ak

从集合S {a1,a2, ,an}中选取r个元素的有序排列，称为从n中取r的排

列。其不同排列的个数，称为n中取r的排列数，记作p(n,r)。当r n时，称为n个元素的全排列，记作P(n,n)

对于r n，P(n,r)

n!

(n r)!