151202

Ruby


Number of smooth weakly unimodal compositions of n into positive parts such that the first and last part are 1(2)

速くしてみた。

# nをl以上の相異なるk個の数で分割
def g(n, l, k)
  return 0 if n < l
  return 1 if k == 1
  s = 0
  (l + 1..n).each{|i|
    v = g(n - i + 1, i, k - 1)
    break if v == 0
    s += v
  }
  return s
end

# nをk個の相異なる数に分割
def g0(n, k)
  g(n, 1, k)
end

def f(n)
  # 1, 1, … , 1の真っ平らなもの
  s = 1
  # 山型
  (1..n).each{|i|
    (1..i).each{|k|
      # 和がiでkのぼるものと和がn - iでk + 1のぼるものを組み合わせたもの
      s += g0(i, k) * g0(n - i, k + 1) 
    }
  }
  s
end

def A001522(n)
  (0..n).map{|i| f(i)}
end
ary = A001522(56)

# OEIS A001522のデータ
ary0 =
[1,1,1,1,2,3,5,7,10,14,19,26,35,47,62,82,107,139,
 179,230,293,372,470,591,740,924,1148,1422,1756,
 2161,2651,3244,3957,4815,5844,7075,8545,10299,
 12383,14859,17794,21267,25368,30207,35902,42600,
 50462,59678,70465,83079,97800,114967,134956,
 158205,185209,216546,252859]
# 一致の確認
p ary == ary0