仕事の部屋: 11月 2018

Ruby

A321686

n=4 の場合
4 | 1111 |
3+1 | 1112 |
2+2 | 1122 | 1212, 2121.
2+1+1 | 1123 | 1213, 1231, 2131, 1312, 1321, 3121.
1+1+1+1 | 1234 | 1234, 1243, ... (24 terms)
より、T(4,1) = 0, T(4,2) = 0+2 = 2, T(4,3) = 6, T(4,4) = 24

となっているが、

要素の数が同じもの同士は区別しないとすると、

4 | 1111 |
3+1 | 1112 |
2+2 | 1122 | 1212.
2+1+1 | 1123 | 1213, 1231, 2131.
1+1+1+1 | 1234 | 1234.

T(4,1) = 0, T(4,2) = 0+1 = 1, T(4,3) = 3, T(4,4) = 1
となる。

このように要素の数が同じもの同士は区別しないとした場合について

出力してみた。

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 mul(f_ary, b_ary)
  s1, s2 = f_ary.size, b_ary.size
  ary = Array.new(s1 + s2 - 1, 0)
  (0..s1 - 1).each{|i|
    (0..s2 - 1).each{|j|
      ary[i + j] += f_ary[i] * b_ary[j]
    }
  }
  ary
end

def ncr(n, r)
  return 1 if r == 0
  (n - r + 1..n).inject(:*) / (1..r).inject(:*)
end

def f(n)
  return 1 if n < 2
  (1..n).inject(:*)
end

def A(a)
  ary = [1]
  a.each{|i|
    ary = mul(ary, [0] + (1..i).map{|j| (-1) ** (i - j) * ncr(i - 1, i - j) / f(j).to_r})
  }
  (0..ary.size - 1).inject(0){|s, i| s + f(i) * ary[i]}.to_i
end

def B(n)
  a = Array.new(n + 1, 0)
  partition(n, 1, n).each{|ary|
    a[ary.size] += A(ary) / ary.group_by(&:to_i).inject(1){|s, i| s * f(i.last.size)}
  }
  a[1..-1]
end

n = 40
(1..n).each{|i| p B(i)}
# Row sums
p (1..n).map{|i| B(i).inject(:+)}

