ACM培训第十二讲-组合数学分析.ppt

ACM程序设计第十二讲-组合数学 湖南工学院 张新玉 zhangxinyu247@163.com 组合数学简介 组合数学起源于古老的数学娱乐和游戏。而在当今社会中同样发挥着重要的作用。 组合数学研究一个集合的物体进行满足一些规则的排列。具体的说，组合数学研究的是这些排列的存在性、计数和分类。 在ACM/ICPC中用到的组合数学知识有： 加法乘法原理、多重集排列和组合、递推关系、母函数、鸽巢原理、容斥原理、 加法乘法原理 加法原理 把事情分成N类，每类有Ci种做法，则该事情共有C1+C2+…+CN种做法 乘法原理 把事情分成N步，每步有Ci种做法，则该事情共有C1*C2*…*CN种做法 [ 例 ] 某班选修企业管理的有 18 人，不选 的有 10 人，则该班共有 18 + 10 = 28 人。 [ 例 ] 北京每天直达上海的客车有 5 次，客 机有 3 次， 则每天由北京直达上海的旅行 方式有 5 + 3 = 8 种。 [例] 某种字符串由两个字符组成，第一个字符可选自{a，b，c，d，e}，第二个字符可选自{1，2，3}，则这种字符串共有5 ?3 = 15 个。 [例] 从A到B有三条道路，从B到C有两条道路，则从A经B到C有3?2=6 条道路。 例 题 例1、数1,2,3,…9的全排列中，求偶数在原来位置上，其余都不在原来位置上的错排数目。 解：偶数位置不动，相当于求1,3,5,7,9五个数字的错排，所求的排列数为 D5=5!(1-1/1!+1/2!-1/3!+1/4!-1/5!)=44 错排问题 例 题 例2、在8个字母A,B,C,D,E,F,G,H的全排列中，求使A,C,E,G四个字母不在原来位置上的错排数目。 解：令S为的8个字母的全排列的集合，有|S|=8!。令Ai(i=1,2, 3,4)分别表示A,C,E,G在原位置的排列的集合。显然，|Ai|=7!, (i=1,2,3,4)，|Ai∩Aj |=6!,(i,j=1,2,3,4;i≠j)，…，（参照定理3.5的证明过程）。 由乘法法则和容斥原理得 例 题 例3、求8个字母A,B,C,D,E,F,G,H的全排列中只有4个元素不在原来位置上的排列数。 解：8个字母中只有4个不在原来的位置上，其余4个不动，相当于4个数字的错排，首先在8个字母中选出4个不动的数字，再作其他4个数字的错排。根据乘法法则，所求的排列数为 C(8,4)×D4=630 例 题 例4、求{1,2,…,n}的全排列中，正好只有r(0≤r≤n)个元素在原来位置上的排列个数。 解：从{1,2,…,n}中取r个数有C(n,r)种方式，选定r个数后，剩下的n-r个数不在原来的位置上，相当于n-r个数字的错排，根据乘法法则，所求的排列数为 C(n,r)×Dn-r 例 题 例5、设有n册书分给n个学生，之后又将这n册书收回重新分给这n个学生。问有多少方式分配这n册书使得没有一个学生两次得到同一册书? 解： n册书可以用n!种方式第一次分给n个学生。对第二次分配，据题意，这是一个n册书的错排。由乘法法则，所求的方式数为 n!×Dn 两个推论 推论3.5.1： 证明： 由于e-1可以表成下列的无穷级数： 故 即 两个推论 推论3.5.2：Dn=(n-1)(Dn-1+Dn-2) 推论3.5.1： 证明： {1,2,…,n}的错排可以分为两种互不相容的类型。 ①对于k∈{2,3,…,n}，令a1=k,ak=1。由于a1≠1，故选取a1的方法有n-1种。而a1=k,ak=1的值已定，故将剩下的n-2个数进行错排，由乘法法则，这种类型的错排列数为(n-1)Dn-2 。 ②对于k∈{2,3,…,n}，令a1=k,ak≠1 。选取a1的方法仍有n-1种。由于a1=k已定，且ak≠1 ，故将剩下的n-1个数{2,3,…,k-1,1, k+1,…,n}进行错排（此时将1看作k），由乘法法则，这种类型的错排数为(n-1)Dn-1 。 由于这两种类型互不相容，由加法法则有 Dn=(n-1)(Dn-1+Dn-2) 容斥原理 容斥原理两个基本公式 容斥原理指的就是以上两个基本公式。 容斥原理两个基本公式 例 求不超过120的素数个数。 因不超过120的合数必然是2、3、5、7的倍数，而且不超过120的合数的因子不可能都超过11。 设 Ai 为不超过120的数 i 的倍数集，i =2，3，5，7。 注意：27并非就是不超过120的素数个数，因为这里排除了2，3，5，7这四个数，又包含了1这个非素数。2， 3，5，7本身是素数。故所求的不超过 120的素数个数为： 27+4-1=3