作者hb13256 (*)
看板Math
標題Re: [機統] 是我高中沒學好嗎？
時間Wed Jan 5 15:05:36 2011
※ 引述《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
1F：推 XII :a_n=Σ_{k>0}(k^n/2^{k+1}) (如果不想算遞迴的話) 01/05 16:15
2F：推 yhliu :推原 po 的遞迴關係. 01/05 16:46
3F：推 thisday :水喔 01/05 20:23
4F：→ thisday :一樓是怎麼算的呀? 01/05 20:24
5F：推 kzvito :精彩~可以解讀成一直取第一名，直到取完全部九人嗎？ 01/05 22:46
6F：→ hb13256 :我是這樣解讀 如果只有一個第一名 01/06 00:09
7F：→ hb13256 :剩下八個人內的第一名 就是第二名 其餘依此類推 01/06 00:10