「nをk個の相異なる数に分割する」場合の数を高速に求めるには？

「nをk個の相異なる数に分割する」場合の数をf(n, k)とします。

例えば、10 = 1 + 2 + 7 = 1 + 3 + 6 = 1 + 4 + 5 = 2 + 3 + 5
なので、f(10, 3) = 4です。

f(n, k)を高速に求めるにはどのようにすればよろしいでしょうか？

以下大変遅いコードです。

# nをk個の相異なる数（最大値がl）に分割
def g(n, l, k)
  return 1 if n == l && k == 1
  # 末尾がiのものにlを追加
  (1..l - 1).inject(0){|s, i| s += g(n - l, i, k - 1)}
end

# nをk個の相異なる数に分割
def f(n, k)
  (1..n).inject(0){|s, l| s += g(n, l, k)}
end

# 以下検証のためp(n | 和因子は相異なる)を求めてみる
def A000009(n)
  return 1 if n == 0
  (1..n).inject(0){|s, k| s += f(n, k)}
end
p (0..20).map{|i| A000009(i)}

実行結果
[1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 38, 46, 54, 64]
（p(n | 和因子は相異なる)については、オイラーの分割恒等式をプログラミングで確認するには？ で質問しました。）