這是針對前一問的補充問題? 其實在前一問題做
發問之修改就可以了.
k 種物, 可重複, 且無限; 裝箱每箱 n 件, 不限物種.
設第一種物裝 x_1 件, 第二種物 x_2 件, 以此類推.
裝箱要求是每箱 n 件, 即是
x_1 + x_2 + ... + x_k = n
其中所有 x_i 都是非負整數.
一般把原裝箱問題, 或解非負整數解數的方法稱
"重複組合". 不過我個人不喜歡重複組合, 而習慣
把非負整數解問題變成正整數解問題:
令 y_i = x_i + 1, for all i. 則上述非負整數解問題
等價於正整數解問題:
y_1 + y_2 + ... + y_k = n + k
所有 y_i 都是正整數.
正整數解問題
y_1 + y_2 + ... + y_k = N
相當於於把 N 個相同物排列後切割 (劃分) 成 k 部
分, 第一部分的件數是 y_1, 第二部分是 y_2, 以此
類推. 這又相當於在 N-1 個可切割點選取 k-1 個.
所以其方法數是 C(N-1,k-1); 在前述裝箱問題就是
C(n+k-1,k-1). 也就是就: k 種物, 可重複, 取 n 件,
這樣的重複組合數是
H(k,n) = C(k+n-1,n) = C(n+k-1,k-1).