151115

Ruby


Dixon's identity

Dixon's identity を確認するコードを書いてみた。

def ncr(n, r)
  r = [r, n - r].min
  return 1 if r == 0
  return n if r == 1
  numerator = (n - r + 1..n).to_a
  denominator = (1..r).to_a
  (2..r).each{|p|
    pivot = denominator[p - 1]
    if pivot > 1
      offset = (n - r) % p
      (p - 1).step(r - 1, p){|k|
        numerator[k - offset] /= pivot
        denominator[k] /= pivot
      }
    end
  }
  result = 1
  (0..r - 1).each{|k|
    result *= numerator[k] if numerator[k] > 1
  }
  return result
end

def f(n)
  m = ncr(2 * n, n)
  s = m * m * m
  (0..n - 1).each{|i|
    (n - i) % 2 == 0 ? s0 = 2 : s0 = -2
    m = ncr(2 * n, i)
    s += s0 * m * m * m
  }
  s
end
ary = (0..100).map{|i| f(i)}
p ary

def g(n)
  ncr(3 * n, n) * ncr(2 * n, n)
end
ary0 = (0..100).map{|i| g(i)}

# 一致の確認
p ary == ary0

出力結果
[1, 6, 90, 1680, 34650, 756756, 17153136, 399072960, 9465511770, 227873431500, 5550996791340, 136526995463040, 3384731762521200, 84478098072866400, 2120572665910728000, 53494979785374631680, 1355345464406015082330, 34469858696831179429500, 879619727485803060256500, 22514366432046593564460000, 577831214478475823831865900, 14866378592908813372327325400, 383331414957648741501332688000, 9904298260191196595161087296000, 256376887255990870197659395110000, 6647750135792940867877229051444256, 172644824532516079698894427850821536, 4490186382903298862950669893074864640, 116939573426172903295569869740819625280, 3049327996713402817207903975524583094400, 79607789567531236214574346454361782651136, 2080571532547465690702652742505463614012416, 54432139997018169779222721652071650604875610, 1425432294246982705017331107505766145041177820, 37362109442632851178222433008152866950473778500, 980137754325264739153760087469388189649326812960, 25733153725826742295097099333513427886580242390260, 676129685550027699309454100092387144689767216053800, 17777902978506545489876283429576007693615707520173600, 467765731229343820187277358876812510123932028242832000, 12315686996104586105755778762527877375925475388598463020, 324457176864656573634444032288702901528992030374462542120, 8552867757486695393424970238902882608332272909530900345000, 225584778148789162220956705576428220142319245674420199040000, 5953061113440928872866052731353160003652422655736636347600000, 157178452094435902773657469301001507533471817141538271091744000, 4152006974608028932625878026488081410723506942789897542979264000, 109730270338441253547622797277670526373036819972871986672308480000, 2901279777984880331429724637396325141316257378084815835114447910000, 76743139816667950790962853694727450947519994203318056513168924100000, 2030807663084593981010775419611355697953653094605883738674081337103840, 53761358112015687488073030485490006896692325060431653483330466954103040, 1423761410651421368720750633530303030278157321589316089475330894446493600, 37719286813050009048579857830565358101545002334650667407111133678504507200, 999638712247086659559071129336793852567694712078807811118500826706045376000, 26501496253675160909090667202741659438188047976817213626598113156534880983040, 702813596120264168420100264216585729858529081007646807547722792977161961682240, 18644353293199621014505522244637588198370766848891683084807087573623142344534400, 494751524904085543615600166389508984331795961672670263262354070607072137577852800, 13132732232443982829670053253200410845233538310415033704522124712465804513701120000, 348695928658441817432456030627892908625692498038703169911236614657154552846287571200, 9261011514538879615581805880900871966633347705233238234250972770789560827623546227200, 246028745022037041192303334172111614264463441118214955380257372360309560800446550656000, 6537707150411741663005756625967313613818198591044569139341139971805776961073695340032000, 173769574576495682336776543913345076449313300929448789599626442561155990662132131755196250, 4619844079024722843588346052452165457336228601231068577649145511745421966180983155392703900, 122852217341117492036248772573886372340679379304913236859634164255863796803154353716269340900, 3267666462581739485214547437140127613605951857653517594350705995132576818511167260798075140000, 86933778740026044115943597885403161498827202773533829459739435577253316405624302354856749042500, 2313304017763894040968051757215233465718634387603234794004282523268687808323575481062130127325000, 61569766689937960254467232238567732176563555570135401815278063174410038614352534681265053609228000, 1639043128490957055010609938005720172022638941338998290419173768250967971015999354113676876441968000, 43641420336729707234397085212756472867338899126740342211913301549321201589378547617343908035355872500, 1162226138365172938879933484560700528501970704873097370244006742217407822698709836884633653698936895000, 30957323692831286498361413085833414734714654312050763773519142333789464028274984807887630520183881575000, 824736124322297825688612963447227057508515419837631867741241705523974030474875755265921557196920134631680, 21975733717096185796473626515288941743924095257190195678078868755258439600807864956709993625683724072130080, 585661272497616515044830110588768035917936632077689799138681405299103734411140283658246937560176292905595200, 15610703030636665846776793125239864373560149202954437762446036511266445496710354622007000225223318387231190400, 416168686146022827044820195509919665834471659091100681768269757209503477286119019709906216547453246798193472000, 11096487752511595522482872981716523639998320427696869834535650154495770372651104099596352535774485430175706753580, 295916487746676394175695527224358066635565635109344692496473794380659496878718652627644477636689318362463451889480, 7892573306437975093912735849556272407855791344513664061915171071419909900391047466127567016562144907067845845011800, 210538889733995326906395070634527081992574112904425463395271760408287705410808827225334698141906262923797923536961600, 5617055837928659338170191616631196596528072102360840913287968947967709827605550131118091967859106291865782186200825000, 149880931040957026874529904637212715163773136100448038243478807142270298522458628038440481400094901810883970179780242000, 3999851087769055453811143112178812448372753719708224985984974721269975992586370222784644193729736525125072268551149952000, 106757816983895439658994204191090459878486419137991228916459848486056354871488771622004732463638706936949015681424668160000, 2849788534514062176579024264201167056451569678637302538630261745782618487386933870371587588509615989229368107390592013520000, 76081906500907553147477119195886983641940845845402142134091838326051045515429226810690522325732671789210260531484470786400000, 2031443260542010119077007584099957194338814614328418974344795855037656286406786599717148568706192509121387445272510543678944000, 54247704004735895386090224503988423394192501938670360863508124163700900923904258122817457540081220468188278480591944401278464000, 1448805941667125372403791971777715395588045257943813217532610050473131929802523339870378813437542519711006657672236416813444800000, 38698144413464674445829484765423084201405831818668498310550180210452305718478360149170444296764273074181678349187734135669833600000, 1033760752303553842937255724765783702455843429433964728522211921330371462402629258670234458104146561388619664728641100654539104000000, 27618421889465228630876382419127612543085112945307461438488825443046409476861202917842908764569462858257996574040003060988349096960000, 737947690602566698072784902905870017174971432544507503188163987635460736549388430306764855863733935654795857679150889079441950057510000, 19719650106090269411886524406166744438123399647642206560378368733253681899310525351475171400767204106885463120020077377111711074817700000, 527009907687419540754903211816118904773454471132968541590919944400953355449003948449857277498137936662440446489932655167483200557195900000, 14085860158942600030216758021360117160948284181001167141634260650471762166454553039069953312255097835740526411846011462878675565550764000000, 376523493564631064367712071965768747782444205128669798396168767743500485766630075466163294008566118208045715304490994009624725072511252178400]
true