基本的组合计数公式.ppt

《基本的组合计数公式.ppt》由会员分享，可在线阅读，更多相关《基本的组合计数公式.ppt（31页珍藏版）》请在三一办公上搜索。

1、,漳州师范学院计算机科学与工程系,第十二章 基本的组合计数公式,第十二章 基本的组合计数公式,加法法则与乘法法则排列与组合二项式定理与组合恒等式多项式定理知 识 点：加法法则与乘法法则、排列和组合的定义、排列和组合的生 成算法、基本恒等式、二项式定理、多项式定理教学要求：深刻理解和掌握排列、组合的基本概念及基本应用。教学重点：排列和组合的定义的概念及基本应用。学时:4,12.1 加法法则与乘法法则,加法法则:如果事件 A 有 m 种产生方式,事件 B 有n种产生方式,当A与B产生的方式不重叠时,”事件A或B”有 m+n 种产生方式加法原理中事件的产生方式应是互相排斥的加法法则(集合形式):若

2、S=AB,AB=,则|S|=|A|+|B|加法法则的推广:设A1,A2,An是n个事件,它们的产生方式分别有p1,p2,pn种,当其中任何两个事件产生的方式都不重叠时,事件”A1或A2或或An”有p1+p2+pn种产生方式,12.1 加法法则与乘法法则,乘法法则:事件 A 有 m 种产生方式,事件B 有n 种产生方式,当A与B产生的方式彼此独立时,“事件 A 与 B”有 mn 种产生方式 乘法法则中各事件的出现应是相互独立的,也就是说B的出现不受A的影响,同样A的出现也不受B的影响乘法法则(集合形式):若 S=AB,则|S|=|A|B|乘法法则的推广:设A1,A2,An是n个事件,它们的产生方

3、式分别有p1,p2,pn种,当其中任何两个事件产生的方式都彼此独立时,事件”A1与A2与与An有p1p2pn种产生方式,A上的函数 f 可以用二元关系表示成f=,每个yi都有n种不同的选择,根据乘法法则,有nn个不同的函数,当 f 是双射时,yi y2,yn之间都互不相同构造双射的方法:第一步确定y1,y1共有n种可能的取值第二步确定y2,y1确定后y2只有n-1种可能取值第n步确定yn,yn只有一种取值根据乘法法则 有n(n-1)(n-2)1个不同的构造方法,12.1 加法法则与乘法法则,例12.1 设A为n元集,问A上的自反关系有多少个A上的反自反关系有多少个A上的对称关系有多少个A上的反

4、对称关系有多少个A上的函数有多少个A上的双射函数有多少个,n元集A上的二元关系R的关系矩阵,R是A上的自反关系当且仅当在MR中 对主角线上的元素全都为1,非主对角线上的元素可以是0或1。非主对角线的位置有n2-n个,根据乘法法则自反关系的个数是 2 n2-n,R是A上的反自反关系当且仅当在MR中 对主角线上的元素全都为0,非主对角线上的元素可以是0或1。非主对角线的位置有n2-n个,根据乘法法则自反关系的个数是 2 n2-n,R是A上的对称关系当且仅当MR是对称矩阵。主对角线上的元素可以是0或1,主对角线的位置有n个,在每对非主对角线的对称位置上,两个元素取值同时是0或同时是1,这样的对称位置

5、共有(n2-n)/2对。根据乘法法则对称关系的个数是 2(n2+n)/2,R是A上的反对称关系当且仅当在MR非主对角线的位置上,关于主对角线对称的两个位置取值不能全为1。主对角线上的元素可以是0或1,主对角线的位置有n个,在每对非主对角线的对称位置上,两个元素取值有三种不同的情况,这样的对称位置共有(n2-n)/2对。根据乘法法则对称关系的个数是 2n3(n2-n)/2,这两个元素的取值有三种不同的情况:(0,0),(0,1),(1,0),上、下三角区域分别有1+2+(n-1)个元素,例12.2 Ipv4协议网址计数:32 位地址(w.x.y.z):网络标识+主机标识 A类:最大网络；B类:中

6、等网络；C:最小网络；D类:多路广播；E类:备用 限制条件：1111111 在A 类中的网络标识部分无效 主机标识部分不允许全0或全1 A 类:netid 271,hostid 2242,地址数:127*16777214 B 类:netid 214,hostid 2162,地址数:16384*65534 C 类:netid 221,hostid 282,地址数:2097152*254 Ipv4协议网址总数=2130706178+1073709056+532676608=3737091842,12.1 加法法则与乘法法则,12.1 加法法则与乘法法则,加法法则与乘法法则的其它例子从城市A到城市B

