acm-组合数学的艺术1

1、CHAPTER 1（1）Introduction to Combinatorics,By Yuhong Zhang (HAUT) , 186-2371-8860 （O）, 159-3629-0516（H）,ACM-Association for Computing Machinery ICPC-International Collegiate Programming Contest,2020/9/15,2,前言,据说很早以前，夏禹治水时，河南洛阳附近的大河里浮出了一只乌龟，背上有一个很奇怪的图形，古人认为是一种祥瑞，预示着洪水将被夏禹王彻底制服。 后人称之为洛书或河图。,黄蓉：“九宫之义，法以

2、灵龟，二四为肩，六八为足，左三右七，戴九履一，五居中央”,易经 系辞中曰：“河出图，洛出书，圣人则之”。,2020/9/15,4,洛书构造 （杨辉1275） 九子斜排 上下對易 左右相更 四维挺出,原型,洛书,7,前言,幻方可以看作是一个3阶方阵，其元素是1到9的正整数，每行、每列以及两条对角线的和都是15。 （斜排法）,2020/9/15,8,其它幻方。,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16,1 15 14 4 12 6 7 9 8 10 11 5 13 3 2 16,【对调法】,2020/9/15,9,丢勒作品忧郁中的四阶幻方,Objective,C

3、ombinatorics, is an important part of discrete mathematics. Techniques for counting are important in computer science, especially in the analysis of algorithm.,组合数学的研究对象,组合数学研究的主要内容是依据一定的规则来安排某些事物的有关数学问题。 这些问题包括如下4个方面： 1.这些安排是否存在，即存在性问题。 2.如果这些安排是存在的，那么符合要求的安排又有多少？即计数问题。 3.怎样构造这样的安排？即算法构造问题 4.如果给出了最

4、优化标准，如何从众多安排中得到最优解？,1.存在性问题,实际生活中的各种问题，有些可以立即得出问题有解还是无解，但也有不少问题难以一时判断。 例如，n个笼子方n+1个鸽子，至少一个笼子放2个以上鸽子。 竞赛中不太可能专门出现判定某个问题是否有解的试题，但往往会在测试数据中加入无解的干扰项。,2.计数问题,如果一个组合的解是存在的，那么很自然地会问有多少不同的解。 例如，将8个“车（皇后）”放在8*8的国际象棋棋盘上，如果它们两两不能互吃，那么称这个8“车”处于一个安全的状态。这种状态是存在的，问题是有多少种这类状态。 这就是一个典型的计数问题。,3.构造性问题,一个组合问题已经判定它的解是存在

5、的，甚至也推知有多少个解，但关键问题还在于如果把解（呈现）构造出来，有的解哪怕给出一个也好。 如前面提到的魔方问题、正交拉丁方问题。,4.优化问题,如果构造算法不止一个，自然面临如何择优，如果改进，使得答案尽早地解出来。 如动态规划和线性规划问题的解决方法。,Outline,Counting（计数）: Product rule, sum rule, Permutations namely the number of ways m mutually events can occur n1 + n2 + + nm-1 + nm We can give another formulation in

