算法分析：N 個蘋果放入 N 個盤子的放法數——組合數學經典模型

經典組合問題：N 個完全相同的蘋果，放入編號 1~N 的 N 個盤子（容量無限），問共有多少種放法？本文從遞歸建模到數學歸納法證明，推導出閉式解 C(2N-1, N)。

問題建模與遞歸關係

設 F(i, j) 表示 i 個蘋果放入 j 個盤子的放法數。聚焦第 1 號盤子：

• 0 個蘋果 → 剩餘 i 個放入 j-1 個盤子：F(i, j-1)
• 1 個蘋果 → 剩餘 i-1 個放入 j-1 個盤子：F(i-1, j-1)
• ...
• i 個蘋果 → 剩餘 0 個放入 j-1 個盤子：F(0, j-1)

得遞歸式 ①：

F(i, j) = F(i, j-1) + F(i-1, j-1) + ... + F(0, j-1)

同理 F(i-1, j) 得式 ②：

F(i-1, j) = F(i-1, j-1) + ... + F(0, j-1)

回代得核心遞歸 ③：

F(i, j) = F(i, j-1) + F(i-1, j)

邊界條件

F(i, 1) = 1        // 只有 1 個盤子，全放進去，唯一放法
F(1, j) = j        // 只有 1 個蘋果，選 1 個盤子放，j 種選法

猜想閉式解：組合數

觀察遞歸 ③ 與組合數性質 C(n, k) = C(n-1, k) + C(n-1, k-1) 結構相似，猜想：

F(i, j) = C(i, i+j-1)  // 即從 i+j-1 個位置選 i 個

數學歸納法證明

1. 基礎驗證：
   • F(i, 1) = C(i, i) = 1 ✓
   • F(1, j) = C(1, j) = j ✓
2. 歸納假設： 假設 F(i, j-1) = C(i, i+j-2)、F(i-1, j) = C(i-1, i+j-2) 成立。
3. 歸納步驟：

   F(i, j) = F(i, j-1) + F(i-1, j)
           = C(i, i+j-2) + C(i-1, i+j-2)
           = C(i, i+j-1)          // 組合數遞歸性質
   

   成立。故公式對所有 i, j ≥ 1 成立。

最終公式與數值驗證

F(N, N) = C(N, 2N-1)

組合意義直觀理解

「N 個相同物放入 N 個盒子」等價於「在 2N-1 個間隙中選 N 個放隔板」，或「N 個 ★ 和 N-1 個 | 排列」，本質是可重複組合（Stars and Bars 定理）：

H(n, k) = C(n+k-1, k) = C(n+k-1, n-1)

程式實現提示

// 計算 C(n, k) 避免溢出
long long comb(int n, int k) {
    if (k > n-k) k = n-k;
    long long res = 1;
    for (int i = 1; i <= k; i++) {
        res = res * (n - k + i) / i;
    }
    return res;
}

// N蘋果N盤子
long long ways(int N) { return comb(2*N - 1, N); }

結語

此問題完美展示了「遞歸建模 → 猜想閉式 → 數學歸納證明 → 組合意義解釋」的算法分析完整鏈路。掌握 Stars and Bars 模型，可秒殺大類「相同物放入不同盒」變體問題。