151109

Ruby


Number of palindromic and unimodal compositions of n

線対称な山型に分割してみる。
例えば、n = 6 のとき、
1 + 2 + 2 + 1,
1 + 4 + 1,
などがある。
この山を横に切ると、
4 + 2,
3 + 1 + 1 + 1,
…,
となる。
この操作からわかるように、
p(n | 和因子が線対称な山型に並ぶ)
= p(n | 和因子は偶数) + p(n | 和因子は奇数)
が成り立つ。

オンライン整数列大辞典の
A035363（http://oeis.org/A035363/list）、
A000009（http://oeis.org/A000009/list）、
A096441（http://oeis.org/A096441/list）
と比較し、答え合わせしてみる。

def A035363(n)
  even = []
  2.step(n, 2){|i| even << i}
  ps0 = Array.new(n + 1){0}
  ps0[0] = 1
  even.each{|num|
    (num..n).each{|i|
      ps0[i] += ps0[i - num]
    }
  }
  ps0
end

def A000009(n)
  odd = []
  1.step(n, 2){|i| odd << i}
  ps1 = Array.new(n + 1){0}
  ps1[0] = 1
  odd.each{|num|
    (num..n).each{|i|
      ps1[i] += ps1[i - num]
    }
  }
  ps1
end

def A096441(n)
  ps0, ps1 = A035363(n), A000009(n)
  (1..n).map{|i| ps0[i] + ps1[i]}
end

ary = A035363(69)
# OEIS A035363のデータ
ary0 =
[1,0,1,0,2,0,3,0,5,0,7,0,11,0,15,0,22,0,30,0,42,0,
 56,0,77,0,101,0,135,0,176,0,231,0,297,0,385,0,490,
 0,627,0,792,0,1002,0,1255,0,1575,0,1958,0,2436,0,
 3010,0,3718,0,4565,0,5604,0,6842,0,8349,0,10143,0,
 12310,0]
# 一致の確認
p ary == ary0

ary = A000009(55)
# OEIS A000009のデータ
ary0 =
[1,1,1,2,2,3,4,5,6,8,10,12,15,18,22,27,32,38,46,
 54,64,76,89,104,122,142,165,192,222,256,296,340,
 390,448,512,585,668,760,864,982,1113,1260,1426,
 1610,1816,2048,2304,2590,2910,3264,3658,4097,4582,
 5120,5718,6378]
# 一致の確認
p ary == ary0

ary = A096441(55)
# OEIS A096441のデータ
ary0 =
[1,2,2,4,3,7,5,11,8,17,12,26,18,37,27,54,38,76,54,
 106,76,145,104,199,142,266,192,357,256,472,340,
 621,448,809,585,1053,760,1354,982,1740,1260,2218,
 1610,2818,2048,3559,2590,4485,3264,5616,4097,7018,
 5120,8728,6378]
# 一致の確認
p ary == ary0

出力結果
true
true
true