160103(6)

Ruby


Arrangement of the word 'Success'

A190945(100)(2) の二つ目のコードで使っている考え方は

実に汎用性がある。

考え方を知りたい人は以下を読んでみてください。

http://math.stackexchange.com/questions/129451/find-the-number-of-arrangements-of-k-mbox-1s-k-mbox-2s-cdots

http://math.stackexchange.com/questions/162394/arrangement-of-the-word-success

この考え方を用いてコードを書いてみた。

オンライン整数列大辞典の
A114938（http://oeis.org/A114938/list）、

A190945（http://oeis.org/A190945/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 A114938(n)
  (1..n).map{|i| A([2] * i)}
end

def A190945(n)
  (1..n).map{|i| A(1..i)}
end

# Arrangement of the word 'Success'
p A([1, 1, 2, 3])

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

ary = A190945(11)
# OEIS A190945のデータ
ary0 =
[1,1,10,1074,1637124,45156692400,
 27230193578558160,420296434943941609215120,
 190200071567439616748736269178720,
 2843464512159537301384360263178682136716160,
 1562137388408002436396705025296003247844758163480828800]
# 一致の確認
p ary == ary0

出力結果
96
true
true