7、有两条陆路,两条水路,一条航线,则由推广的加法原理知,从A到B有2+2+1=5种走法。书架上有三本不同的英语书,两本不同的日语书,两本不同的俄语书,一个学生要选英语、日语、俄语书各一本,由推广的乘法原理知共有3 2 2=12种选法。求比10000小的正整数中含有数字1的数的个数。,12.2 排列与组合,设n元集合S,从S 中选取r 个元素,根据是否有序,是否允许重复可以将该问题分为四个子类型例:S=1,2,3,4,5,从S中选取3个元素无重复排列:1 2 3,2 1 3,5 2 4 看作不同的选取结果可重复排列:1 1 2,1 2 1,2 1 3 看作不同的选取结果无重复组合:1 2 3,2

8、4 5 是不同的选取结果 但 1 2 3,2 1 3看作相同的选取结果可重复组合:1 1 3,2 4 5 是不同的选取结果 但 1 1 3,1 3 1看作相同的选取结果,12.2 排列与组合,定义12.1 设n元集合S从S 中有序选取的r 个元素称作S的一个r排列,S的不同r排列总数记作P(n,r),r=n时的排列称为S的全排列从S 中无序选取的r 个元素称作S的一个r组合,S的不同r组合总数 记作C(n,r),有时也记作定理12.1 设n,r为自然数,规定0!=1,则,12.2 排列与组合,例 设S=1,2,3,4从S的所有不同3排列(从S中有序选取3个元素得到的排列)1 2 3,1 3 2

9、,2 1 3,2 3 1,3 1 2,3 2 1 1 2 4,1 4 2,2 1 4,2 4 1,4 1 2,4 2 1 1 3 4,1 4 3,3 1 4,3 4 1,4 1 3,4 3 1 2 3 4,2 4 3,3 2 4,3 4 2,4 2 3,4 3 2 P(4,3)=24从S的所有不同3组合(从S中无序选取3个元素得到的组合)1 2 3,1 2 4,1 3 4,2 3 4 C(4,3)=4,12.2 排列与组合,推论1 元素依次排成一个圆圈的排列称为环排列.S的r环排列数等于 P(n,r)/r证:设线排列的r个元素依次为 a1,a2,ar,将a1接在ar的后面就组成一个环排列.只要

10、相邻关系不变,这r个元素中的任何一个作为线排列的首元素,首尾相连所构成的环排列都是相同.因此环排列数是线排列数的1/r.例 一家人请客入席,共8个人,围圆桌而坐,若座位不编号有多少种坐法?座位编号呢?解 座位不编号为环状排列问题,有7!=5040种坐法.座位编号实际上为非环状排列问题,故有8!=40320种坐法.,12.2 排列与组合,推论2 设S=a,b,c,d,e,n=5,r=3,C(5,3)=10考虑含有a的组合的生成方法:从余下的4个元素中取2个再加上a,含有a的组合共有C(4,2)=6种,同理含有b,c,d,e的组合都各有6种,这样共得到 5*C(4,2)种组合.但每种组合都被重复计

11、算了3次.例如(a,b,c),分别在计算含有a,b,c的组合中各被计算了一次 所以 C(5,3)=5*C(4,2)/3=5*6/3=10选取一个3组合时,没有被选取的元素同时也组成了一个2组合 例如 选取(a,b,c),同时也得到一个2组合(d,e),即C(5,3)=C(5,2)所有的3组合分成一类含有a,一类不含有a.含有a的组合如上述方法 共有C(4,2)种,不含有a的组合是从余下的4个元素中选取出,共有C(4,3)种,根据加法法则 C(5,3)=C(4,2)+C(4,3),12.2 排列与组合,多重集:S=n1a1,n2a2,nkak 其中 a1,a2,ak 是 k 个不同的元素Ni 表

12、示 ai 在S中出现的次数,称作ai的重复度ni=时表示有足够多的ai以备选取,即ai的选取次数不受限制定义12.2 设S=n1a1,n2a2,nkak为多重集,n=n1+n2+nk 表示S中元素的总数(1)从S中有序选取的r个元素称为多重集S的一个 r排列.当 r=n 时的排列称为 S 的全排列(2)从S中无序选取的r个元素称为多重集S的一个r组合例 由a,b,c,d四个字母组成的长度为10的字符串是多重集的10排列 英文单词 mathematics 中出现的所有字母 a a c e h i m m s t t 是多重集的一个11组合,12.2 排列与组合,定理12.2 设S=n1a1,n2

