151223(2)

Ruby

郵便切手の問題(2)

チェックはup_check しかしないときの偶数項を出力してみる。

# 切手が貫通していないか
def test_intersect(ary)
  ary.inject([]){|stack, i| stack.last == i ? stack[0..-2] : stack << i} == []
end

def up_check(ary)
  ary1 = ary.map{|i| (i + 1) / 2}
  # ary1.delete((ary.size + 1) / 2) if ary.size % 2 == 1
  test_intersect(ary1)
end

def f(n)
  cnt = 0
  (2..n).to_a.permutation(n - 1){|c|
    # 左が一番上
    c = [1] + c
    if up_check(c)
      cnt += 1
    end
  }
  cnt
end

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

出力結果
1
4
40
672
16128
506880

この結果を調べると次のようになる。
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!

C(i) をカタラン数とすると、
C(i) * 2＾(i - 1) * (i - 1)! となっている。

その理由は次のとおりである。
「１直線上に並ぶ2i個の点を２つずつ上半平面の弧で結んで、
それらが互いに交わらないようにする方法の数」
がC(i)である。
そして、一番左とその片割れには番号1 をふっているが、
それ以外のペアには2～i がふられている。
その番号のふり方が、2＾(i - 1) * (i - 1)! 通りあるからである。