组合数学 (三): 排列组合的数学逻辑

怼烎@ 2022-02-14 01:18 599阅读 0赞

### 排列组合的数学逻辑 ###

*  前言
 *  排列
 *   *  圆排列
     *  项链排列
 *  组合
 *   *  n 个相同的小球放到 m 个相同的盒子里
     *   *  允许空盒子
         *  不允许空盒子
     *  n 个不同的小球放到 m 个相同的盒子里
     *   *  不允许空盒子
         *  允许空盒子
     *  n 个相同的小球放到 m 个不同的盒子里
     *   *  允许空盒子
         *  不允许空盒子
     *  n 个不同的小球放到 m 个不同的盒子里
     *   *  允许空盒子
         *  不允许空盒子
 *  总结

# 前言 #

[本系列上一篇博客][Link 1] 讲的是如何用代码实现排列组合, 本篇博客讲的是排列组合的数学逻辑, 类似于高中数学里面排列组合的习题思路.

# 排列 #

## 圆排列 ##

如果 n 个不同的数排成一列, 不同的方案数是  n ! n! n!  
如果 n 个不同的数排成首尾相接的一个环, 比如 n = 3, 分别为 1, 2, 3  
那么  
 \{ 1 , 2 , 3 \} ≡ \{ 2 , 3 , 1 \} ≡ \{ 3 , 1 , 2 \} \\\{1, 2, 3\\\} \\equiv \\\{2, 3, 1\\\} \\equiv \\\{3, 1, 2\\\} \{ 1,2,3\}≡\{ 2,3,1\}≡\{ 3,1,2\}  
也就是说, 每一种排列都有另外的 n - 1 种排列与之等价, 因此不同的方案数公有  n ! / n n! / n n!/n 个  
易知, 如果不是全排列, 那么不同的方案数有  P ( n , r ) r \\frac\{P(n, r)\}\{r\} rP(n,r) 个

## 项链排列 ##

项链排列是在圆排列的**平移等价性**上多了一个**翻转等价性**, 还拿 1, 2, 3 来说,  
 \{ 1 , 2 , 3 \} ≡ \{ 1 , 3 , 2 \} \\\{1, 2, 3\\\} \\equiv \\\{1, 3, 2\\\} \{ 1,2,3\}≡\{ 1,3,2\} (脑补一下三角形水平翻转)  
因此, 项链排列的个数有  P ( n , r ) 2 r \\frac\{P(n, r)\}\{2r\} 2rP(n,r) 个.

# 组合 #

组合比较难. 以下通过放球模型 (即 n 个小球放到 m 个盒子里) 来解释, 根据小球是否相同, 盒子是否相同, 是否允许有空盒子, 一共有八种情况

## n 个相同的小球放到 m 个相同的盒子里 ##

### 允许空盒子 ###

用动态规划做.  
记  d p \[ i \] \[ j \] dp\[i\]\[j\] dp\[i\]\[j\] 表示将  j j j 个小球放入**至多**  i i i 个盒子的方法数 (因为允许空盒子, 所以 i 表示的是最多能放入 i 个盒子).  
然后规定  d p \[ 0 \] \[ j \] = d p \[ 1 \] \[ j \] = d p \[ i \] \[ 1 \] = 1 dp\[0\]\[j\] = dp\[1\]\[j\] = dp\[i\]\[1\] = 1 dp\[0\]\[j\]=dp\[1\]\[j\]=dp\[i\]\[1\]=1, 即如果没有小球, 或者只有 1 个小球, 或者只有一个盒子, 那么方案数都是 1  
然后有一个显然的关系: 如果 i > j, 那么  d p \[ i \] \[ j \] = d p \[ j \] \[ j \] dp\[i\]\[j\] = dp\[j\]\[j\] dp\[i\]\[j\]=dp\[j\]\[j\], 意思是如果盒子的数量比小球多, 那么不论再怎么分, 最多只有 j (小球的个数) 个盒子里面有球, 也就是  d p \[ j \] \[ j \] dp\[j\]\[j\] dp\[j\]\[j\] 表示的值.  
最后是转移方程:  
 d p \[ i \] \[ j \] = d p \[ i − 1 \] \[ j \] + d p \[ i \] \[ j − i \] dp\[i\]\[j\] = dp\[i-1\]\[j\] + dp\[i\]\[j-i\] dp\[i\]\[j\]=dp\[i−1\]\[j\]\+dp\[i\]\[j−i\]  
