2017年10月9日月曜日

171009

Ruby


PD(n), PD_t(n), PDO(n) and PDO_t(n)

つい最近の論文だが、
Bernard L. S. Lin, The number of tagged parts over the partitions with designated summands, Journal of Number Theory.
においてPD_t(n) と PDO_t(n) が考え出されたので、数えてみた。
n の分割を一つずつcheck しているので、かなり遅いコードです。

# 和因子はmin以上max以下
def partition(n, min, max)
  return [[]] if n == 0
  [max, n].min.downto(min).flat_map{|i| partition(n - i, min, i).map{|rest| [i, *rest]}}
end

def PD(n)
  partition(n, 1, n).map{|i| i.each_with_object(Hash.new(0)){|v, o| o[v] += 1}.values.inject(:*)}.inject(:+)
end

def PD_t(n)
  partition(n, 1, n).map{|i| i.each_with_object(Hash.new(0)){|v, o| o[v] += 1}.values}.map{|i| i.size * i.inject(:*)}.inject(:+)
end

def PDO(n)
  partition(n, 1, n).select{|i| i.all?{|j| j.odd?}}.map{|a| a.each_with_object(Hash.new(0)){|v, o| o[v] += 1}.values.inject(:*)}.inject(:+)
end

def PDO_t(n)
  partition(n, 1, n).select{|i| i.all?{|j| j.odd?}}.map{|a| a.each_with_object(Hash.new(0)){|v, o| o[v] += 1}.values}.map{|i| i.size * i.inject(:*)}.inject(:+)
end

n = 40
p (1..n).map{|i| PD(i)}
p (1..n).map{|i| PD_t(i)}
p (1..n).map{|i| PDO(i)}
p (1..n).map{|i| PDO_t(i)}

出力結果
[1, 3, 5, 10, 15, 28, 41, 69, 102, 160, 231, 352, 498, 732, 1027, 1470, 2031, 2856, 3896, 5382, 7272, 9896, 13233, 17800, 23579, 31362, 41219, 54288, 70791, 92456, 119698, 155097, 199512, 256664, 328134, 419436, 533162, 677412, 856573, 1082284]
[1, 3, 6, 13, 24, 45, 77, 132, 213, 346, 537, 834, 1257, 1893, 2778, 4077, 5865, 8421, 11903, 16785, 23364, 32444, 44562, 61041, 82859, 112164, 150639, 201768, 268413, 356100, 469636, 617724, 808236, 1054802, 1370127, 1775286, 2290610, 2948427, 3780717, 4836814]
[1, 2, 4, 5, 8, 12, 16, 22, 32, 42, 56, 76, 98, 128, 168, 213, 272, 348, 436, 548, 688, 852, 1056, 1308, 1603, 1964, 2404, 2920, 3544, 4296, 5176, 6230, 7488, 8958, 10704, 12772, 15182, 18024, 21368, 25254]
[1, 2, 4, 6, 10, 16, 24, 36, 52, 74, 104, 144, 196, 264, 352, 468, 614, 800, 1036, 1332, 1704, 2168, 2744, 3456, 4331, 5408, 6724, 8328, 10278, 12640, 15496, 18936, 23072, 28030, 33960, 41040, 49470, 59488, 71368, 85428]