151223(3)

Ruby

郵便切手の問題(3)

チェックはup_check しかしないときを考えたが、
その一般化を考えてみた。
なお、コード中のtest_intersect(ary, k) は

http://ja.stackoverflow.com/questions/20262/%E5%90%8C%E3%81%98%E6%95%B0%E5%90%8C%E5%A3%AB%E5%B7%A6%E3%81%8B%E3%82%89%E9%A0%86%E3%81%AB%E7%B7%9A%E3%81%A7%E7%B5%90%E3%82%93%E3%81%A0%E3%81%A8%E3%81%8D-%E4%BA%A4%E7%82%B9%E3%81%8C%E3%81%A7%E3%81%8D%E3%82%8B%E3%81%8B%E5%90%A6%E3%81%8B%E3%81%AE%E5%88%A4%E5%AE%9A%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6
のunarist さんの回答が元です。

def test_intersect(ary, k)
  ary.inject([]){|stack, i| stack.last == i ? stack[0..-2] : stack += Array.new(k - 1, i)} == []
end

def up_check(ary, k)
  ary1 = ary.map{|i| (i + k - 1) / k}
  test_intersect(ary1, k)
end

def f(n, k)
  cnt = 0
  (2..n).to_a.permutation(n - 1){|c|
    c = [1] + c
    cnt += 1 if up_check(c, k)
  }
  cnt
end

(1..6).each{|i| p f(2 * i, 2)}
(1..4).each{|i| p f(3 * i, 3)}
(1..3).each{|i| p f(4 * i, 4)}

出力結果
1
4
40
672
16128
506880
2
36
1728
142560
6
576
152064

この結果を調べると次のようになる。
1 = 1
4 = 2 * (2!)^1 * 1!
40 = 5 * (2!)^2 * 2!
672 = 14 * (2!)^3 * 3!
16128 = 42 * (2!)^4 * 4!
506880 = 132 * (2!)^5 * 5!
2 = 1 * 2!
36 = 3 * 2! * (3!)^1 * 1!
1728 = 12 * 2! * (3!)^2 * 2!
142560 = 55 * 2! * (3!)^3 * 3!
6 = 1 * 3!
576 = 4 * 3! * (4!)^1 * 1!
152064 = 22 * 3! * (4!)^2 * 2!

151123分でも書いたが、
原点(0, 0) から点(i, j) への最短経路で対角線を超えないものを
i x j 格子点上のDyck path といい、その個数をC(i, j) と書く。
一般に、
C(mn, n) = binomial((m + 1)n, n) / (mn + 1)
が成り立つ。
これを用いると、、
C((k - 1)i, i) * (k - 1)! * (k!)＾(i - 1) * (i - 1)! となっている。

その理由は次のとおりである。
「１直線上に並ぶki個の点をk個ずつ上側で線で結んで、
それらが互いに交わらないようにする方法の数」
がC((k - 1)i, i)である。
そして、一番左とその仲間には番号1 をふっているが、
それ以外のグループには2～i がふられている。
その番号のふり方が、(k - 1)! * (k!)＾(i - 1) * (i - 1)! 通りあるからである。