出力結果
[1]
[0, 1]
[0, 1, 1]
[0, 1, 3, 1]
[0, 1, 7, 6, 1]
[0, 1, 15, 25, 10, 1]
[0, 1, 31, 90, 65, 15, 1]
[0, 1, 63, 301, 350, 140, 21, 1]
[0, 1, 127, 966, 1701, 1050, 266, 28, 1]
[0, 1, 255, 3025, 7770, 6951, 2646, 462, 36, 1]
[0, 1, 511, 9330, 34105, 42525, 22827, 5880, 750, 45, 1]
[0, 1, 1023, 28501, 145750, 246730, 179487, 63987, 11880, 1155, 55, 1]
[0, 1, 2047, 86526, 611501, 1379400, 1323652, 627396, 159027, 22275, 1705, 66, 1]
[0, 1, 4095, 261625, 2532530, 7508501, 9321312, 5715424, 1899612, 359502, 39325, 2431, 78, 1]
[0, 1, 8191, 788970, 10391745, 40075035, 63436373, 49329280, 20912320, 5135130, 752752, 66066, 3367, 91, 1]
[0, 1, 16383, 2375101, 42355950, 210766920, 420693273, 408741333, 216627840, 67128490, 12662650, 1479478, 106470, 4550, 105, 1]
[0, 1, 32767, 7141686, 171798901, 1096190550, 2734926558, 3281882604, 2141764053, 820784250, 193754990, 28936908, 2757118, 165620, 6020, 120, 1]
[0, 1, 65535, 21457825, 694337290, 5652751651, 17505749898, 25708104786, 20415995028, 9528822303, 2758334150, 512060978, 62022324, 4910178, 249900, 7820, 136, 1]
[0, 1, 131071, 64439010, 2798806985, 28958095545, 110687251039, 197462483400, 189036065010, 106175395755, 37112163803, 8391004908, 1256328866, 125854638, 8408778, 367200, 9996, 153, 1]
[0, 1, 262143, 193448101, 11259666950, 147589284710, 693081601779, 1492924634839, 1709751003480, 1144614626805, 477297033785, 129413217791, 23466951300, 2892439160, 243577530, 13916778, 527136, 12597, 171, 1]
[0, 1, 524287, 580606446, 45232115901, 749206090500, 4306078895384, 11143554045652, 15170932662679, 12011282644725, 5917584964655, 1900842429486, 411016633391, 61068660380, 6302524580, 452329200, 22350954, 741285, 15675, 190, 1]
[0, 1, 1048575, 1742343625, 181509070050, 3791262568401, 26585679462804, 82310957214948, 132511015347084, 123272476465204, 71187132291275, 26826851689001, 6833042030178, 1204909218331, 149304004500, 13087462580, 809944464, 34952799, 1023435, 19285, 210, 1]
[0, 1, 2097151, 5228079450, 727778623825, 19137821912055, 163305339345225, 602762379967440, 1142399079991620, 1241963303533920, 835143799377954, 366282500870286, 108823356051137, 22496861868481, 3295165281331, 345615943200, 26046574004, 1404142047, 53374629, 1389850, 23485, 231, 1]
[0, 1, 4194303, 15686335501, 2916342574750, 96416888184100, 998969857983405, 4382641999117305, 9741955019900400, 12320068811796900, 9593401297313460, 4864251308951100, 1672162773483930, 401282560341390, 68629175807115, 8479404429331, 762361127264, 49916988803, 2364885369, 79781779, 1859550, 28336, 253, 1]
[0, 1, 8388607, 47063200806, 11681056634501, 485000783495250, 6090236036084530, 31677463851804540, 82318282158320505, 120622574326072500, 108254081784931500, 63100165695775560, 24930204590758260, 6888836057922000, 1362091021641000, 195820242247080, 20677182465555, 1610949936915, 92484925445, 3880739170, 116972779, 2454606, 33902, 276, 1]
[0, 1, 16777215, 141197991025, 46771289738810, 2436684974110751, 37026417000002430, 227832482998716310, 690223721118368580, 1167921451092973005, 1203163392175387500, 802355904438462660, 362262620784874680, 114485073343744260, 25958110360896000, 4299394655347200, 526655161695960, 48063331393110, 3275678594925, 166218969675, 6220194750, 168519505, 3200450, 40250, 300, 1]
[0, 1, 33554431, 423610750290, 187226356946265, 12230196160292565, 224595186974125331, 1631853797991016600, 5749622251945664950, 11201516780955125625, 13199555372846848005, 10029078340998476760, 5149507353856958820, 1850568574253550060, 477898618396288260, 90449030191104000, 12725877242482560, 1343731795378830, 107025546101760, 6433839018750, 290622864675, 9759104355, 238929405, 4126200, 47450, 325, 1]
[0, 1, 67108863, 1270865805301, 749329038535350, 61338207158409090, 1359801318005044551, 11647571772911241531, 47628831813556336200, 106563273280541795575, 143197070509423605675, 123519417123830092365, 71823166587281982600, 29206898819153109600, 8541149231801585700, 1834634071262848260, 294063066070824960, 35569317763922670, 3270191625210510, 229268487458010, 12246296312250, 495564056130, 15015551265, 333832005, 5265000, 55575, 351, 1]
[0, 1, 134217727, 3812664524766, 2998587019946701, 307440364830580800, 8220146115188676396, 82892803728383735268, 392678226281361931131, 1006698291338432496375, 1538533978374777852325, 1501910658871554621690, 985397416171213883565, 451512851236272407400, 148782988064375309400, 36060660300744309600, 6539643128396047620, 898741468057510350, 94432767017711850, 7626292886912700, 474194413703010, 22653141490980, 825906183960, 22693687380, 460192005, 6654375, 64701, 378, 1]
[0, 1, 268435455, 11438127792025, 11998160744311570, 1540200411172850701, 49628317055962639176, 588469772213874823272, 3224318613979279184316, 9452962848327254398506, 16392038075086211019625, 18059551225961878690915, 13326679652926121224470, 6855064482242755179765, 2534474684137526739000, 689692892575539953400, 140694950355081071520, 21818248085373723570, 2598531274376323650, 239332331869053150, 17110181160972900, 949910385013590, 40823077538100, 1347860993700, 33738295500, 626551380, 8336601, 74907, 406, 1]
[0, 1, 536870911, 34314651811530, 48004081105038305, 7713000216608565075, 299310102746948685757, 4168916722553086402080, 26383018684048108297800, 88300984248924568770870, 173373343599189364594756, 215047101560666876619690, 177979707061075333384555, 102442517922081938561415, 42337710060168129525765, 12879868072770626040000, 2940812098256837097720, 511605167806434372210, 68591811024147549270, 7145845579888333500, 581535955088511150, 37058299246258290, 1848018090851790, 71823880393200, 2157580085700, 49402080000, 843303006, 10359090, 86275, 435, 1]
[0, 1, 1073741823, 102944492305501, 192050639071964750, 38613005164147863680, 1803573616698300679617, 29481727160618553500317, 215233066194937952784480, 821091876924369227235630, 1822034420240818214718430, 2538891460766525007411346, 2350803586293570877234350, 1509732440048140534682950, 695170458764435751922125, 235535731151727520125765, 59932861644880019603520, 11638099950966221425290, 1746257766241090259070, 204362877042025885770, 18776564681658556500, 1359760239259935240, 77714697244997670, 3499967339895390, 123605802450000, 3392632085700, 71327958156, 1122998436, 12774790, 98890, 465, 1]
[0, 1, 2147483647, 308834550658326, 768305500780164501, 193257076459811283150, 10860054705353951941382, 208175663741028175181836, 1751346256720122175776157, 7605059958514260997905150, 19041436079332551374419930, 29749840488672593296243236, 30748534496289375534223546, 21977325306919397828112700, 11242118862750241061592700, 4228206426040348553808600, 1194461517469807833782085, 257780560811305783833450, 43070739743305846088550, 5629152430039582088700, 579894170675197015770, 47331529706117196540, 3069483578649883980, 158213946062591640, 6466506598695390, 208421604592500, 5247158997756, 101648915928, 1480692556, 15642600, 112840, 496, 1]
[0, 1, 4294967295, 926505799458625, 3073530837671316330, 967053687799836580251, 65353585308583522931442, 1468089700892551178214234, 14218945717502005581391092, 70196885883348471156922507, 198019420751839774742104450, 346289681454731077633095526, 398732254444145099706925788, 316453763486241547299688646, 179366989385422772690410500, 74665215253355469368721700, 23339590705557273894321960, 5576731051262006158950735, 1033053876190811013427350, 150024635914057905773850, 17227035843543522404100, 1573856294503658143110, 114860168436414644100, 6708404338089491700, 313410104431281000, 11677046713507890, 344847738534156, 7991679727812, 143108307496, 1934327956, 19027800, 128216, 528, 1]
[0, 1, 8589934591, 2779521693343170, 12295049856484723945, 4838341969836854217585, 393088565539300974168903, 10341981491556441770431080, 115219655440908595829342970, 645990918667638245993693655, 2050391093401746218577967007, 4007205916753881628706155236, 5131076734784472274116204982, 4512631179765285214602878186, 2827591614882160364965435646, 1299345218185754813221236000, 448098666542271851677873060, 118144018577011378596484455, 24171700822696604400643035, 3883521958557911223130500, 494565352784928353855850, 50278018028120343409410, 4100780000104780313310, 269153468212472953200, 14230246844440235700, 605336272268978250, 20643087915395946, 560623091185080, 11998712337700, 199203818220, 2505161956, 23002496, 145112, 561, 1]
[0, 1, 17179869183, 8338573669964101, 49182978947632238950, 24204004899040755811870, 2363369735205642699231003, 72786959006434393367186463, 932099225018825208405174840, 5929137923449652809772585865, 21149901852685100431773363725, 46129656177694444134345674603, 65580126734167548918100615020, 63795282071733180063953621400, 44098913788115530324118977230, 22317769887668482563283975646, 8468923882862104440067204960, 2456546982351465287818108795, 553234633385550257808059085, 97958618035296917640122535, 13774829014256478300247500, 1550403731375455565453460, 140495178030425510302230, 10291309768991658236910, 610679392479038610000, 29363653651164691950, 1142056558069272846, 35779911377393106, 896587036640680, 17775623066080, 274358676900, 3218239332, 27646080, 163625, 595, 1]
[0, 1, 34359738367, 25015738189761486, 196740254364198919901, 121069207474151411298300, 14204422416132896951197888, 511872082780246396269536244, 7529580759157036060608585183, 54294340536065700496358447625, 217428156450300657127506223115, 528576119807323985909575784358, 833091176987705031151553054843, 894918793666698889749497693220, 681180075105350604601619302620, 378865462103142768773378611920, 157820552013462153604359255006, 50230222582837014332975054475, 12414770383291369928363172325, 2414448376056191692970387250, 373455198320426483645072535, 46333307373141045174770160, 4641297648044816792102520, 377195302717233649751160, 24947615188488584876910, 1344770733758155908750, 59057124160965785946, 2108114165258886708, 60884348403332146, 1412080105557000, 26006383373080, 374124096192, 4102913892, 33045705, 183855, 630, 1]
[0, 1, 68719476735, 75047248929022825, 786986033194985441090, 605542777625121255411401, 85347603704271533118485628, 3597309001877857670837951596, 60748518156036534881138217708, 496178645583748340527834613808, 2228575905039072271771420678775, 6031765474330864502132839851053, 10525670243659784359728212442474, 12467035494654790597895023066703, 10431439845141607354172167929900, 6364162006652492136202298481420, 2903994294318537226443126692016, 1011734335921691397264935181081, 273696089482081673043512156325, 58289289528359012094800530075, 9883552342464721365871837950, 1346454653156388432315245895, 148441855630127014601025600, 13316789610541190736379200, 975938067240959686797000, 58566883532442482595660, 2880255961943266343346, 115976206622955727062, 3812875920552186796, 101834671464485146, 2192271606749400, 37604230355032, 505417340736, 5193422157, 39296775, 205905, 666, 1]
[0, 1, 137438953471, 225141815506545210, 3148019180028870787185, 3028500874158801262498095, 512691165003254319966325169, 25266510616849275228984146800, 489585454250170136719943693260, 4526356328409771599631649741980, 22781937695974471058242041401558, 68577996122678581795232659040358, 132339808398248276818871389160741, 172597131674172062132363512309613, 158507193326637293556305374085303, 105893869944928989397206645151200, 52828070715749087759292325553676, 20103478004987290979947024770393, 5938263946599161512048153994931, 1381192590520902902844722227750, 255960336377653439412237289075, 38159100058748878444492001745, 4612175477019182753537809095, 454728016672574401537747200, 36739303224324223219507200, 2440110155552021751688500, 133453538542967407522656, 6011613540763070974020, 222736732398416957350, 6766081393022256030, 167602819666967146, 3358002747755392, 53777585258584, 676800271917, 6529512507, 46503450, 229881, 703, 1]
[0, 1, 274877906943, 675425583958589101, 12592301861930989693950, 15145652389974035183277660, 3079175490893684721060449109, 177378265482948180922855352769, 3941950144618210368988533692880, 41226792409938114533404791371080, 232345733288154482182052063757560, 777139895045438870805801290845496, 1656655696901657903621689328969250, 2376102520162485084539597049185710, 2391697838247094171920638749503855, 1746915242500572134514405051353303, 951143001396914393545883854010016, 394587196800533034418391746650357, 126992229043772198196813796679151, 32180923166496316666097876322181, 6500399318073971691089468009250, 1057301437611379886746569325720, 139626960553170899022323801835, 15070919860488393988905994695, 1336471294056355758805920000, 97742057113124767011719700, 5909902157669174347277556, 295767104143570323821196, 12248242047918745779820, 418953092796062382220, 11794165983031270410, 271700904847384298, 5078885476030080, 76111994231845, 898803697155, 8157133257, 54779166, 255892, 741, 1]
[1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057, 51724158235372, 474869816156751, 4506715738447323, 44152005855084346, 445958869294805289, 4638590332229999353, 49631246523618756274, 545717047936059989389, 6160539404599934652455, 71339801938860275191172, 846749014511809332450147, 10293358946226376485095653, 128064670049908713818925644, 1629595892846007606764728147, 21195039388640360462388656799, 281600203019560266563340426570, 3819714729894818339975525681317, 52868366208550447901945575624941, 746289892095625330523099540639146, 10738823330774692832768857986425209]

