[Combinatorial] 2 小乒乓球的组合之旅

2 小乒乓球的组合之旅

• 2-1 加减乘除来计数 计数的基本法则
  • 1.1 加法法则与乘法法则
    • 加法法则: 分类
    • 乘法法则: 分步
  • – 事件独立性，隐含条件
• 2-2 点兵点将 排列组合定义
  • 乒乓球放盒子
    • 编号的乒乓球：
      • – 4个乒乓球：1号，2号，3号，4号
      • – 取出其中的3个
      • –如果考虑顺序，则称之为排列数 P(4,3) • P(4,3)=4×3×2 = 24
      • –如果不考虑顺序，则称之为组合数 C(4,3) • C(4,3)=24/3！=4
  • 排列和组合
    • [排列 Permutation]从n个不同的元素中，取r个不重复的元素，按次序排列，称为从n个中取r个的无重排列。排列的个数用P(n,r)表示。当r=n时称为全排列。 一般不说可重即无重。 (n ≥ r)
    • [组合 Combination]从n个不同元素中取r个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从n个中取r个的无重组合。 (n ≥ r) 组合的个数用C(n,r)表示
  • 排列的模型
    • 从n个中取r个的排列的典型例子是从n个不同的球中,取出r个,放入r个不同的盒子里,每盒1个。(n ≥ r)
    • 排列P(n, r)的递推关系
      • 分步递推
        • – 选No.1盒子内的乒乓球
        • • n种选择
        • – 从n-1个球中选出r-1个放入r-1个 盒子内的排列
        • • P(n-1,r-1)
      • 分类递推
        • – 不选第一个球？
        • • P(n-1,r)
        • – 选择第一个球？
        • • rP(n-1,r-1)
  • 组合的模型
    • 若球不同，盒子相同，则是从n个中取r个的组合的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标号方案。
    • C(n,r)=C(n,n-r)，n个乒乓球中选出r个的方法自然等于剩下n-r个的方法。
    • 格路模型：
    • 从 (0,0)点出发沿x轴或y轴的正方向每步走一个单位，最终走到(m,n)点，其路径数是C(m+n,n).
  • 二项式定理
  • 组合恒等式 Combinatorial Indentities
    • C(n, r)=C(n-1,r)+C(n-1,r-1)
    • C(m+n, r)=C(m,0)C(n, r)+C(m, 1)C(n,r-1)+ …+C(m, r)C(n, 0)， 即Vandermonde恒等式
  • 乒乓球来证明恒等式
• 2-3 小乒乓球的大花样
  • 圆排列
    • 将圆排列剪开：从n个中取r个的圆排列的排列数为 P(n,r)/r , 2≤r≤n
  • 项链排列
    • 排列的方法和项链一样,在圆排列的基础上， 正面向上和反面向上两种方式放置各个数是同一个排列
    • 从n个中取r个的项链排列的排列数为 P(n, r)/2r, 3≤r≤n
  • 可重排列
    • 例 26个英文字母能组成多少4位数的字符串？ 26^4
    • 例 26个英文字母能组成多少4位数的字符串， 其中每位字母都不相同？ P(26,4)
    • 例 26个英文字母能组成多少4位数的字符串， 其中每位字母都不相同且b和d不相邻？ P(26,4) –C(24,2)3!2
      • 减去bd相邻的情况：C(24,2)取出两个字母，3!全排，2为bd和db两种情况
  • 多重全排列
    • 多重排列：
      • 请问“pingpang”8个字母有多少种不同的排列？
      • –2个p, 2个n，2个g，1个i，1个a
    • 解决思路：
      • 加上下标以区别 p1 p2 n1 n2 g1 g2 i a
      • 全排列后除以每种重复字母的冗余度：8!/(2!2!2!)
    • 给出多重排列的定义：
      • 求r1个1，r2个2，…，rt个t的排列数，设r1+r2+…+rt =n, 设此排列数为P(n;r1 ,r2 ,…,rt )
      • P(n;r1 ,r2 ,…,rt )= n!/(r1 !·r2 !·…·rt!)
  • 多项式展开
    • 利用上面的定义
  • 例 乒乓球入洞游戏：
    • 共有6个洞，洞口每次只能进入一个乒乓球，一组编号为1-9的9个乒乓球滚入洞口的方案有多少？（洞很小，是个栈，有顺序）
    • 隔板法
      • [解法1]给每个方案的门标号可产生5!个14 个元的全排列。故若设x为所求方案数，则 x·5!=14! ∴x=14!/5!=726485760
      • [解法2]在14个元的排列中先确定“1”的位置 ，有C(14,5)种选择，再确定球的位置，有9！ 种选择。 故 C(14,5)·9! 即所求
      • [解法3]把全部选择分解成若干步，使每步宜于计 算。 •1号有6种选择； •2号除可有1号的所有选择外，还可（也必须）选 择当与1号同一门时在1号的前面还是后面，故2号 有7种选择； •3号的选择方法同2号，故共有8种 • 。。。。 •以此类推，9号有14种选择。 故所求方案为 678….14 =14!/5!=726485760
