# -*- coding: utf-8 -*-
# http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2015
#
# まず最短経路を進む場合，スタートからゴールへの距離は
# 常に(0,0)から(20,20)へのマンハッタン距離になり
# |0 - 20| + |0 - 20| = 40
# である．
# また40回進むうち必ず右に20回進み，右に進まない場合は必ず下に進むことになる．
#
# ここで形式的で分かりやすい問題に変換してみる．
#
# 右に進める赤色の石が20個と下に進める青色の石が20個の計40個の石がある．
# これらの石を一列に並べたときの石の並び方の見た目はいくつあるか．
#
# 全ての石を区別した場合，順列の数は40!となる．
# 20個の赤色の石と20個の青色の石は同じ見た目の区別がないため
# 重複順列の総和
#  40! / (20! * 20!)
# がルートの数となる.
def fact(n)
  (1 .. n).reduce(:*)
end
puts fact(40) / (fact(20) * fact(20))