Ruby

A129373

A(x) = (1+x) * A(x^2) * A(x^3) * A(x^4) * ... * A(x^n) * ...

を満たすA(x) について考える。

(1+x) * A(x^2),

(1+x) * A(x^2) * A(x^3),

(1+x) * A(x^2) * A(x^3) * A(x^4),

...

がA(x) に近づくさまを出力してみた。

# m次以下を取り出す
def mul(f_ary, b_ary, m)
  s1, s2 = f_ary.size, b_ary.size
  ary = Array.new(s1 + s2 - 1, 0)
  (0..s1 - 1).each{|i|
    (0..s2 - 1).each{|j|
      ary[i + j] += f_ary[i] * b_ary[j]
    }
  }
  ary[0..m]
end

def s(f_ary, g_ary, n)
  s = 0
  (1..n).each{|i| s += i * f_ary[i] * g_ary[i] ** (n / i) if n % i == 0}
  s
end

def A(f_ary, g_ary, n)
  ary = [1]
  a = [0] + (1..n).map{|i| s(f_ary, g_ary, i)}
  (1..n).each{|i| ary << (1..i).inject(0){|s, j| s + a[j] * ary[-j]} / i}
  ary
end

def S(n)
  a = [0, 1]
  (2..n).each{|i|
    s = 0
    (1..i - 1).each{|j|
      s += a[j] if i % j == 0
    }
    a << s
  }
  a
