151004

Ruby

Number of permutations of the multiset {1,1,2,2,....,n,n} with no two consecutive terms equal(1)

オンライン整数列大辞典の

A114938（http://oeis.org/A114938/list）

と比較し、答え合わせしてみる。

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

def f(n)
  s = 0
  # 包除原理を使用
  (0..n).each{|i| s += (-1) ** i * ncr(n, i) * (1..2 * n - i).inject(:*) / 2 ** (n - i)}
  s
end

def A114938(n)
  (1..n).map{|i| f(i)}
end
ary = A114938(16)

# OEIS A114938のデータ
ary0 =
[0,2,30,864,39480,2631600,241133760,29083420800,
 4467125013120,851371260364800,197158144895712000,
 54528028997584665600,17752366094818747392000,
 6720318485119046923315200,
 2927066537906697348594432000,
 1453437879238150456164433920000]
# 一致の確認
p ary == ary0