离散数学 (第七版) 课件 第四部分 组合数学

1

组合分析2第8章组合分析初步8.1加法法则与乘法法则8.2基本排列组合的计数方法8.3递推方程的求解与应用38.1加法法则和乘法法则加法法则与乘法法则应用实例4加法法则使用条件：事件A与B产生方式不重叠适用问题：分类选取.方式分别计数，再相加.推广：事件A1有n1种产生方式，事件A2有n2种产生方式，…,事件Ak有nk种产生的方式，则“事件A1或A2或…Ak”有n1+n2+…+nk

种产生的方式.

事件A有m种产生方式，事件B有n种产生方式，则“事件A或B”有m+n种产生方式.5乘法法则使用条件：事件A与B产生方式相互独立适用问题：分步选取.方式是连续的步骤，各步相互独立，分别计数，然后相乘.推广：事件A1有n1种产生方式，事件A2有n2种产生方式，…,事件Ak有nk种产生的方式，则“事件A1与A2与…Ak”有n1n2…nk

种产生的方式.

事件A有m种产生方式，事件B有n种产生方式，则“事件A与B”有mn种产生方式.6应用实例例1由数字1、2、3、4、5构成3位数.(1)如果各位数字都不相同，那么有多少种方法?(2)如果必须是偶数，则有多少种方法?(3)其中可以被5整除的有多少个?(4)其中比300大的有多少个?解(1)5×4×3=60.(2)个位为2,4，十位、百位各5种：2×5×5=50.(3)个位为5，十位和百位同(2)：1×5×5=25.(4)百位取3,4或5，十位和个位各5种:3×5×5=75.7应用实例解1400=23527正因子为：2i5j7k，

0

i

3,0

j

2,0

k

1N=(3+1)(2+1)(1+1)=24例2求1400的不同的正因子个数88.2基本排列组合的计数方法排列组合的分类集合的排列集合的组合多重集的排列多重集的组合9排列组合的分类选取问题：设n元集合S，从S中选取r个元素.根据是否有序，是否允许重复可将该问题分为四个子类型不重复重复有序集合排列P(n,r)多重集排列无序集合组合C(n,r)多重集组合10集合的排列从n元集S中有序、不重复选取的r个元素称为S的一个r排列，S的所有r排列的数目记作

S

的r-环排列数=

11集合的组合从n元集S中无序、不重复选取的

r个元素称为S的一个r组合，S的所有r

组合的数目记作证明方法：公式代入组合证明（一一对应）12基本计数公式的应用解令

A={1,4,…,298}，B={2,5,…,299}

C={3,6,…,300}将方法分类：分别取自A,B,C:各

A,B,C各取1个：例1从1—300中任取3个数使得其和能被3整除有多少种方法？13基本计数公式的应用（续）解1000!=1000

999

998

…

2

1

将上面的每个因子分解，若分解式中共有

i个5,j个2，那么min{i,j}就是0的个数.1,…,1000中有

500个是2的倍数，j>500;200个是5的倍数，

40个是25的倍数（多加40个5），

8个是125的倍数（再多加8个5），

1个是625的倍数（再多加1个5）

i=200+40+8+1=249.min{i,j}=249.

例2求1000！的末尾有多少个0？14多重集S={n1

a1,n2

a2,…,nk

ak}，0<ni

+∞(1)全排列r=n,n1+n2+…+nk=n证明：分步选取，先放a1,有种方法；再放a2,有种方法，...,放ak有种方法

(2)若r

ni时，每个位置都有k种选法，得kr.多重集的排列15多重集的组合当r

ni

，

多重集S={n1

a1,n2

a2,…,nk

ak}的组合数为

证明一个

r组合为{x1

a1,x2

a2,…,xk

ak}，其中

x1+x2+…+xk

=r,xi为非负整数.这个不定方程的非负整数解对应于下述排列

1…101…101…10……01…1

x1个

x2个

x3个

xk个r个1，k-1个0的全排列数为16实例解：设盒子的球数依次记为x1,x2,…,xn,则满足下述方程：

x1+x2+…+xn=r，x1,x2,…,xn为非负整数该方程的解的个数为：例3r个相同的球放到n个不同的盒子里，每个盒子球数不限，求放球方法数.17实例解：固定a

和b中间选7个字母，有种方法将它看作大字母与其余17个全排列有18！种，例4排列26个字母，使得a与b之间恰有7个字母，求方法数.18实例（续）解:(1)

(2)例5(1)10个男孩，5个女孩站成一排，若没女孩相邻，有多少种方法？

