一般, k 種物, 任意組合裝箱, 每箱 n 件, 則方法數 = C(n+k-1,k-1). 求過程 謝謝!?

2020-11-18 11:13 pm

回答 (1)

2020-11-19 5:09 am
這是針對前一問的補充問題? 其實在前一問題做
發問之修改就可以了.

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).


收錄日期: 2021-05-04 02:32:50
原文連結 [永久失效]:
https://hk.answers.yahoo.com/question/index?qid=20201118151312AA4CwAp

檢視 Wayback Machine 備份