カタラン数を計算してみる

Ruby F# Snippet

　F#で書いてみたカタラン数は何処かバグっているようで、試しにRubyで書いたらまあ普通に期待値帰ってきたｗ−

世界に整数数値型*1のみならF#でも動くはず*2なのだが？

カタラン数とは

気に入ったのは、凸角形の三角形分割の組み合わせ数と一致するとの事。

Rubyでカタラン数

$ ruby catalan.rb
1
2
6
1
3
3
[1, 1]
[2, 2]
[3, 5]
[4, 14]
[5, 42]
[6, 132]
[7, 429]
[8, 1430]
[9, 4862]
[10, 16796]
[11, 58786]
[12, 208012]
[13, 742900]
[14, 2674440]
[15, 9694845]

def fact n
<<EOS
  if n == 0
    1
  else
    n * fact(n-1)
  end
EOS
  (1..n).inject(:*) || 1
end

def comb(n, r)
  fact(n) / (fact(r) * fact(n-r))
end

def catalan n
  case n
  when 0 then 1
  else
    comb(2*n, n) - comb(2*n, n-1)
  end
end

puts fact 0
puts fact 2
puts fact 3

puts comb 3, 0
puts comb 3, 1
puts comb 3, 2

(1..15).each{|i|
  p [i,catalan(i)]
}

F#の場合

  • rev1: int32で駄目
  • rev2: int64にしたけどfactorial 21でオーバーフローしているのでbitintにしないとイケないか
    • todo
  • rev3: bigint版
    • todo

*1:int64ではどこかで精度が足りてないのだろうか？

*2:なんかまたポカミスしてる気がするのだｗ−