組合數學 (三): 排列組合的數學邏輯

排列組合的數學邏輯

• 前言
• 排列
• • 圓排列
  • 項鍊排列
• 組合
• • 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)​

總結

腦子疼.