150503(3)

Ruby


| σ(i + 1) - σ(1) | ≠ 1 を満たすσの個数

σをSnの要素とし、

1 ≦ i ≦ n - 1 に対し、| σ(i + 1) - σ(1) | ≠ 1 を満たす

ものの個数を求めるコードを書いてみた。
（150503(2)のコードと比べ物にならないくらい速い。
　なお、c(-1, -1) = 1 としていますが、「コンピュータの数学」5.1
　に書いてあるように本来は n < 0 のとき、c(n, n) = 0 です。）

オンライン整数列大辞典の
A002464（http://oeis.org/A002464/list）
と比較し、答え合わせしてみる。

def c(m, n)
  return 1 if m == n
  return 0 if m < n
  return 0 if n < 0
  return 1 if n == 0
  n = m - n if n > m - n
  return (m - n + 1..m).inject(:*) / (1..n).inject(:*)
end

N = 23

ary = [1]

(1..N).each{|n|

  cnt1 = 0

  (0..n - 1).each{|r|

    cnt2 = 0

    (0..r).each{|c|

      cnt2 += 2 ** c * c(r - 1, c - 1) * c(n - r, c)

    }

    cnt1 += (-1) ** r * (1..n - r).inject(:*) * cnt2

  }

  ary << cnt1

}

# OEIS A002464のデータ

ary0 =

[1,1,0,0,2,14,90,646,5242,47622,479306,5296790,

 63779034,831283558,11661506218,175203184374,

 2806878055610,47767457130566,860568917787402,

 16362838542699862,327460573946510746,

 6880329406055690790,151436547414562736234,

 3484423186862152966838]

# 一致の確認

p ary == ary0