151115(2)

Ruby


Number of weakly unimodal partitions of n(1)

例えば、n = 4 のとき、
[ 1 1 1 1 ],
[ 2 2 ],
[ 1 1 2 ],
[ 1 2 1],
[ 2 1 1 ],
[ 1 3 ],
[ 3 1 ],
[ 4 ]
の8通りある。

オンライン整数列大辞典の

A001523（http://oeis.org/A001523/list）
と比較し、答え合わせしてみる。

def f(n)
  return 1 if n == 0
  s = 0
  ps = Array.new(n + 1){0}
  ps[0] = 1
  (1..n).each{|num|
    old_ary = ps.clone
    # 最大値がnum
    (num..n).each{|i|
      j = ps[i - num]
      # 左のあがる階段がj通り、右のさがる階段がold_ary[n - i]通り
      s += j * old_ary[n - i]
      ps[i] += j
    }
  }
  s
end

def A001523(n)
  (0..n).map{|i| f(i)}
end
ary = A001523(38)

# OEIS A001523のデータ
ary0 =
[1,1,2,4,8,15,27,47,79,130,209,330,512,784,1183,
 1765,2604,3804,5504,7898,11240,15880,22277,31048,
 43003,59220,81098,110484,149769,202070,271404,
 362974,483439,641368,847681,1116325,1464999,
 1916184,2498258]
# 一致の確認
p ary == ary0