161022

Ruby


二項係数の二乗の性質について(1)

 重複組合せnHr を((n, r)) と表示することにする。
二項係数の二乗に関する次の式を確認してみる。

2 * binomial(2n - 1, n - 1) = Sum_{k=0..n} binomial(n, k)^2
3 * binomial(2n - 1, n - 1)^2 = Sum_{k=0..n} binomial(n, k)^2 * ((2n, n - k))

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

def nhr(n, r)
  ncr(n + r - 1, r)
end

n = 50
(1..n).each{|i|
  k = (0..i).inject(0){|s, j| s + ncr(i, j) ** 2}
  p [i, k, k == 2 * ncr(2 * i - 1, i - 1)]
}
(1..n).each{|i|
  k = (0..i).inject(0){|s, j| s + ncr(i, j) ** 2 * nhr(2 * i, i - j)}
  p [i, k, k == 3 * ncr(2 * i - 1, i - 1) ** 2]
}

出力結果
[1, 2, true]
[2, 6, true]
[3, 20, true]
[4, 70, true]
[5, 252, true]
[6, 924, true]
[7, 3432, true]
[8, 12870, true]
[9, 48620, true]
[10, 184756, true]
[11, 705432, true]
[12, 2704156, true]
[13, 10400600, true]
[14, 40116600, true]
[15, 155117520, true]
[16, 601080390, true]
[17, 2333606220, true]
[18, 9075135300, true]
[19, 35345263800, true]
[20, 137846528820, true]
[21, 538257874440, true]
[22, 2104098963720, true]
[23, 8233430727600, true]
[24, 32247603683100, true]
[25, 126410606437752, true]
[26, 495918532948104, true]
[27, 1946939425648112, true]
[28, 7648690600760440, true]
[29, 30067266499541040, true]
[30, 118264581564861424, true]
[31, 465428353255261088, true]
[32, 1832624140942590534, true]
[33, 7219428434016265740, true]
[34, 28453041475240576740, true]
[35, 112186277816662845432, true]
[36, 442512540276836779204, true]
[37, 1746130564335626209832, true]
[38, 6892620648693261354600, true]
[39, 27217014869199032015600, true]
[40, 107507208733336176461620, true]
[41, 424784580848791721628840, true]
[42, 1678910486211891090247320, true]
[43, 6637553085023755473070800, true]
[44, 26248505381684851188961800, true]
[45, 103827421287553411369671120, true]
[46, 410795449442059149332177040, true]
[47, 1625701140345170250548615520, true]
[48, 6435067013866298908421603100, true]
[49, 25477612258980856902730428600, true]
[50, 100891344545564193334812497256, true]
[1, 3, true]
[2, 27, true]
[3, 300, true]
[4, 3675, true]
[5, 47628, true]
[6, 640332, true]
[7, 8833968, true]
[8, 124227675, true]
[9, 1772928300, true]
[10, 25601084652, true]
[11, 373225729968, true]
[12, 5484344754252, true]
[13, 81129360270000, true]
[14, 1207006196670000, true]
[15, 18046083758212800, true]
[16, 270973226431914075, true]
[17, 4084288492517016300, true]
[18, 61768560534979567500, true]
[19, 936965754818692830000, true]
[20, 14251249130792317944300, true]
[21, 217291154547500103985200, true]
[22, 3320424336845683407178800, true]
[23, 50842036159640899051320000, true]
[24, 779930957476713513919207500, true]
[25, 11984731064970170540288110128, true]
[26, 184451393491049784469167896112, true]
[27, 2842929845357250175988436873408, true]
[28, 43876850929620825420229701745200, true]
[29, 678030386065817178550897983211200, true]
[30, 10489883439533820437936337242480832, true]
[31, 162467664010428078458110763285207808, true]
[32, 2518883431474175950782193826089803867, true]
[33, 39090110185411913285784275170723310700, true]
[34, 607181676893820341660503845125871770700, true]
[35, 9439320697768093540067457327818042449968, true]
[36, 146863011226694319553950778980033185155212, true]
[37, 2286728960780289346685182472416645270101168, true]
[38, 35631164555094536219125073150536370205870000, true]
[39, 555574423792650901362768070242025348982520000, true]
[40, 8668349947224835688512588815951200507499768300, true]
[41, 135331455095162753009711112960037659797039809200, true]
[42, 2114055315534186406992970197690928431614075386800, true]
[43, 33042833217381280239100507687002613127986359480000, true]
[44, 516738026079253946549073848518435493317621394430000, true]
[45, 8085100058417324465412768304423758108778032721540800, true]
[46, 126564675961727530998266794572652440262364629427371200, true]
[47, 1982178148289690204805811690826384709514154241588652800, true]
[48, 31057565604712593920785504357132156255842434080447207500, true]
[49, 486831544814228731696244582251156115303992440254773470000, true]
[50, 7634297553158809278967829041029729737751087851099255647152, true]