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

排列组合的数学逻辑

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

前言

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

排列

圆排列

如果 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 &lt; = n ) C_{n-1}^{m-1} \space (m &lt;= 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 &gt; 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 &amp;&amp; (i &gt; j || i = 0) \\ j! &amp;&amp; (i = j) \\ i \times (dp[i-1][j] + dp[i-1][j-1]) &amp;&amp; (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)​

总结

脑子疼.