組合數學：可重複組合數（隔板法）通用公式推導

問題：n 個不同元素，取 m 個（可重複），有多少種組合？

例：{0,1,2} 取 3 個，共 10 種：
{0,0,0}, {0,0,1}, {0,0,2}, {0,1,1}, {0,1,2}, {0,2,2}, {1,1,1}, {1,1,2}, {1,2,2}, {2,2,2}

隔板法直觀推導

1. 想像有 m 顆相同的球（代表取的次數）。
2. 用 n-1 根隔板 將球分成 n 組（對應 n 個元素）。
3. 球與隔板總共 m + n - 1 個位置，選 n-1 個位置放隔板（或選 m 個位置放球）。

因此組合數為：

C(m + n - 1, n - 1) = C(m + n - 1, m)

驗證例子

• n=3, m=3 → C(5,2) = 10 ✅
• n=5, m=2 → C(6,4) = 15

對應關係示意

元素:   0     1     2
取數:   2     0     1   → 球球 | 空 | 球
排列:   ● ● |   | ●
位置:   共 5 個位置，選 2 個放隔板

程式碼實現（計算組合數）

// 避免溢位：迭代相乘除以階乘
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;
}

// 可重複組合數
long long combinationWithRepetition(int n, int m) {
    return comb(n + m - 1, m);
}

擴展：生成所有組合（遞迴/迭代）

void gen(int n, int m, int start, List cur, List> ans) {
    if (cur.size() == m) { ans.add(new ArrayList<>(cur)); return; }
    for (int i = start; i < n; i++) {
        cur.add(i);
        gen(n, m, i, cur, ans); // i 不變 → 允許重複
        cur.remove(cur.size() - 1);
    }
}

隔板法將「可重複組合」轉化為經典「不重複組合」，是組合數學中最優雅的技巧之一。