作者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