end

def B(n)
  ary1 = S(n).map{|i| -i}
  ary2 = Array.new(n + 1, -1)
  A(ary1, ary2, n)
end

n = 20
ary = B(n)
a = Array.new(n + 1, 0)
a[0] = 1
a[1] = 1
p [1, a]
(2..n).each{|i|
  b = Array.new(n + 1, 0)
  (0..n / i).each{|j| b[i * j] = ary[j]}
  a = mul(a, b, n)
  p [i, a]
}

出力結果
[1, [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
[2, [1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 7, 7, 9, 9, 13, 13, 19, 19, 26]]
[3, [1, 1, 1, 2, 2, 2, 4, 4, 5, 8, 9, 10, 17, 18, 21, 30, 35, 39, 58, 64, 76]]
[4, [1, 1, 1, 2, 3, 3, 5, 6, 8, 11, 14, 16, 26, 30, 36, 48, 64, 72, 99, 118, 148]]
[5, [1, 1, 1, 2, 3, 4, 6, 7, 10, 14, 18, 22, 33, 40, 50, 67, 87, 106, 141, 171, 219]]
[6, [1, 1, 1, 2, 3, 4, 7, 8, 11, 16, 21, 26, 40, 48, 61, 83, 108, 132, 182, 220, 281]]
[7, [1, 1, 1, 2, 3, 4, 7, 9, 12, 17, 23, 29, 44, 55, 70, 95, 125, 155, 211, 264, 336]]
[8, [1, 1, 1, 2, 3, 4, 7, 9, 13, 18, 24, 31, 47, 59, 77, 104, 138, 173, 235, 295, 383]]
[9, [1, 1, 1, 2, 3, 4, 7, 9, 13, 19, 25, 32, 49, 62, 81, 111, 147, 186, 254, 320, 415]]
[10, [1, 1, 1, 2, 3, 4, 7, 9, 13, 19, 26, 33, 50, 64, 84, 115, 154, 195, 267, 339, 441]]
[11, [1, 1, 1, 2, 3, 4, 7, 9, 13, 19, 26, 34, 51, 65, 86, 118, 158, 202, 276, 352, 460]]
[12, [1, 1, 1, 2, 3, 4, 7, 9, 13, 19, 26, 34, 52, 66, 87, 120, 161, 206, 283, 361, 473]]
[13, [1, 1, 1, 2, 3, 4, 7, 9, 13, 19, 26, 34, 52, 67, 88, 121, 163, 209, 287, 368, 482]]
[14, [1, 1, 1, 2, 3, 4, 7, 9, 13, 19, 26, 34, 52, 67, 89, 122, 164, 211, 290, 372, 489]]
[15, [1, 1, 1, 2, 3, 4, 7, 9, 13, 19, 26, 34, 52, 67, 89, 123, 165, 212, 292, 375, 493]]
[16, [1, 1, 1, 2, 3, 4, 7, 9, 13, 19, 26, 34, 52, 67, 89, 123, 166, 213, 293, 377, 496]]
[17, [1, 1, 1, 2, 3, 4, 7, 9, 13, 19, 26, 34, 52, 67, 89, 123, 166, 214, 294, 378, 498]]
[18, [1, 1, 1, 2, 3, 4, 7, 9, 13, 19, 26, 34, 52, 67, 89, 123, 166, 214, 295, 379, 499]]
[19, [1, 1, 1, 2, 3, 4, 7, 9, 13, 19, 26, 34, 52, 67, 89, 123, 166, 214, 295, 380, 500]]
[20, [1, 1, 1, 2, 3, 4, 7, 9, 13, 19, 26, 34, 52, 67, 89, 123, 166, 214, 295, 380, 501]]

仕事の部屋

2018年11月23日金曜日

181123

2018年11月4日日曜日

181104