13、a2,nkak为多重集(1)S的全排列数是(2)若r ni,i=1,2,k,那么S的r排列数是 k rS的全排列数也记作例 由1个a,2个b,3个c,4个d组成的长度为10的字符串共有 10!/(1!2!3!4!)种,12.2 排列与组合,定理12.2 当 r ni,i=1,2,k 时,多重集S的r组合是 C(k+r-1,r)证明 设 S=n11,n22,nkk 现有k个盒子如图所示，编号分别为1,2,k 将 r 个完全相同的球投入到盒子中 第 i 只盒子中装有的球数 ti 表示 S中的元素 i 被取出 ti 次,由于 t1+t2+t k=r 则每次投球的结果都可以得到一个从S中取r个元素的可

14、重复组合。将r个球和 k-1个盒子的隔板位置选好，就可以得到各个盒子的球数 而这样的位置选择恰好有 C(k+r-1,r)种,12.2 排列与组合,例 设 S=1,2,3,4,从S中取3个元素的可重复组合,球与隔板共占有(4-1)+3个位置,球和隔板的位置选择代表可重复组合即从4+3-1个位置中选择3个位置放球，其余位置放隔板就可以得到一个可重复组合,所以总共有 C(4+3-1,3)=C(6,3)=6!/(3!(6-3)!)=20 种可重复组合,12.2 排列与组合,例12.3 排列26 个字母,使得a与b之间恰有7 个字母,求方法数.解 固定a和b,中间插入7 个字母,有 2 P(24,7)种

15、方法,将它看作大字母与其余17 个全排列有 18！种，共 N=2 P(24,7)18!或者 从第1个位置至第18个位置中选取一个位置,设为第k个位 从a,b中选取一个放在第k个位置上,另一个放在第k+8个位置上 将其余的24个字母排在剩余的24个位置上 这样得到的26个字母全排列数为 C(18,1)C(2,1)24!=2P(24,7)18!,12.2 排列与组合,例12.4 把 2n 个人分成n 组,每组2 人,有多少分法？解:相当于把 2n个不同的球放到 n 个相同的盒子,每个盒子2 个,放法为(将2n个球排成一列,按顺序依次各取2个球放入每个盒子中,再消除次序)例12.5 下而给出一段简单

16、的程序,问它的输出x是什么?Algorithm 输出结果为 C(n+k-1,k)1.x02.for i11 to n3.for i21 to i1 K+1.for ik 1 to ik-1K+2.xx+1K+3.return x,例:x=0;for(i=1;i=5;i+)for(j=1;j=i;j+)for(k=1;k=j;k+)x=x+1;return x;返回的结果为 35 即 C(5+3-1,3),12.2 排列与组合,例12.6 从S=1,2,n中选择k个不相邻的数,有多少种方法?解 容易证明 kn-k+1时无解 当 kn-k+1时,设有 n-k+1 个盒子如图所示 将 k 个完全相同

17、的球投入到盒子中,每个盒子最多投入一个球 则不同投球的结果可以得到从S中取k个不相邻数的不同方法。具体做法是从左至右将k个球和(n-k)个盒子中间隔板依次编号为 1,2,3,n 则k个球所对应的编号就是选择k个不相邻数的一种方法 而这样的投球结果恰好有 C(n-k+1,k)种,n-k+1个盒子,12.2 排列与组合,例 设 S=1,2,3,4,5,6,7,8,9,从S中取3个不相邻的数,表示选择的3个数是 1,3,7,表示选择的3个数是 2,5,7,表示选择的3个数是 3,5,9,表示选择的3个数是 2,5,8,表示选择的3个数是 2,4,6,从S中选择3个不相邻的数的方法总数为 C(9-3+

18、1,3)=35,12.3 二项式定理与组合恒等式,定理12.4(二项式定理),设n是正整数,对一切x和y推论 设n是正整数,则,例(x+y)5=(x+y)(x+y)(x+y)(x+y)(x+y)=+C(5,3)x3y2+构成x3y2的项必须是从5个(x+y)中选3个提供x,其他5-3个提供y 因此,x3y2的系数是C(5,3),12.3 二项式定理与组合恒等式,主要恒等式,12.3 二项式定理与组合恒等式,例12.7 证明以下组合恒等式 证(1)由二项式定理有 两边求导数得 令x=1即可得原等式(2),12.3 二项式定理与组合恒等式,非降路径问题:设m,n是正整数,从(0,0)点到(m,n)