6、terms of sets. Let A1, A2, , Am be pairwise disjoint sets. Then |A1 A2 Am | = |A1| |A2| |Am| (In fact, this is a special case of the general Principal of Inclusion-Exclusion (PIE),例1,有一所学校给一名物理竞赛优胜者发奖，奖品有三类： 第一类是三种不同版本的法汉词典； 第二类是四种不同类型的物理参考书； 第三类是两种不同的奖杯。这位优胜者只能挑选一样奖品。那么，这位优胜者挑选奖品的方法有多少？,解：设S是所有这些奖品

7、的集合，Si是第i类奖品的集合(i=1,2,3)。显然SiSj=(ij)，于是由加法规则有,也就是说这位优胜者挑选奖品的方法共有9种。,Product Rule（乘法规则）,If two events are not mutually exclusive (that is we do them separately), then we apply the product rule Theorem: Product Rule Suppose a procedure can be accomplished with two disjoint subtasks. If there are n1 wa

8、ys of doing the first task and n2 ways of doing the second task, then there are n1.n2 ways of doing the overall procedure,example 2,How many different license plates can be made by a state, if each plate is to display three letters followed by three numbers? We divide the procedure of labeling a pla

9、te into six steps - we choose a first letter, a second, and a third, and then a first number, a second, and a third. There are 26 ways to choose a letter of the English alphabet, and there are 10 ways to choose a number from the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Thus the number of possible licens

10、e plates is,26 26 26 10 10 10 = 17,576,000,example 3,某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有多少种着色方案？ 42 = 8 若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则方案数是多少？ 4 4 = 16， 而只有 4 3 = 12 种。(必须能区分条纹色),在乘法法则中要注意事件 A 和 事件 B 的相互独立性。,Classification of Permutations,研究排列问题的主要目的是求出根据已知的条件所能作出的不同排列的种数。 分类,线排列 圆排列 重排列,P

11、ermutations（排列）,A permutation of a set of distinct objects is an ordered arrangement of these objects. An ordered arrangement of r elements of a set of n elements is called an r-permutation Theorem: The number of r permutations of a set of n distinct elements is It follows that In particular Note he

12、re that the order is important. It is necessary to distinguish when the order matters and it does not,Proof.,In constructing an r-permutation of an n-element set, we can choose the first item in n ways, the second item in n - 1 ways, whatever the choice of the first item, . ,and the rth item in n -

13、(r - 1) ways, whatever the choice of the first r - 1 items. By the multiplication principle the r items can be chosen in n x (n - 1) x . x (n - r + 1)ways.,线排列 线排列是把一些元素排成一条直线,A= r是正整数，从这n个不同的元素中取r个按照一定的次序排列起来(rn)，称为集合A的r-排列。 记为P(n,r)。 注意：A的r-排列为A的r有序子集。,例：集合A=a,b,c 集合A有6个2排列：ab,ac,ba,ca, bc，cb 即P(3

14、,2)=6 A有6个3排列：abc,acb,bac,bca,cab,cba, 即P(3,3)=6,例4：由数字1，2，3，4，5，6可以构成多少个数字互不相同的四位数。 解：很显然 这是一个排列P（6，4）360 。 例5：将具有9个字母的单词FRAGMENTS进行排列，要求字母A总是紧跟在字母R的右边，问有多少种这样的排法? 解：A和R可以算一个元素，所以这是一个P（8，8） 答案为P(8,8)=8!=40320,Programming Exercise 1,Are you excited when you see the title AC ? If the answer is YES ,

15、AC it ;You must learn these two combination formulas in the school . If you have forgotten it , see the picture.,Now I will give you n and m , and your task is to calculate the answer .,Input & output,In the first line , there is a integer T indicates the number of test cases.Then T cases follows in

16、 the T lines.Each case contains a character A or C, two integers represent n and m. (1=n,m=10),Sample Input 2 A 10 10 C 4 2,Sample Output 3628800 6,二、圆排列 一些元素排成一个圆圈的排列,从集合A=a1,a2,an的n个不同元素中取出r个元素按照某种顺序(如逆时针)排成一个圆圈，称这样的排列为圆排列(或称循环排列)。,圆排列 一些元素排成一个圆圈的排列,注意：把一个圆排列旋转所得到的另一个圆排列视为相同的圆排列。即排列 a1a2ar, a2a3ar

17、a1, a3ara1a2 , ara1a2ar-1 在圆排列中是同一个. 所以圆排列的个数为 P(n,r)/r=n!/(r(n-r)!) （记下重要结论）,例6：有8人围圆桌就餐，问有多少种就座方式?如果有两人不愿坐在一起，又有多少种就座方式?,解：由圆排列公式知，8人围圆桌就座一共有8!8=7!种就座方式。 又由于两人不愿坐在一起，设这两个人为甲和乙，当甲和乙坐在一起时，相当于7个人围圆桌而坐，其就座方式为7!7=6! 而甲和乙坐在一起时，又有两种情况，或者甲坐在乙的右面，或者甲坐在乙的左面，这样一来，甲和乙坐在一起时共有26!种就座方式 ，,有8人围圆桌就餐，问有多少种就座方式?如果有两人

18、不愿坐在一起，又有多少种就座方式?,甲和乙不坐在一起时共有就座方式的种数为 7!26!=56!=3600,Example 6-2,例7 4男4女围圆桌交替就座有多少种方式?,首先这是一个圆排列 先让四个男（女）的围圆桌而坐，有4!/4种就座方式。 加入一个女（男）的进去就座就有4种方式 加入第二个女（男）的又有3种方式 。 由乘法规则知，4男4女围圆桌交替就座的方式数为(4!/4)4321=144,Exe2. Lolihunters Birthday Bracelet,In Lolihunters birthday, she received a bracelet which consists

19、 of n (n10) different colors of beads . One day, Lohihunter accidentally broke the bracelet, she didnt remember the order of it. How many different bracelets can she make using the n beads？ Language：C/C+/Java Time limit: within 5mins,参考答案,三、重排列,上面我们讨论了从集合A(A中的元素是互不相同的)中选r个元素进行排列，在每种排列中每个元素至多只出现一次的情况

20、 现在考虑元素允许重复出现的情况，即考虑在重集 B=k1a1,k2a2,knan中选r个元素进行的排列。,定义1-3 从重集B=k1b1,k2b2,knbn中选取r个元素按照一定的顺序排列起来，称这种r排列为重排列。,定理1-3 重集B=b1,b2,bn的r排列的个数为 。,证明：选择r-排列的第一项，可以从n个元素中任选一个 。有n种选法 第二项，由于可以重复选取，仍有n种选法。 。 由乘法规则可求得r排列的数目为 。,例8 由1，2，3，4，5，6这六个数字能组成多少个五位数?又可组成多少大于34500的五位数?,一个五位数，数字可以重复出现，这是一个重排列问题。 由定理1.3知，这六个数

21、字可以组成 65个五位数 。,解：,万位：可选4，5，6。其余四位任选,所以个数为364,万位选3， 千位选5，6 后三位任选， 个数为263,万位和千位上的数字分别是3和4，百位上的数字是5，6 。个数为262,由加法规则知，大于34500的 五位数的个数为364+263+262=4392,重集B=n1b1,n2b2,nkbk的全排列个数为n!/n1!n2!nk!,将B中的ni个bi分别赋予上标1，2，ni，即 B=A=b11,b12,b1n1, bk1,bk2,bknk 。A中元素个数为nn1+n2+nk 显然，集合A的全排列个数为n!。,定理1.4,证明：,Proof(Con.),又由于

22、ni个bi赋予上标1，2，ni的办法有ni!种， 对于重集B的任一个全排列，都可以产生集合A的n1!n2!nk!个排列(由乘法规则) 故重集B的全排列个数为n!n1!n2!nk! 证毕。,四面红旗、三面蓝旗、二面黄旗、五面绿旗可以组成多少由14面旗子组成的一排彩旗?,解：这是一个重排列问题，它是求重集4红旗，3蓝旗，2黄旗，5绿旗的全排列的个数 由定理1.4知，组成一排彩旗的种数为14!4!3!2!5!,例9,用字母A、B、C组成五个字母的符号，要求在每个符号里，A至多出现2次，B至多出现1次，C至多出现3次，求此类符号的个数。,这也是一个重排列问题。根据分析，符合题目要求的符号只有三种情况：

23、2A，0B，3C，1A，1B，3C和2A，1B，2C。,例10,解：,由定理1.4和加法规则知：此类符号的个数为 5!/2!0!3! + 5!/1!1!3! + 5!/2!1!2! =60,46,组合恒等式,如图，求从(0, 0)点到 (m, n)点、沿格子线走 的最短路径数N。,一条到达点(m, n)的路径对应 一个由m个x，n个y组成的排列,x x x y y x y x x y y x x y y x x x y,重集B=n1b1,n2b2,nkbk的全排列个数为n!/n1!n2!nk!,Combinations (1),Whereas permutations consider ord

24、er, combinations are used when order does not matter Definition: A k-combination of elements of a set is an unordered selection of k elements from the set. (A combination is imply a subset of cardinality k),Combinations (2),Theorem: The number of k-combinations of a set of cardinality n with 0 k n i

25、s is read n choose k.,Combinations (3),A useful fact about combinations is that they are symmetric Corollary: Let n, k be nonnegative integers with k n, then,Combinations: Example,In a sequence of 10 coin tosses, how many ways can 3 heads and 7 tails come up?,The number of ways of choosing 3 heads o

26、ut of 10 coin tosses is,It is the same as choosing 7 tails out of 10 coin tosses, which illustrates the corollary,Combinations: Example C,How many committees of 5 people can be chosen from 20 men and 12 women If exactly 3men must be on each committee? If at least 4 women must be on each committee?,I

27、f exactly three men must be on each committee? We must choose 3 men and 2 women. The choices are not mutually exclusive, we use the product rule,If at least 4 women must be on each committee? We consider 2 cases: 4 women are chosen and 5 women are chosen. Theses choices are mutually exclusive, we us

28、e the addition rule:,Combinations: Example C,How many committees of 5 people can be chosen from 20 men and 12 women If exactly 3men must be on each committee? If at least 4 women must be on each committee?,If exactly three men must be on each committee? We must choose 3 men and 2 women. The choices

29、are not mutually exclusive, we use the product rule,If at least 4 women must be on each committee? We consider 2 cases: 4 women are chosen and 5 women are chosen. Theses choices are mutually exclusive, we use the addition rule:,(Pascal公式) C(n,r)=C(n-1,r)+C(n-1,r-1) (1.9),证明： C(n,r)= n!/r!(n-r)! =C(n

30、-1,r)+C(n-1,r-1),推论2,也可用组合分析的方法论证：,推论2,在集合A的n个元素中固定一个元素，不妨设为a1， 于是，从n个元素中取r个元素的组合,(1) r个元素中包含a1。这可以从除去a1的n-1个元素中取r-1个元素的组合，然后将a1加入而得到，其组合个数为C(n-1,r-1)。,2)r个元素中不包含a1。这可以从除去a1的n-1 个元素中取r个元素的组合而得到， 其组合个数为C(n-1,r)。,由加法规则即得 C(n,r)=C(n-1,r)+C(n-1,r-1),利用式(1-9)和初始值C(n,0)=C(n,n)=1，对所有非负整数可计算出表1-1的三角形阵列，通常称这

