Re: [中學] 排列組合問題
※ 引述《zephyrhymn (是)》之銘言：
(內文略)
: 若是不用遞迴解而是用重複組合數公式有沒有辦法算出?
排列 組合 重複組合公式能解的題目沒有遞迴多
因為遞迴本質上是divide and conquer
一個方法是 先假設n個骰子會丟出 N 點
因此 x_1 + x_2 + ... + x_n = N
x_i 下限是 1 不考慮上限有 H(n, N-n) = C(N-1, n-1) 種排法
n
考慮上限是 6 的話是 sum (-1)^j C(n, j) H(n, N-n-6j) (排容原理)
j=0
n
= sum (-1)^j C(n, j) C(N-1-6j, n-1)
j=0
方便起見設 C(m, n) = 0 if n > m or n < 0
所以N不大的話其實不會很多項
N n
因此總共有 sum sum (-1)^j C(n, j) C(N-1-6j, n-1) 種可能
n=0 j=0
N N
= sum sum (-1)^j C(n, j) C(N-1-6j, n-1)
j=0 n=j
N N-5j
= sum (-1)^j ------ C(N-6j, j) 2^(N-1-7j)
j=0 N-6j
(實際上 j > N/7 的時候C就是0了 沒那麼多項)
嘛 老實說我不確定這樣對不對 也懶得檢查(欸)
倒數兩行的sum公式是靠wolframalpha爆出來的 最後一個sum不覺得化簡的了
總之 遞迴好用又簡單 用遞迴吧ow o
--
嗯嗯ow o
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.105
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1499078582.A.C2B.html
推
07/03 20:21, , 1F
07/03 20:21, 1F
推
07/03 20:36, , 2F
07/03 20:36, 2F
討論串 (同標題文章)