210403

Ruby


Number of tilings of a <n,k,n> hexagon

一般化された二項係数を利用し計算してみた。

def ncr(n, r)
  return 1 if r == 0
  (n - r + 1..n).inject(:*) / (1..r).inject(:*)
end

# generalized binomial coefficient (n,r)_m
def g_ncr_m(n, r, m = 1)
  # to_rとto_iは念のため
  (1..r).inject(1){|s, i| s * ncr(n - i + m, m) / ncr(i - 1 + m, m).to_r}.to_i
end

n = 10
(0..n).each{|i|
  p [i, (0..5).map{|j| g_ncr_m(i + j, i, i)}]
}

出力結果

[0, [1, 1, 1, 1, 1, 1]]

[1, [1, 2, 3, 4, 5, 6]]

[2, [1, 6, 20, 50, 105, 196]]

[3, [1, 20, 175, 980, 4116, 14112]]

[4, [1, 70, 1764, 24696, 232848, 1646568]]

[5, [1, 252, 19404, 731808, 16818516, 267227532]]

[6, [1, 924, 226512, 24293412, 1447482465, 55197331332]]

[7, [1, 3432, 2760615, 877262100, 142174944340, 13710834632352]]

[8, [1, 12870, 34763300, 33803832920, 15484613937936, 3940599631842016]]

[9, [1, 48620, 449141836, 1371597504992, 1832516612010448, 1274867710694037824]]

[10, [1, 184756, 5924217936, 58043512597616, 232187445047217296, 454924095627897307776]]