160104(2)

Ruby


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

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

def C(n, r)
  r = [r, n - r].min
  return 1 if r == 0
  return n if r == 1
  numerator = (n - r + 1..n).to_a
  denominator = (1..r).to_a
  (2..r).each{|p|
    pivot = denominator[p - 1]
    if pivot > 1
      offset = (n - r) % p
      (p - 1).step(r - 1, p){|k|
        numerator[k - offset] /= pivot
        denominator[k] /= pivot
      }
    end
  }
  result = 1
  (0..r - 1).each{|k|
    result *= numerator[k] if numerator[k] > 1
  }
  return result
end

def mul(f_ary, b_ary)
  s1, s2 = f_ary.size, b_ary.size
  ary = Array.new(s1 + s2 - 1, 0)
  (0..s1 - 1).each{|i|
    (0..s2 - 1).each{|j|
      ary[i + j] += f_ary[i] * b_ary[j]
    }
  }
  ary
end

def f(n)
  return 1 if n < 2
  (1..n).inject(:*)
end

def A(a)
  ary = [1]
  a.each{|i|
    ary = mul(ary, [0] + (1..i).map{|j| (-1) ** (i - j) * C(i - 1, i - j) / f(j).to_r})
  }
  (0..ary.size - 1).inject(0){|s, i| s + f(i) * ary[i]}.to_i
end

def A193638(n)
  (0..n).map{|i| A([3] * i)}
end
ary = A193638(13)

# OEIS A193638のデータ
ary0 =
[1,0,2,174,41304,19606320,16438575600,
 22278418248240,45718006789687680,
 135143407245840698880,553269523327347306412800,
 3039044104423605600086688000,
 21819823367694505460651694873600,
 200345011881335747639978525387827200]
# 一致の確認
p ary == ary0