160221

Ruby


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

第10 ** i 項を求めてみた。

（実行時間は7～8時間くらい。）

def A001522(n)
  a = []
  m = Math.sqrt(2 * n).to_i
  (m + 1).times{a << Array.new(n + 1){0}}
  a[0][0] = 1
  (1..n).each{|x|
    b = Marshal.load(Marshal.dump(a))
    (1..m).each{|i| (0..n - x).each{|j| b[i][j + x] += a[i - 1][j]}}
    a = b
  }
  # 1, 1, … , 1の真っ平らなもの
  s = 1
  # 山型
  (1..n - 1).each{|i|
    # k + 1 <= m
    (1..m - 1).each{|k|
      s += a[k][i] * a[k + 1][n - i]
      break if a[k][n] == 0
    }
  }
  s
end

(0..4).each{|i| p A001522(10 ** i)}

出力結果
1
19
92377832
11910553732718752974456751586469
18025910585317110305980655794157479897788811117151181916744879563021342251768216899112133590826921698849578