160306

Ruby

Ordered Bell number(3)

以下のコードは、オンライン整数列大辞典の

A142071 のCOMMENTS の
Row sums are: A000629.

と

A000629 のFORMULA の

a(n) = 2 * A000670(n) - 0^n.

を利用した。

Ordered Bell number(2) のコードに比べてかなり速くなった。

（実行時間は20分弱。）

def A000670(n)
  a = [1]
  b = [0, 1]
  (2..n + 1).each{|i|
    b << 0
    s = 0
    i.downto(1){|j|
      # b[j]をb[j - 1] * (j - 1) + b[j] * jにする
      c = b[j] += (b[j - 1] + b[j]) * (j - 1)
      s += c
    }
    a << s / 2
  }
  a
end

N = 4
ary = A000670(10 ** N)
(0..N).each{|i| p ary[10 ** i]}