意思是, 将 j 个小球放入**至多** i 个盒子的方案数, 等于将 j 个小球放入至多 i-1 个盒子的方案数( d p \[ i − 1 \] \[ j \] dp\[i-1\]\[j\] dp\[i−1\]\[j\]) + 将 j 个小球放入正好 i 个盒子的方案数( d p \[ i \] \[ j − i \] dp\[i\]\[j-i\] dp\[i\]\[j−i\]).  
这里解释一下为什么正好 i 个盒子的方案数是  d p \[ i \] \[ j − i \] dp\[i\]\[j-i\] dp\[i\]\[j−i\], 假设有 5 个小球和 3 个盒子, 那么如果想让小球正好放入 3 个盒子里, **那么每个盒子至少有一个球**. 所以如果先从小球中拿出 3 个来给每个盒子放入一个球, 那么问题就变成了**将剩下的2个小球随意 (允许空盒子) 放入3个盒子里**, 即  d p \[ i \] \[ j − i \] dp\[i\]\[j-i\] dp\[i\]\[j−i\].  
综上  
 d p \[ i \] \[ j \] = \{ 1 ( i ≤ 1 ∣ ∣ j = 1 ) d p \[ j \] \[ j \] ( i > j ) d p \[ i − 1 \] \[ j \] + d p \[ i \] \[ j − i \] ( o t h e r ) dp\[i\]\[j\]=\\left\\\{ \\begin\{aligned\} 1 &&(i \\le1 || j=1)\\\\ dp\[j\]\[j\] && (i > j)\\\\ dp\[i-1\]\[j\] + dp\[i\]\[j-i\] &&(other) \\end\{aligned\} \\right. dp\[i\]\[j\]=⎩⎪⎨⎪⎧1dp\[j\]\[j\]dp\[i−1\]\[j\]\+dp\[i\]\[j−i\](i≤1∣∣j=1)(i>j)(other)

### 不允许空盒子 ###

将  j j j 个小球放入  i i i 个盒子 (不允许空盒子) 的方案数等于将  j j j 个小球放入  j − i j-i j−i 个盒子的方案数, 即上式中的  d p \[ i \] \[ j − i \] dp\[i\]\[j-i\] dp\[i\]\[j−i\].

## n 个不同的小球放到 m 个相同的盒子里 ##

也是用动态规划, 和上述的情况类似, 只是稍微复杂一点. 先从不允许空盒子说起;

### 不允许空盒子 ###

记  d p n o t   e m p t y \[ i \] \[ j \] dp\_\{not\\space empty\}\[i\]\[j\] dpnot empty\[i\]\[j\] 表示 j 个小球 **恰好 (不允许空盒子)** 放入 i 个盒子的方案数.  
显然  d p n o t   e m p t y \[ j \] \[ j \] = 1 dp\_\{not \\space empty\}\[j\]\[j\] = 1 dpnot empty\[j\]\[j\]=1,  d p n o t   e m p t y \[ 1 \] \[ j \] = 1 dp\_\{not \\space empty\}\[1\]\[j\] = 1 dpnot empty\[1\]\[j\]=1  
更一般地, 有转移方程:  
 d p n o t   e m p t y \[ i \] \[ j \] = i × d p n o t   e m p t y \[ i \] \[ j − 1 \] + d p n o t   e m p t y \[ i − 1 \] \[ j − 1 \] dp\_\{not \\space empty\}\[i\]\[j\] = i \\times dp\_\{not \\space empty\}\[i\]\[j-1\] + dp\_\{not \\space empty\}\[i-1\]\[j-1\] dpnot empty\[i\]\[j\]=i×dpnot empty\[i\]\[j−1\]\+dpnot empty\[i−1\]\[j−1\]  
解释一下, 将  j j j 个小球放入  i i i 个盒子里的方案数是一下两种情况的和:

1.  先将前  j − 1 j-1 j−1 个小球放入  i i i 个盒子, 然后将最后一个小球放入任意一个盒子 (一共有 i 种可能)
2.  将前  j − 1 j-1 j−1 个小球放入  i − 1 i-1 i−1 个盒子, 最后一个小球单独放一个盒子

综上, 有  
 d p n o t   e m p t y \[ i \] \[ j \] = \{ 0 ( i > j ) 1 ( i = j ∣ ∣ i = = 1 ) i × d p n .   e . \[ i \] \[ j − 1 \] + d p n .   e . \[ i − 1 \] \[ j − 1 \] ( o t h e r ) dp\_\{not\\space empty\}\[i\]\[j\]=\\left\\\{ \\begin\{aligned\} 0 && (i > j) \\\\ 1 && (i = j || i == 1)\\\\ i \\times dp\_\{n. \\space e.\}\[i\]\[j-1\] + dp\_\{n. \\space e.\}\[i-1\]\[j-1\] && (other) \\end\{aligned\} \\right. dpnot empty\[i\]\[j\]=⎩⎪⎨⎪⎧01i×dpn. e.\[i\]\[j−1\]\+dpn. e.\[i−1\]\[j−1\](i>j)(i=j∣∣i==1)(other)

### 允许空盒子 ###

同样地, 记  d p \[ i \] \[ j \] dp\[i\]\[j\] dp\[i\]\[j\] 表示将  j j j 个小球放入**至多**  i i i 个盒子的方法数.  
有  d p \[ 1 \] \[ j \] = 1 dp\[1\]\[j\] = 1 dp\[1\]\[j\]=1  
如果 i > j, 那么  d p \[ i \] \[ j \] = d p \[ j \] \[ j \] dp\[i\]\[j\] = dp\[j\]\[j\] dp\[i\]\[j\]=dp\[j\]\[j\]  
一般情况的转移方程:  
 d p \[ i \] \[ j \] = d p \[ i − 1 \] \[ j \] + d p n o t   e m p t y \[ i \] \[ j \] dp\[i\]\[j\] = dp\[i-1\]\[j\] + dp\_\{not\\space empty\}\[i\]\[j\] dp\[i\]\[j\]=dp\[i−1\]\[j\]\+dpnot empty\[i\]\[j\]  
综上, 有  
 d p \[ i \] \[ j \] = \{ 1 ( i = 1 ) d p \[ j \] \[ j \] ( i > j ) d p \[ i − 1 \] \[ j \] + d p n o t   e m p t y \[ i \] \[ j \] ( o t h e r ) dp\[i\]\[j\]=\\left\\\{ \\begin\{aligned\} 1 && (i = 1) \\\\ dp\[j\]\[j\] && (i > j) \\\\ dp\[i-1\]\[j\] + dp\_\{not\\space empty\}\[i\]\[j\] &&(other) \\end\{aligned\} \\right. dp\[i\]\[j\]=⎩⎪⎨⎪⎧1dp\[j\]\[j\]dp\[i−1\]\[j\]\+dpnot empty\[i\]\[j\](i=1)(i>j)(other)

## n 个相同的小球放到 m 个不同的盒子里 ##

### 允许空盒子 ###

公式:  C n + m − 1 n C\_\{n+m-1\}^n Cn\+m−1n  
解释: 这个问题等价于将小球划分成 m 份的方案数, 通过**隔板法**来解决:  
因为要划分成 m 份所以需要 m-1 个隔板  
因为允许有空盒子, 说明隔板之间没有约束关系, 因为小球和隔板放到一起一共有 n+m-1 个位置, 因此 **隔板一共有 n+m-1 个可能的位置**  
所以方案数就是从这些可能的位置中选取 m-1 个隔板 (或者 n 个小球, 二者等价)

### 不允许空盒子 ###

公式:  C n − 1 m − 1   ( m < = n ) C\_\{n-1\}^\{m-1\} \\space (m <= n) Cn−1m−1 (m<=n)  
解释: 这个问题和上一种情形的关系的区别是, 隔板的位置有约束, 即每两个隔板之间必须至少有一个小球. 这样的话可以使用 **插空法**, 因为一共有 n-1 个空隙, 只要在这其中选取任意 m-1 个位置作为隔板, 那么肯定不会出现空盒子.

## n 个不同的小球放到 m 个不同的盒子里 ##

### 允许空盒子 ###

公式:  m n m^n mn  
解释: 因为每一个小球都有 m 种放法, 彼此互不影响; 一共 n 个小球, 所以一共是  m n m^n mn 种方法.

### 不允许空盒子 ###

此时必定  m ≤ n m \\le n m≤n, 否则方案数为 0  
用动态规划,  d p \[ i \] \[ j \] dp\[i\]\[j\] dp\[i\]\[j\] 表示将 j 个小球放入 i 个盒子里, 有  
 d p \[ j \] \[ j \] = j ! dp\[j\]\[j\] = j! dp\[j\]\[j\]=j!  
更一般地, 有转移方程  
 d p \[ i \] \[ j \] = i × ( d p \[ i \] \[ j − 1 \] + d p \[ i − 1 \] \[ j − 1 \] ) dp\[i\]\[j\] = i \\times (dp\[i\]\[j-1\] + dp\[i-1\]\[j-1\]) dp\[i\]\[j\]=i×(dp\[i\]\[j−1\]\+dp\[i−1\]\[j−1\])  
解释一下:  d p \[ i \] \[ j − 1 \] dp\[i\]\[j-1\] dp\[i\]\[j−1\] 表示的是将除了最后一个球以外的所有球放到 i 个不同的盒子的方案数, 此时最后一个球可以放到  i i i 个盒子中的任何一个盒子上, 因此是  i × d p \[ i \] \[ j − 1 \] i \\times dp\[i\]\[j-1\] i×dp\[i\]\[j−1\]. 当然也可以将最后一个球单独放到一个盒子里, 将剩下的  j − 1 j-1 j−1 个球放入到剩下的  i − 1 i-1 i−1 个盒子里, 因此是  i × d p \[ i − 1 \] \[ j − 1 \] i \\times dp\[i-1\]\[j-1\] i×dp\[i−1\]\[j−1\].  
综上  
 d p \[ i \] \[ j \] = \{ 0 ( i > j ∣ ∣ i = 0 ) j ! ( i = j ) i × ( d p \[ i − 1 \] \[ j \] + d p \[ i − 1 \] \[ j − 1 \] ) ( o t h e r ) dp\[i\]\[j\]=\\left\\\{ \\begin\{aligned\} 0 && (i > j || i = 0) \\\\ j! && (i = j) \\\\ i \\times (dp\[i-1\]\[j\] + dp\[i-1\]\[j-1\]) && (other) \\end\{aligned\} \\right. dp\[i\]\[j\]=⎩⎪⎨⎪⎧0j!i×(dp\[i−1\]\[j\]\+dp\[i−1\]\[j−1\])(i>j∣∣i=0)(i=j)(other)

# 总结 #

脑子疼.

[Link 1]: https://blog.csdn.net/vinceee__/article/details/89203212