151116

Ruby


Number of weakly unimodal partitions of n(2)

f(10 ** i) を調べてみた。

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

(0..5).each{|i| p f(10 ** i)}

出力結果
1
209
881103407093
621820350227357514973418077551453276312298427
19002522919705812331177485379942859319055411162011514367363395916246742323537767948739063616351819551047189156629598790992584402183987248909495666154869
48678030871829155901022590522684849620391551473549000799273927405133763444866764659809512433747622053270638883565798902546892005839120274437671143669750850751160633528202728499786015906676582056664426896989396840534790145116651069254954897615303378028235812765793586406800773111878610378487167931235857873906002076196204137971760798472390952909509209509726649183557835082279874649003714814090330292729697886962484793304921164447358209863494970638027349114178340713474610030285902396235276379