• 2-4 多样的组合
  • 可重组合：
    • 从A={1,2,3….n}中取r个元素{a1 ,a2 ,…ar },ai∈A ，i=1,2,..r,且允许ai =aj , i≠j，记为Cbar(n,r)。
    • A={1,2,3,4}中取5个元素构成组合，元素可以重复
    • 可重组合模型：取r个无标志的球，n个有区别的盒子， 每个盒子允许放多于一个球，或者空盒。
    • 无重组合的模型：n个球是有区别的，r个盒子是无区别 的，取r个球放入盒子，每个盒子一个球。
    • 求解方法：构造相关的无重组合
      • 一一对应的方法
        • 我们可以按照盒子的序号1-n ，盒子里有几个球，这个序号就写几次，那么上面的方案就可以表示为
        • 1 1 3 3 4
        • 共有5个数字，我们把它分别加上序号 0 1 2 3 4 就成了
        • 1 2 5 6 8
        • （这样加起来元素值一定是不一样的）
        • 最后的这个序列，我们可以看到 第一个数字最小是1，最后一个数字最大是5+4=9
        • 每一种方案都可以一一对应一个1-9中选出5个数字的无重组合。
      • 我们再来看一下普遍的情况：
        • r个无区别的球，n个有区别的盒子
        • 按照盒子编号1-n，有几个球写几次 可以写出一个r个数字的序列。分别加上0 1 2 …… r-1
        • 结果第一个数字最小是1+0 最大是n+r-1 ，无重组合的个数就是从1到n+r-1中选出r个不重复的数字。
        • 因此，无重组合的公式为：r个无区别的球，n个有区别的盒子 共有 C(n+r-1,r) 种。
      • 隔板法：转为门框分割的问题
        • 可以转化为 r个球，插入n-1个隔板。一共有r+n-1个位置，从中选出r个位置放球。得到结果C(n+r-1,r)
          • 比如说这里A={1,2,3,4}中取5个元素构成组合，就是5个球，3个隔板（分隔出四个区域）
          • 这样就会有5+3个位置，从中选3个隔板放好，搞定
          • （选隔板和选球放好得到的结果是一样的c(n,r)=c(n,n-r)）
        • 感觉隔板法比较方便理解和记忆
  • 线性方程的非负整数解
    • 线性方程x1+x2…+xn=b的非负整数解的个数是C(n+b-1,b)
    • 这相当于b个无区别的球，n个有区别的盒子（x1到xn）
  • 不相邻组合
    • 不相邻的组合是指从A={1,2,…n}中取r个不相邻的数进行组合(不可重)，即不存在相邻的两个数j, j+1的组合
    • 从A={1,2,…n}中取r个不相邻的数进行组合，其组合数为C(n-r+1,r)
    • 可以采用和无重组合类似的一一对应的方法：不同的是这里减去序号0 1 2 3……因为不相邻，所以减去后也是不可能相同的。
  • 应用举例
    • 例 某保密装置须同时使用若干把不同的钥匙才能打开。现有７人，每人持若干钥匙。须４人到场，所备钥匙才能开锁。问
      • ①至少有多少把不同的锁？
      • ②每人至少持几把钥匙？
    • 解
      • ①每３人至少缺１把钥匙，任意4个人都不缺钥匙， 则要求每３人所缺钥匙不同。
      • 如果abc缺的钥匙和abd缺的钥匙一样，那abcd就不能 开门
      • 故至少共有C(7,3)=35把不同的锁。
      • ②任意4个人都不缺钥匙，任一人对于其他６人中的每３人，都至少有１把钥匙与之相配才能开锁。故每人至少持C(6,3) ＝20把不同的钥匙。
      • 为加深理解，举一个较简单的例子:４人中３人到场，才能开锁，所求如上。共有C(4,2)=6把不同的钥匙。每人有C(3,2)=3 把钥匙。
• 2-5 钟声里的全排列
  • 全排列
  • 把所有的排列列举出来就可以生成全排列。全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。
  • 字典序法生成全排列
  • 按照字典中的顺序。可以参考英文字典。
  • 字典中，每个排列有唯一的前驱和后继，相邻排列之间差尽可能的小。
  • 算法实现
  • SJT全排列生成算法
  • 1. 找到最大的可移动数m(当一个数指向一个比它小的数是，该数就是可移动数)
  • 2. 交换m和m所指向的数
  • 3. 改变所有比m大的数的方向
  • 4. 重复上面的步骤，直至找不到可移动数
  • 库函数中的全排列生成函数
  • C++标准程序库中有两个函数next_permutation, prev_permutation，可以生成字典序排列。
  • Stirling公式
  • 全排列的个数可能超出我们的想象。10个字符的全排列有10! = 3628800种。20个字符的全排列有2432902008000000000种。
  • Stirling公式可以用来估计n！的大小。n越大，估计越精确。

以上内容整理于幕布