Expansion of e.g.f. 1/(1 - f(x)).
この形のe.g.f. を２通りで求めてみた。
def f(n)
return 1 if n < 2
(1..n).inject(:*)
end
def ncr(n, r)
return 1 if r == 0
(n - r + 1..n).inject(:*) / (1..r).inject(:*)
end
def gf_to_egf(ary)
(0..ary.size - 1).map{|i| f(i) * ary[i]}
end
def I(ary, n)
a = [1]
(0..n - 1).each{|i| a << -(0..i).inject(0){|s, j| s + ary[1 + i - j] * a[j]}}
a
end
def I_egf(ary, n)
a = [1]
(1..n).each{|i| a << -(1..i).inject(0){|s, j| s + ncr(i, j) * ary[j] * a[-j]}}
a
end
# ary[0] = 0として扱われる
def A_1(ary, n)
a = [1] + (1..n).map{|i| -ary[i]}
gf_to_egf(I(a, n))
end
# a[0] = 0として扱われる
def A_2(ary, n)
a = gf_to_egf(ary)
b = [1] + (1..n).map{|i| -a[i]}
I_egf(b, n)
end
def A000670_1(n)
ary = (0..n).map{|i| 1r / f(i)}
A_1(ary, n).map(&:to_i)
end
def A000670_2(n)
ary = (0..n).map{|i| 1r / f(i)}
A_2(ary, n).map(&:to_i)
end
def A006153_1(n)
ary = [0] + (0..n).map{|i| 1r / f(i)}
A_1(ary, n).map(&:to_i)
end
def A006153_2(n)
ary = [0] + (0..n).map{|i| 1r / f(i)}
A_2(ary, n).map(&:to_i)
end
n = 10
p A000670_1(n)
p A000670_2(n)
p A006153_1(n)
p A006153_2(n)
出力結果
[1, 1, 3, 13, 75, 541, 4683, 47293, 545835, 7087261, 102247563]
[1, 1, 3, 13, 75, 541, 4683, 47293, 545835, 7087261, 102247563]
[1, 1, 4, 21, 148, 1305, 13806, 170401, 2403640, 38143377, 672552730]
[1, 1, 4, 21, 148, 1305, 13806, 170401, 2403640, 38143377, 672552730]
