章排列与组合.doc

第三章 排列与组合
3.1 两个基本的计数原理
例3：
有6个桔子和9个苹果，要求蓝子中至少有一个水果，问可以装配成多少种不同的水果蓝？
区分两种不同的计数类型：
（1）对元素的有序摆放数或选择数的计数。
a)没有重复的元素
b)有重复的元素（无限重复或有限重复）
（2）对元素的无序摆放数或选择数的计数。
a)没有重复的元素
b)有重复的元素（无限重复或有限重复）
定义：与顺序有关的摆放或选择称 排列。与顺序无关的摆放或选择称 组合。
3.2 集合的排列
（一）线性排列
定义： 从n个元素中取出r个元素的有序摆放，称n元素集合的r-排列。
用P（n, r）表示n元素集合的全部r-排列数。
定理3.2.1：
对于整数n和r, r £ n, 有：
P（n, r）= n ´(n-1) ´(n-2) 、、、´(n-r+1)=n! /(n-r)!
其中：定义n!= n ´(n-1) ´(n-2)、、、´2 ´1
约定：（1）0！=1
（2）当r>n时，P（n, r）=0
例1：
将数字1，2，、、、，15 放入一个4´4的方阵中，问共有多少种摆放方法？若放入6´6的方阵中，共有多少种摆放方法？
例2：
有多少个取自{1，2，、、、，9}的各位互异的7位数，使得5和6不以任何顺序相继出现？
（二）循环排列
定义：把元素排成首尾相连的一个圈，只考虑元素间的相对顺序的排列称循环排列。
定理3.2.2
n个元素集合的循环r排列个数为：
P（n, r）/r = n! /r(n-r)!
特别地，n元素的循环排列个数=(n-1)!
例3：
10个人围坐一个圆桌，其中2个人不愿彼此挨着就座，问有多少种座位摆放方法？
3.3 集合的组合
定义：
从n个元素中无序地取出r个元素，称n元素集合的r-组合。
用表示n元素集合的全部r-组合数。
定理3.3.1：
对于整数n和r, r £ n, 有：
P（n, r）=r! 即 = P（n, r）/r! =n!/r!(n-r)!
约定：（1）=1
（2）当r>n时， =0
推论3.3.1：
对于整数r，0£r £ n， =
例1：
平面上25个点，假设不存在3点共线情况，问这些点可以组成多少条直线？多少个三角形？
例2：
如果每个词都包含3，4或5个元音，那么字母表中26个字母可以构造多少个8字母词？（假设每个词中的字母使用次数没有限制）
定理3.3.2：
下述公式成立：++…+=2n .
例3：
用不同计数法证明： =n(n-1)/2
3．4 多重集的排列
定理3.4.1：
令S是多重集，它有k个不同的元素，每个元素都有无限重复次数，那么，S的r-排列个数为kr .
例1：
具有4位数字的三进制数的个数是多少？
定理3.4.2：
令S是多重集，它有k个不同的元素，每个元素的重复数分别为n1，n2，、、、，nk，那么，S的排列数=，其中n= n1+n2+、、、+nk
例2：
求字母多重集{1.m, 4.I, 4S, 2.P }的排列数
例3：
在8´8的棋盘上，对于8个非攻击型车有多少种可能的摆放法？
定理3.4.3：
有n个车共k种颜色，其中第一种颜色的车有n1个，第二种颜色的车有n2个， 、、、 ，第k种颜色的车有nk个，那么，把这些车放到n´n的棋盘上，使得没有车能相互攻击的摆放方法数为：. n!
***悬而未决的问题：
多重集S={n1.a1, n2.a2, 、、、, nk.ak }，令n= n1+n2+、、、+nk ，求S的r排列数？其中r<n.
例4：
设多重集S={3.a, 2.b, 4.c}, 求S的8排列个数？
3.5 多重集的组合
定理3.5.1：
令S是多重集，它有k个不同的元素，每个元素都有无限重复次数，那么，S的r-组合个数为= .
例1：
取自自然数1，2，、、、，k的长为r的非减序列个数是多少？
例2：
令S={¥.a, ¥.b, ¥.c, ¥.d },求S的使得4个元素都至少出现一次的10-组合个数。
****悬而未决的问题：
令多重集S={n1.a1, n2.a2, 、、、, nk.ak }，n= n1+n2+、、、+nk ，求S的r-组合数，其中0£r£n.