(2)如果站成一个圆圈，有多少种方法？19实例（续）解：相当于2n不同的球放到n个相同的盒子，每个盒子2个，放法为例6把2n个人分成n

组，每组2人，有多少分法？20实例（续）例79本不同的书，其中4本红皮，5本白皮.(1)9本书的排列方式数有多少？

(2)若白皮书必须放在一起，那么有多少方法？

(3)若白皮书必须放在一起，红皮书也必须放在一起，那么有多少方法？

(4)若把皮和红皮书必须相间，有多少方法？解：

(1)9!(2)5！5！

(3)5！4！2！(4)5！4！218.3

递推方程的求解与应用Hanoi塔问题递推方程的定义二分归并排序算法的分析快速排序算法的分析递归树分治算法分析的一般公式22Hanoi塔问题Hanoi塔问题：从A柱将这些圆盘移到C柱上去.如果把一个圆盘从一个柱子移到另一个柱子称作1次移动，在移动和放置时允许使用B柱，但不允许大圆盘放到小圆盘的上面.问把所有的圆盘的从A移到C总计需要多少次移动？23算法设计与分析算法Hanoi(A,C,n)//*把n个盘子从A移到C1.Hanoi(A,B,n-1)2.move(A,C)//*把1个盘子从A移到C3.Hanoi(B,C,n-1)

移动n个盘子的总次数为T(n)，得到递推方程

T(n)=2T(n

1)+1.T(1)=1.可以求得T(n)=2n

11秒钟移动1次，64个盘子大约需要5000亿年2425递推方程的定义定义10.5

设序列a0,a1,…,an,…,简记为{an},一个把an与某些个ai（i<n）联系起来的等式叫做关于序列{an}的递推方程.实例：

Fibonacci数列：

fn=fn-1+fn-2,初值f0=1,f1=1

阶乘数列{an}，an=n!：an=nan-1,a1=1

求解方法：迭代法26二分归并排序算法算法Mergesort(A,s,t)//*排序数组A[s..t]1.m(t-s)/22.AMergesort(A,s,m)//*排序前半数组3.BMergesort(A,s+1,t)//*排序后半数组4.Merge(A,B)//*将排好序的A,B归并假设n=2k，比较次数至多为W(n)

W(n)=2W(n/2)+n

1归并两个n/2大小数组的比较次数为n

127实例

输入：[5,1,7,8,2,4,6,3]

划分：[5,1,7,8],[2,4,6,3]

递归排序前半个数组:[5,1,7,8]

[1,5,7,8]

递归排序后半个数组:[2,4,6,3]

[2,3,4,6]

归并:[1,5,7,8]和

[2,3,4,6]

输出：[1,2,3,4,5,6,7,8]归并过程1578234628求解递推方程29归纳法验证解n=1代入上述公式得

W(1)=1log1

1+1=0，符合初始条件.假设对于任何小于n的正整数t，W(t)都是正确的，将结果代入原递推方程的右边得

2W(n/2)+n

1=2(2k

1log2k

1

2k

1+1)+2k

1=2k(k

1)

2k+2+2k

1=k2k

2k+1=nlogn

n+1=W(n)30快速排序算法算法Quicksort(A,p,r)//*排序数组A[p..r]输入：数组A[p..r]输出：排好序的数组A1.ifp<r2.thenq

Partition(A,p,r)//*以A[p]为准划分A3.A[p]A[q]//*A[p]与A[q]交换

4.Quicksort(A,p,q-1)//*对子数组递归排序

5.Quicksort(A,q+1,r)31Partition(A,p,r)1.x

A[p]2.i

p3.j

r+14.whiletruedo5.repeatj

j16.untilA[j]<x//*右边第1个比A[p]小的A[j]7.repeati

i+18.untilA[i]>x//*左边第1个比A[p]大的A[i]9.ifi<j10.thenA[i]A[j]//*交换A[j]与A[i]11.elsereturnj划分过程3227

99

081364861671088

25

9027

250813

64

861671088999027

25081310

8616

7

6488999027

25081310716

866488999016

25081310786648899902733平均时间复杂度T(n)为对数组的各种输入平均做的比较次数将输入按照A[p]在排好序后的位置分别为1,2,…,n进行分类.假设每类输入出现的概率相等A[p]处位置1，划分后子问题规模分别为0和n-1…

A[p]处位置n，划分后子问题规模分别为n-1和0n种输入的平均复杂度为34递推方程求解差消法化简35迭代36用积分近似.37递归树W(n)W(n/2)W(n/2)n

1n/2-1W(n/4)n

1n/2-1W(n/4)….38n-1n/2-1n/2-1n/4-1n/4-1n/4-1