31、个三角阵列为杨辉三角形或Pascal三角形。,0 1 1 1 1 2 1 2 1 3 1 3 3 1 4 1 4 6 4 1 5 1 5 10 10 5 1 6 1 6 15 20 15 6 1 7 1 7 21 35 35 21 7 1 8 1 8 28 56 70 56 28 8 1 ,数510510能被多少个不同的奇数整除?,解：510510=2357111317除2是偶数外都是奇数，于是要整除510510的奇数只能是除2以外的奇素数之积或者1，而且在一个积中一个奇数至多出现一次 。 奇素数之积分下面几种情况讨论： 一个奇素数，一共有C(6，1)=6个 。 六个奇素数，一共有C(6，6)

32、=1个 被1整除，1个 由加法规则知总共有6+15+20+15+6+1+1=64个。,例2,从1，2，1000中选出三个整数，有多少种选法使得所选的三个整数的和能被3整除?,解：把集合A=1,2,1000分成三个子集合， A1=1,4,7,1000A1= 1000/3+1 =334, A2=2,5,8,998A2= 998/3 +1=333, A3=3,6,9,999 A3 = 999/3 =333 a1+a2+a3能被3整除 ,则只有下面两种情形： (1)a1，a2和a3取自同一子集Ai(i=1,2,3)中。 选法的种数为C(334,3)+2C(333,3) (2) a1，a2和a3分别取自