19、点的非降路径是 一条折线,这条折线由m+n次移动构成,每次允许向上 或者向右移动一步.问不同的非降路径有多少条?解 不同的路径取决于m+n步的选择 其中包含m步向右,n步向上。这种路径的条数等于从m+n个 位置中选m个位置的方法数。即 C(m+n,m)或 C(m+n,n)例 某城市7条南北走向的街道,6条东西走向的街道。问从西南角到东北角的最短路有几条?解 记东西走向的路段为x,南北走向的路段为y,则每条最短路由6个x和5个y组成.x,y的不同排列构成不同的最短路 所以共有 11!/(5!6!)=C(11,5)条最短路,12.3 二项式定理与组合恒等式,给定非负整数a,b,m,n,其中am,b

20、n.从(a,b)点到(m,n)点的非降路径数等于 从(0,0)点到(m-a,n-b)点的非降路径数,即 C(m-a+n-b,m-a)设a,b,c,d,m,n是非负整数,其中acm,bdn.从(a,b)点经过(c,d)点到(m,n)点的非降路径数=从(a,b)点到(c,d)点的非降路径数 从(c,d)点到(m,n)点的非降路径数,12.3 二项式定理与组合恒等式,例12.8 求集合1,2,n上的单调递增函数的个数 解 将自变量看作横坐标,对应的函数值看作纵坐标,得到n个点,再增加两个点(1,1)和(n+1,n),共有n+2个点(如果f(1)1)(1,1),(1,f(1),(2,f(2),(n,f

21、(n),(n+1,n)如果 f(1)1,那么从(1,1)直接向上连接到(1,f(1)每个点都按先向右,后向上的规则连接到下一个点,这样得到一条从(1,1)到(n+1,n)的非降路径.这种非降路径和集合 1,2,n上单调递增函数是一一对应的 根据公式,集合1,2,n上单调递增函数个数是 C(2n-1,n)例 设A=1,2,3,4,如右图所示 黑线表示的非降路径对应A上的递增函数 f(1)=1,f(2)=1,f(3)=2,f(4)=2 红线表示的非降路径对应A上的递增函数 f(1)=2,f(2)=3,f(3)=3,f(4)=4,12.3 二项式定理与组合恒等式,例12.9 栈(后进先出栈)的输出计

22、数问题 解 将进栈、出栈分别记作x,y,一个输出对应了n个x,n个y的排列,且排列的任何前缀中的x个数不少于y的个数.将排列中的x看作向右 走一步,y看作向上走一步,这样一个排列就对应了一条从(0,0)点到(n,n)点的非降路径,且不穿过对角线。如右图所示,任何一条从(0,0)到(n,n)穿过对角线的路径一定要 接触直线y=x+1,有可能接触多次,但最后会离开这条直线上的一点P,沿直线y=x+1下方的一条非降路径到达(n,n).把从(0,0)到P这部分 以直线y=x+1为轴进行翻转,加上从 P到(n,n)的这段路径就得到一条从(-1,1)到(n,n)的非降路径,这样的路径与原路径是一一对应的。

23、所以,原问题的解为,y=x+1,12.4 多项式定理,定理12.5 设n为正整数,xi为实数,i=1,2,t,那么有 这里 称为多项式系数 当t=2时有 这时就得到二项式定理,12.4 多项式定理,推论1 在多项式定理的展开式中,右边不同的项数为不定 方程 n1+n2+nt=n 的非负整数解的个数推论2,其中求和是对方程 n1+n2+nt=n 的所有非负整数解求和,12.4 多项式定理,例12.10(费马小定理)证明:如果 p 是素数,那么对所有 n0(mod p),有 np-1 1(mod p)引理若,则 证明 由于p是素数,根据全排列数的定义显然有 存在某个 j 使得 kj=p,其他 ki=0,ij 由 可推出 k1!k2!kn!中不含p 由于 是整数,因此 k1!k2!kn!整除(p-1)!所以,12.4 多项式定理,费马小定理的证明 证 根据多项式定理有 令所有的 xi=1 得到 根据引理,当,有 右边恰有n项的值等于1,其余各项之和为 np-n p整除其余的每一项,因此 p|(np-n),即 np-1 1(mod p),