20章节 组合计数.pptVIP

第20讲 组合计数;Chapter 8 组合计数 ;计算机科学是研究算法的一门科学，组合计数是算法分析与设计的基础，它对于分析算法的时间复杂度和空间复杂度是至关重要的. 当然，组合计数在诸多领域的很多问题的讨论中也经常用到. 从儿时的数“数”也略知组合计数的重要性. 本章主要讨论组合计数的基本计数技巧和方法，包括计数的基本原理、排列组合、二项式定理、生成函数与递归关系等内容，它们都与集合、映射、运算和关系密切联系. ;8.1 排列组合与二项式定理 ;注意到 随着n的增大，n!呈指数增长. Stirling给出的近似公式为: ;利用乘法原理有下述结论. 定理8-1 对于任意r ≤ n, 有 显然 , n个元素的全排列个数为n!. 约定;2. n个元素的r-圆排列 实际上, n个元素的r-排列是线排列. 如果从n个不同的元素中, 取r个出来按顺序排列成一个圆, 就是n个元素的r-圆排列(circular permutation), 这样的排列个数记为⊙ 或⊙P(n, r). ;上面的圆排列可以得到1234,2341,3412和4123四个线排列. 一般地, 一个r-圆排列可以得到r个r-排列,于是 ⊙ ;3. n个元素的r-可重排列 前面所讨论的排列中要求没有重复元素. 如果从n个不同的元素中，可重复取r个元素按顺序排列，就是n个元素的r-可重排列(permutation with repetition)，这样的排列个数记为 或U(n, r).;可以这样理解r-可重排列: 先从n个元素中任取一个元素出来排在第一位置, 有n种选取方式. 将其放回后, 再任意取一个元素出来排在第二位置, 也有n种选取方式. 这样一直进行下去, 直到有r个元素排列为止. 因此, 根据乘法原理有 ;4. 有重复元素的全排列 定理8-2 设A1, A2, …, Ak是k个不同元素，现有ni个Ai元素(i = 1, 2, …, k, n1 + n2 + … + nk = n), 即 (可重集) 则这n个元素的全排列个数为 ;Proof 记这n个可重元素的全排列个数为N. 将ni个Ai元素看作不同的元素 于是得到n1 + n2 + … + nk = n个不同元素，其全排列个数为n!. 由于ni个不同的元素的全排列个数为ni! (i = 1,2,…,k),于是所给n个可重元素的一个全排列可以得到n1! n2! … nk!个n个不同元素的全排列, 根据乘法原理知N ·n1! n2! … nk! = n!，进而;2 组合 1. n个元素的r-组合 从n个不同的元素中, 取r个出来放成一堆而不考虑其顺序, 就是n个元素的r-组合(combination), 其组合个数记为 或 或C(n, r). 上面的三个组合个数的记号都是标准的, 但 和 容易混淆. ;约定当r n时, ；同时约定, 由于一个r-组合可以得到r!个r-排列，根据乘法原理有下述结论. 定理8-3 ;2. n个元素的r-可重组合 如果从n个不同的元素中, 可重复地取r个元素而不考虑其顺序, 就是n个元素的r-可重组合(combination with repetition)，这样的组合个数记为 或F(n, r). 定理8-4 Remark 一一对应是组合计数常用的解题技巧之一. ;证(Euler证法) 不妨设n个不同元素分别为1, 2, …, n. 可重复选取的r个元素为c1, c2, … , cr, 可设c1≤c2≤…≤cr. 记d1 = c1, d2 = c2+ 1, … , dr = cr+ (r - 1), 于是得到另外一个组合d1, d2, … , dr. 显然, 是{c1, c2, … , cr}到{d1, d2, … , dr}的一一对应, 于是组合c1, c2, … , cr的个数与组合d1, d2, … , dr的个数相同. 而组合d1, d2, … , dr是在1, 2, …, n, n + 1, …, n + (r - 1)这n + r – 1个不同的元素的r-组合, 其个数为;容易证明, n个元素的r-可重组合个数与不定方程 的非负整数解的个数相同. 利用这一点, 可以证明：若n个元素的r-可重组合中每个元素至少出现一次, 则r ≥ n且这样的组合个数为 例8-1 从为数众多的一元币、五元币、十元币、五十元币和一百元币中选取6张出来，有多少种选取方式？ ;Solution 根据题意, 就是从5个不同的元素中, 可重复地取6个元素而不考虑其顺序的6-可重组合, 其组合个