新浪博客

排列与组合（一） 集合的排列与组合

2014-11-22 22:20阅读：

http://blog.sina.cn/dpool/blog/u/3048730274

排列与组合是数学竞赛中常用的基础知识，在这一篇文章中，我将先介绍几个“原则”，然后研究单个集合的排列与组合，幸运的是今天的例题非常简单。

2.1 加法原则与乘法原则

2.1.1加法原则：假设有两个袋子A和B，A中有n个球，B中有m个球。假设所有球互不相同且抽中每个球的概率相等（即不存在主观因素的影响），那么抽出一个球共有m+n种可能。
2.1.2 乘法原则：假设有两个袋子A和B，A中有
n个球，B中有m个球。假设所有球互不相同且抽中每个球的概率相等，那么从A和B中各抽出一个球共有m*n种可能。
2.1.3 减法原则：设集合A是集合U的子集，A’是集合A的补集，那么可得
|A’|=|U|-|A| （|A|表示集合A中的元素个数）
2.1.4 除法原则：设S是一个有限集合，将S中元素分成k个不相交的子集，且每个子集中的元素个数相等，则每个子集中的元素个数为|S|/k.

2.2 集合的排列
n元集合S的一个r排列是指先从S中选出r个元素，然后将其按次序排列，一般用P(n,r)表示n元集合的r排列数。
显然n时P(n,r)=0。
定理2.2.1 当r<=n时，P(n,r)=n(n-1)...(n-r+1)=n!/(n-r)!
(n!表示从1到n的正整数的积，例如 3!=1*2*3=6。我们规定0!=1)
推出：要构造n元集合的一个r排列，我们可以在n个元素中任取一个作为第一项，有n种取法；在确定第一项后，第二项有(n-1)种取法……最终，第r项有(n-r+1)种取法。

例题：10个男生和5个女生聚餐，围坐在圆桌旁。任意两个女生不相邻的坐法有多少种？
解：
先把10个男生排成圆形，有1/10*10!=9! 种方法。固定一个男生的排法。在男生之间两两安排一个女生。女生之间存在顺序问题，故有P(10 5)种排法。由乘法原则知，共有9!*P(10 5)种排法。

2.3 集合的组合
n元集合S的一个r组合是指从S中取出r个元素的一种无序选择，其组合数记为C(r n) （用笔书写时将r和n竖着排列在括号中）
显然，有
(1) C(0 n)=1；C(n n)=1。
(2) C(r n)=0 (r>n)
定理2.3.1 若0<=r<=n，则C(r n)=P(r n)/r!=n!/[r!(n-r)!]
证明：设S是一元集合，任取S中的一个r组合，将该组合中的r个元素进行排列，便可得到P(r,r)=r!个S中的r排列。由不同的r组合产生的r排列显然不同，而且S中的任一r排列都可恰好通过S中的某一r组合排列而得到。故有
P(n,r)=r!*C(r n)

例题：将6名保送生推荐给三个单位，每个单位两名，问有多少种方案？
解：推荐时名字的顺序是无关紧要的。
由乘法原则知方案数为 C(2 6)*C(2 4)*C(2 2)=90 种

我的更多文章

下载客户端阅读体验更佳

APP专享