Re: [理工] [離散] 99台科

[cksh3300110 (123)]

※ 引述《cksh3300110 (123)》之銘言：
: ※ 引述《sroeud7l (Teddy Bear)》之銘言：
: : 6. [6%] How many ways are there to pack eight identical DVDs into five
: : indistinguishable
: : boxes so that each box contains at least one DVD? Explain why the answer you
: : have.
: : 即求S(8,5)是嗎?
: s(m,n)是用來分相異物分相同箱
: 這題是相同物分相同箱的問題
: 即是求整數的無序分割
: 因為數字很小所以直接窮舉即可 注意每各箱子至少一個 且是無序分割
: 4 1 1 1 1
: 3 2 1 1 1
: 2 2 2 1 1
: 所以三種

S(m,n) 是用在相異物放相同箱

遞迴式如下

S(m,1)=1

S(m,2)=2^(m-1)-1

S(m,n)=n*S(m-1,n)+S(m-1,n-1)
           m
S(m,m-1)= ( )
           2
S(m,m)=1

用來算等價關係非常好用~

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 219.71.13.246
推 annheilong:S(m,3)=3*S(m-1,3)+S(m-1,2) S(m-1,3)還是不會?
→ cksh3300110:你說的對啊 S(m-1,3)=3S(m-2,3)+S(m-2,2)繼續地迴算
推 annheilong:哦哦~最後會看到3S(3,3)+S(2,3)=3*1+1=4?
→ cksh3300110:S(2,3)?!  看你m,n代的值是啥      還有S(m,n)不可空
推 annheilong:阿...原來到S(4,3)就是6了 所以S(m,n)是n個物到m個箱?
→ cksh3300110:@_@ m個物到n個箱 且每箱不可空
推 annheilong:啊啊啊... 一路錯啊XD 謝謝cksh大了~