鍋あり谷あり

テーマを決めずに適当に書いています。

ダイスで組分けもう一回

あれからだいぶ考え、もっとずっと速く計算する方法を思いついた。

require 'rational'

N=6

def perm(a,b)
  (0..b-1).inject(1){|r,i|
    r * (a-i)
  }
end

def combi(a,b)
  ((b+1)..a).inject(1){|r,i|
    r * i / (i-b)
  }
end

def count(n)
  (1..[N,n].min).inject(0){|sum,i|
    sum + perm(N,i) * (N-i)**(n-i) * combi(n,i) * [-1,1][i%2]
  }
end

(1..ARGV[0].to_i).each{|i|
  r=Rational( count( i ), N**i )
  puts "#{i} : #{r.to_f} == #{r}"
}  

これなら、300人の場合も一瞬で計算できる。多倍長整数万歳!

[-1,1][i%2]

は、(-1)**(i+1) でも i%2==0?-1:1 でも 1-i%2*2 でもよかったんだが、配列にしてみた。
こういうとき他の方々はどうしてるんだろと思ったり。