151113

Ruby


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

例えば、n = 9 のとき、
[ 1 1 1 1 1 1 1 1 1 ],
[ 1 1 1 1 1 1 2 1 ],
[ 1 1 1 1 1 2 1 1 ],
[ 1 1 1 1 2 1 1 1 ],
[ 1 1 1 1 2 2 1 ],
[ 1 1 1 2 1 1 1 1 ],
[ 1 1 1 2 2 1 1 ],

[ 1 2 3 2 1 ],
[ 1 1 2 1 1 1 1 1 ],
[ 1 1 2 2 1 1 1 ],
[ 1 1 2 2 2 1 ],
[ 1 2 1 1 1 1 1 1 ],
[ 1 2 2 1 1 1 1 ],
[ 1 2 2 2 1 1 ]
の14通りある。

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

A001522（http://oeis.org/A001522/list）
と比較し、答え合わせしてみる。
（なお、以下のコードにおいて、
「和がn でk のぼるのぼりかた」 = 「n をk 個の相異なる数に分割する場合の数」
を利用したが、
これは「縦横逆に見る」だけのことである。）

# nをk個の相異なる数（最小値がl）に分割
def g(n, l, k)
  return 1 if n == l && k == 1
  # 先頭がiのものにlを前から追加
  (l + 1..n - l).inject(0){|s, i| s + g(n - l, i, k - 1)}
end

# nをk個の相異なる数に分割
def g0(n, k)
  (1..n).inject(0){|s, l| s + g(n, l, 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