33、不同的子集A1，A2和A3中。 选法的种数为C(334,1)C(333,1)C(333,1) 由加法规则知，符合题意的选法种数为 C(334,3)+2C(333,3)+334*333 *333,例3,定义1.5 从重集B=k1b1,k2b2,knbn中选取r个元素不考虑次序组合起来，称为从B中取r个元素的重复组合。 F(n,r),定理1.6 B=b1,b2,bn的r组合数为 F(n,r)= C(n+r-1,r ) (1.11) 证明 ：设n个元素b1，b2，bn和自然数1，2，n一一对应 于是所考虑的任何组合便可看成是一个r个数的组合c1,c2,cr。可认为各ci是按大小次序排列的，相同的ci

34、 连续地排在一起。如按c1c2cr排列。,重复组合,令di=ci+i-1(i=1,2,r)即 d1=c1, d2=c2, ,dr=cr+r-1。 由于ci最大可取n，故di最大可取n+r-1，这样就得到一个集合1,2,n+r-1的r组合d1, d2, dr (d1d2dr) 易见有一种c1,c2,cr的取法便有一种d1,d2,dr的取法。而这两种取法有一一对应关系，从而这两个组合计数问题是等价的。,这样一来，允许重复的从n个不同元素中取r个元素的组合数和不允许重复的从n+r-1个不同元素中取r个元素的组合数是相同的。故有 F(n,r)=C(n+r-1,r) 注意：在定理1.6中，如果B的不同元素的重复数至少是r，则结论仍成立。,某餐厅有7种不同的菜，为了招待朋友，一