组合数学 第三节.ppt

* * 第一章：排列与组合 1.1 基本计数法则 1.2 一一对应: 1.3 排列与组合 1.4 圆周排列 1.5 排列的生成算法 1.6 允许重复的组合与不相邻的组合 1.7 组合意义的解释 1.8 应用举例 1.9 *Stirling公式 例如：从{1,2,3}中取两个数的组合，原来是 {1，2}，{1，3}， {2，3}， 如果允许重复，多了 {1，1}， {2，2}， {3，3}。 1.6.1 允许重复的组合 1.6 允许重复的组合与不相邻的组合 组合模型: 是两个无标志的球放进三个有区别的盒子的情况，一个盒子中可放一个，也可以放多个。 组合模型是r个无标志的球放进n个有区别的盒子的情况:一个盒子中可放一个，也可以放多个。 定理1.2 在n个不同的元素中取r个进行组合，若允许重复，则组合数为C(n+r-1,r)。 证明：只要证明n取r可重复组合，与从n+r-1中取r个的不允许重复的组合一一对应即可。 设n个元素分别为1,2,3,…,n。从中取r个作允许重复的组合a1,a2,…,ar。(假设这r个我们按顺序给出) 由于允许重复，因此有a1≤a2 ≤…≤ ar。 首先证明每个n取r可重复组合，都对应着不同的从n+r-1中取r个的不允许重复的组合。 从{a1,a2,…,ar}构造序列{a1,a2+1, a3+2 …,ar+(r-1)} 1.6 允许重复的组合与不相邻的组合 (ai+i-1)- (ai-1+i-2)= (ai - ai-1)+10， 从n个不同元素中 取r个作允许重复 的组合 C(n+r-1,r) 并且ar+(r-1)≤n+r-1, 因此ak+(k-1)是1到n+r-1中的元素。 1.6 允许重复的组合与不相邻的组合 显然br-r+1≤n, bk-k+1是1到n中的元素， 而且(bk-k+1)- [bk-1-(k-1)+1]= bk- bk-1 -1≥0 b1≤b2-1≤…≤br-r+1 因此，又得到从n+r-1中取r个作不重复的组合对应于从n个元素中取r个作允许重复的组合。 构造序列b1,b2-1,…,br-r+1, 反过来，要证明从(1,2,…,n+r-1)中取r个作不允许重复的组合(b1,b2,…,br),不妨设b1b2… br≤n+r-1。 对应于从n个元素中取r个作允许重复的组合 1.6 允许重复的组合与不相邻的组合 1.6.2 不相邻的组合 例如：从{1,2,3,4}中取2个的组合如下： {1,3},{1,4},{2,4},{1,2},{2,3},{3,4}。 从{1,2,3,4}中取2个不相邻的组合如下： {1,3},{1,4},{2,4}。 1.6 允许重复的组合与不相邻的组合 定理1.4 从{1,2,…,n}中取r个作不相邻的组合，其组合数为C(n-r+1,r)。 1.6.3 线性方程的整数解的个数问题: x1+x2+…+xn=b,n和b都是非负整数; 求方程的非负整数的解的个数. 允许重复的组合模型是r个无标志的球放进n个有区别的盒子的情况: 方程的非负整数的个数与b个无标志的球放进n个有区别的盒子的情况一一对应. C(n+b-1,b) 1.7 组合的解释 1、路径数问题：如图从(0,0)点出发沿x轴或y轴的正方向每步走一个单位，最终走到(m,n)点，问有多少条路径； 无论怎样走法，在x方向上总共走m步，在y方向上总共走n步，若用一个字母x表示x方向上的一步，一个字母y表示y方向上的一步； 则(0,0)→(m,n)的每一条路径可表示为m个x与n个y的一个多重排列； (m+n)! /(m!n!) =C(m+n,m)=C(m+n,n) 1.7 组合的解释 1.22(P64) 求图1.22中从O到P的路径数 (a)必须经过A点； (b)必须过道路AB (c)必须过A和C (d)道路AB封锁 8 7 6 5 4 3 2 1 B A C O P 解：(a) C(3+2,2) C(5+3,3) (b) C(3+2,2) C(4+3,3) (c) C(3+2,2) C(3+1,1) C(2+2,2) (d) C(8+5,5) -C(3+2,2) C(4+3,3) 1 2 3 4 5 1.7 组合的解释 1.32 C(n,r)=C(n-1,r)+C(n-1,r-1) (0,0) (n-r,r) (n-r-1,r) (n-r,r-1) 1.7 组合的解释 1.33 C(n+r+1