150920

Ruby


分割が絡んだ係数について

Handbook of Mathematical Functions: with Formulas, Graphs, and Mathematical Tables

に載っているTable 24.2のM3を求めるコードを書いてみた。

（ただし、順番が異なっている箇所があります。）

# 階乗
def f(ary)
  ary.map{|i| (1..i).inject(:*)}.inject(:*)
end

# nの分割を列挙
def partion_ary(n)
  ary = [[n]]
  # nの分割になっていないものは以下の操作を繰り返す
  f_ary = []
  (n - 1).downto(1){|i| f_ary.push([i])}
  while f_ary.size > 0
    b_ary = []
    f_ary.each{|c|
      i = [n - c.inject(:+), c[-1]].min
      (1..i).each{|j|
        d = c.clone
        d.push(j)
        # nの分割になったら、aryに加える
        d.inject(:+) == n ? ary.push(d) : b_ary.push(d)
      }
    }
    f_ary = b_ary
  end
  ary
end

def multinomials_and_partitions(n)
  m = (1..n).inject(:*)
  ary = []
  partion_ary(n).each{|a|
    ary << m / (f(a) * f(a.group_by(&:to_i).map{|i| i.last.size}))
  }
  ary
end

(1..15).each{|i| p multinomials_and_partitions(i)}

