Re: [機統] 是我高中沒學好嗎？

[hb13256 (*)]

※ 引述《kzvito (HOW)》之銘言：
: Q: 今天有九名跑者，跑到終點以後記錄他們的名次。
: 已知同名次有可能不止一人(如兩個第二名，甚至大家都跑一樣快就九個第一)，
: 若不同人得到相同名次仍算另一種組合，
: 在合理的名次組合下(所以不會有九個第五名，或是沒有第一名等等的情況)，
: 會有多少種組合呢？
: 因為原po在寫程式，
: 跑的式子大致上可以舉這樣的比喻，
: 目前原po想到一個一個算，
: 但是連這種方法我都不會有條理地算 T^T
: 所以主要倒不是想知道答案，而是想請問便於運算的原理
: <(_ _)>
: 感謝大家

假設n個人排名 組合數共有an種

若恰有1個第一名 C(n,1)  其餘n-1人排名組合數an-1種

若恰有2個第一名 C(n,2)  其餘n-2人排名組合數an-2種

...

若恰有k個第一名 C(n,k)  其餘n-k人排名組合數an-k種

則an= C(n,1)*(a(n-1)) + C(n,2)*(a(n-2)) + ... + C(n,n-1)*(a1) + C(n,n) 


已知a1=1
    a2=C(2,1)*a1 + C(2,2)=3
    a3=C(3,1)*a2 + C(3,2)*a1 + C(3,3) = 13
    a4=C(4,1)*a3 + C(4,2)*a2 + C(4,3)*a1 +C(4,4) = 75
    ....
    a9=7087153 (如果我沒key錯的話)




--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 163.30.43.1
推 XII         :a_n=Σ_{k>0}(k^n/2^{k+1}) (如果不想算遞迴的話)
推 yhliu       :推原 po 的遞迴關係.
推 thisday     :水喔
→ thisday     :一樓是怎麼算的呀?
推 kzvito      :精彩~可以解讀成一直取第一名，直到取完全部九人嗎？
→ hb13256     :我是這樣解讀  如果只有一個第一名
→ hb13256     :剩下八個人內的第一名 就是第二名 其餘依此類推