基本的组合计数公式.ppt

,漳州师范学院计算机科学与工程系,第十二章 基本的组合计数公式,第十二章 基本的组合计数公式,加法法则与乘法法则 排列与组合 二项式定理与组合恒等式 多项式定理 知 识 点：加法法则与乘法法则、排列和组合的定义、排列和组合的生 成算法、基本恒等式、二项式定理、多项式定理 教学要求：深刻理解和掌握排列、组合的基本概念及基本应用。 教学重点：排列和组合的定义的概念及基本应用。 学时: 4,12.1 加法法则与乘法法则,加法法则: 如果事件 a 有 m 种产生方式 , 事件 b 有n种产生方式,当a与b产生的方式不重叠时, ”事件a或b” 有 m + n 种产生方式 加法原理中事件的产生方式应是互相排斥的 加法法则 (集合形式): 若 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个事件,它们的产生方式分别有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上的反对称关系有多少个 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,这样的对称位置共有(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类:中等网络；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有两条陆路, 两条水路, 一条航线, 则由推广的加法原理知, 从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 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 , 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的后面就组成一个环排列.只要相邻关系不变,这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)种组合. 但每种组合都被重复计算了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 表示 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 , n2a2 , , nkak为多重集 (1)s的全排列数是 (2)若r ni , i=1,2,k,那么s的r排列数是 k r s的全排列数也记作 例 由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个元素的可重复组合。 将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) 种方法, 将它看作大字母与其余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 下而给出一段简单的程序,问它的输出x是什么? algorithm 输出结果为 c(n+k-1,k) 1. x0 2. for i11 to n 3. for i21 to i1 k+1. for ik 1 to ik-1 k+2. xx+1 k+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 个完全相同的球投入到盒子中,每个盒子最多投入一个球 则不同投球的结果可以得到从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+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)点的非降路径是 一条折线,这条折线由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,bn. 从(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(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 栈(后进先出栈)的输出计数问题 解 将进栈、出栈分别记作x,y,一个输出对应了n个x,n个y的排列, 且排列的任何前缀中的x个数不少于y的个