出力結果
[1]
[1, 1]
[1, 3, 1]
[1, 4, 3, 6, 1]
[1, 5, 10, 10, 15, 10, 1]
[1, 6, 15, 10, 15, 60, 15, 20, 45, 15, 1]
[1, 7, 21, 35, 21, 105, 105, 70, 35, 210, 105, 35, 105, 21, 1]
[1, 8, 28, 56, 35, 28, 168, 210, 280, 280, 56, 420, 840, 280, 105, 70, 560, 420, 56, 210, 28, 1]
[1, 9, 36, 84, 126, 36, 252, 378, 504, 1260, 315, 280, 84, 756, 1890, 1260, 1260, 2520, 126, 1260, 3780, 840, 945, 126, 1260, 1260, 84, 378, 36, 1]
[1, 10, 45, 120, 210, 126, 45, 360, 630, 840, 2520, 1260, 2100, 1575, 120, 1260, 3780, 2520, 3150, 12600, 1575, 6300, 2800, 210, 2520, 9450, 4200, 12600, 12600, 945, 252, 3150, 12600, 2100, 4725, 210, 2520, 3150, 120, 630, 45, 1]
[1, 11, 55, 165, 330, 462, 55, 495, 990, 1320, 4620, 2310, 4620, 6930, 1386, 5775, 165, 1980, 6930, 4620, 6930, 27720, 6930, 34650, 23100, 17325, 15400, 330, 4620, 20790, 9240, 34650, 69300, 5775, 17325, 69300, 15400, 462, 6930, 34650, 11550, 69300, 46200, 10395, 462, 6930, 34650, 4620, 17325, 330, 4620, 6930, 165, 990, 55, 1]
[1, 12, 66, 220, 495, 792, 462, 66, 660, 1485, 1980, 7920, 3960, 9240, 13860, 5544, 27720, 8316, 5775, 220, 2970, 11880, 7920, 13860, 55440, 13860, 83160, 55440, 83160, 8316, 138600, 51975, 69300, 15400, 495, 7920, 41580, 18480, 83160, 166320, 27720, 51975, 415800, 138600, 103950, 138600, 184800, 792, 13860, 83160, 27720, 207900, 277200, 17325, 207900, 415800, 61600, 10395, 924, 16632, 103950, 27720, 277200, 138600, 62370, 792, 13860, 83160, 9240, 51975, 495, 7920, 13860, 220, 1485, 66, 1]
[1, 13, 78, 286, 715, 1287, 1716, 78, 858, 2145, 2860, 12870, 6435, 17160, 25740, 10296, 60060, 36036, 6006, 45045, 36036, 286, 4290, 19305, 12870, 25740, 102960, 25740, 180180, 120120, 180180, 36036, 360360, 270270, 360360, 108108, 200200, 450450, 75075, 715, 12870, 77220, 34320, 180180, 360360, 60060, 135135, 1081080, 360360, 540540, 36036, 900900, 1801800, 675675, 450450, 600600, 200200, 1287, 25740, 180180, 60060, 540540, 720720, 90090, 675675, 2702700, 600600, 450450, 270270, 1801800, 1201200, 1716, 36036, 270270, 72072, 900900, 900900, 45045, 1351350, 1801800, 200200, 135135, 1716, 36036, 270270, 60060, 900900, 360360, 270270, 1287, 25740, 180180, 17160, 135135, 715, 12870, 25740, 286, 2145, 78, 1]
[1, 14, 91, 364, 1001, 2002, 3003, 1716, 91, 1092, 3003, 4004, 20020, 10010, 30030, 45045, 18018, 120120, 72072, 24024, 105105, 168168, 42042, 126126, 364, 6006, 30030, 20020, 45045, 180180, 45045, 360360, 240240, 360360, 72072, 840840, 630630, 840840, 504504, 42042, 560560, 2522520, 630630, 378378, 504504, 1051050, 525525, 1001, 20020, 135135, 60060, 360360, 720720, 120120, 315315, 2522520, 840840, 1261260, 168168, 2522520, 5045040, 3783780, 2522520, 756756, 6306300, 2802800, 1576575, 6306300, 525525, 1401400, 2002, 45045, 360360, 120120, 1261260, 1681680, 210210, 1891890, 7567560, 1681680, 2522520, 126126, 945945, 12612600, 12612600, 4729725, 2102100, 3153150, 8408400, 1401400, 3003, 72072, 630630, 168168, 2522520, 2522520, 252252, 4729725, 12612600, 2102100, 1576575, 3783780, 12612600, 5605600, 135135, 3432, 84084, 756756, 168168, 3153150, 2522520, 105105, 6306300, 6306300, 560560, 945945, 3003, 72072, 630630, 120120, 2522520, 840840, 945945, 2002, 45045, 360360, 30030, 315315, 1001, 20020, 45045, 364, 3003, 91, 1]
[1, 15, 105, 455, 1365, 3003, 5005, 6435, 105, 1365, 4095, 5460, 30030, 15015, 50050, 75075, 30030, 225225, 135135, 45045, 225225, 360360, 180180, 25740, 630630, 210210, 126126, 455, 8190, 45045, 30030, 75075, 300300, 75075, 675675, 450450, 675675, 135135, 1801800, 1351350, 1801800, 1081080, 180180, 1401400, 6306300, 1576575, 1891890, 2522520, 630630, 6306300, 4729725, 3783780, 1891890, 2627625, 1365, 30030, 225225, 100100, 675675, 1351350, 225225, 675675, 5405400, 1801800, 2702700, 360360, 6306300, 12612600, 9459450, 6306300, 3783780, 210210, 18918900, 8408400, 9459450, 37837800, 4729725, 5675670, 3783780, 21021000, 23648625, 15765750, 7882875, 1401400, 3003, 75075, 675675, 225225, 2702700, 3603600, 450450, 4729725, 18918900, 4204200, 6306300, 630630, 2837835, 37837800, 37837800, 28378350, 12612600, 3783780, 23648625, 94594500, 21021000, 23648625, 47297250, 2627625, 21021000, 21021000, 5005, 135135, 1351350, 360360, 6306300, 6306300, 630630, 14189175, 37837800, 6306300, 9459450, 378378, 14189175, 94594500, 63063000, 23648625, 7882875, 4729725, 47297250, 63063000, 7007000, 6435, 180180, 1891890, 420420, 9459450, 7567560, 630630, 23648625, 47297250, 6306300, 4729725, 28378350, 63063000, 21021000, 2027025, 6435, 180180, 1891890, 360360, 9459450, 6306300, 225225, 23648625, 18918900, 1401400, 4729725, 5005, 135135, 1351350, 225225, 6306300, 1801800, 2837835, 3003, 75075, 675675, 50050, 675675, 1365, 30030, 75075, 455, 4095, 105, 1]

ちなみに、面白い性質を持っている。
例えば、n = 4 のとき、
1×(x + 3) + 4×(x + 3)(x + 2) + 3×(x + 3)(x + 2) + 6×(x + 3)(x + 2)(x + 1) + 1×(x + 3)(x + 2)(x + 1)x
= (x + 3)^4
となっている。