181212

Ruby


1212

この記事は
日曜数学 Advent Calendar 2018 (https://adventar.org/calendars/3009)
の12/12 分として書いております。
前回はだまさんの「初等的解法の存在する角度の問題」でした。

「1が2個, 2が2個」を一列に並べるとき、
同じ数字が並ばない並べ方は何通りあるでしょう。
解：1212、2121の2通り。

「1が9個, 2が9個, ... , 9が9個」を一列に並べるとき、
同じ数字が並ばない並べ方は何通りあるでしょう。
また、
「1がn個, 2がn個, ... , nがn個」を一列に並べるとき、
同じ数字が並ばない並べ方の個数を高速に求めるには
どうすればよいでしょうか？

数学の知識と初歩的なプログラミングの知識が必要になります。

①数学の知識
パスカルの三角形とは次のようなものです。
1,
1, 1,
1, 2, 1,
1, 3, 3, 1,
1, 4, 6, 4, 1,
...
さて次のように細工します。
 1/1,
-1/1,  1/2,
 1/1, -2/2,  1/6,
-1/1,  3/2, -3/6,  1/24,
 1/1, -4/2,  6/6, -4/24, 1/120,
...
これらを係数にもつ多項式q_i(x) を作ります。
q_1(x) =  x,
q_2(x) = -x + 1/2 * x^2,
q_3(x) =  x - 2/2 * x^2 + 1/6 * x^3,
q_4(x) = -x + 3/2 * x^2 - 3/6 * x^3 + 1/24 * x^4,
q_5(x) =  x - 4/2 * x^2 + 6/6 * x^3 - 4/24 * x^4 + 1/120 * x^5,
...
さて、q_i(x) は次のような驚くべき性質を持っています。

「1がm_1個, 2がm_2個, ... , kがm_k個」を一列に並べるとき、同じ数字が並ばない並べ方は
Integral_{0..infinity} Product_{i=1..k} q_{m_i}(x) * exp(-x) dx.

ちなみに、Integral_{0..infinity} x^m * exp(-x) dx = m! ですので、
多項式の掛け算をして、係数を求めることが重要であることがわかります。

今回の場合に当てはめると
Integral_{0..infinity} (q_n(x))^n * exp(-x) dx
となります。

②プログラミングの知識
 (q_n(x))^n の計算はバイナリ法を用いると計算回数が少なくてすみます。

これらをもとに実装すると次のようになり、
n = 9 のときは、
11655577382287102750765311537460065620507094071664576111302628243840
通りと求まります。

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 power(ary, n)
  return [1] if n == 0
  k = power(ary, n >> 1)
  k = mul(k, k)
  return k if n & 1 == 0
  return mul(k, 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(n)
  ary = power([0] + (1..n).map{|i| (-1) ** (n - i) * ncr(n - 1, n - i) / f(i).to_r}, n)
  (0..ary.size - 1).inject(0){|s, i| s + f(i) * ary[i]}.to_i
end

n = 20
(0..n).each{|i| p [i, A(i)]}

出力結果
[0, 1]
[1, 1]
[2, 2]
[3, 174]
[4, 2265024]
[5, 7946203275000]
[6, 12229789732207993835280]
[7, 12202002913678756821228939869239920]
[8, 10937192762438008527903830198163831816546577931520]
[9, 11655577382287102750765311537460065620507094071664576111302628243840]
[10, 18877545858631350177544126730326118579042534510881427013497201905522243828084277155584000]
[11, 57814365142525615345822290635367980031764472894406481579410336826627768364093502411683595510203294058889662636800]
[12, 407658789636795392873224914660821849906640854496041813132347715886561006703544292229875155619913436614371595102735557393480894068396031590400]
[13, 7916240618568924952784422376897285074349407297177155333772267175236361650837449810625502710956077916339020347009688544252921894901829502808023567304468717311128650695552000]
[14, 498961977012237615935915814835809945218689415847045000987626530145354117671508674820161361629165453542631518534948206591419638038499418413317775100822845509486513888639232738104669714232846642736185909196800]
[15, 118813418570954352257626152461870566748175083811925094869482044671635443619567119146472438369570944844793864117533983401043281073111768900013398219072288449242647438928900346234820007048719066622523886248828693230918893944171625097165388804864000]
[16, 123074415490344199979921662196075276052024358457569576638878274700296813263968616812171263108052043597819537373317572776761453007104704321107605953901687032805754242905638392434082191822082575494722399225216595810131347324670136983012576738242197768842539749995881462695930820212498432000]
[17, 632673322223167150563381180449202895810656486275138980768979126849568078803929001026198717240246438492208986017127366607503113807961453674908153743390688559089518342608243133491125088605989422356306262511591012413333743083156845181593352662535492648478551130685710723664924508871843351853059474256064874854425780258865548135985152000]
[18, 18262485268060395471719629462211789200248188118212907564935177446312080481434798754251346826458783843905735671916454235952642336679346522571446273991105431911451246995478453093531740103567375709740164836196952627498127365568349243885731021363958900889615826228391994012608680368231380597695100532416438065107000126490501124888837506361583551279679270162874801672720230508095201280000]
[19, 3325346401901827184405264043746239777213987165498607952527099919169429535191502889521807119252816036721707694000409416885917354468125596599265774644403590455801186699549289399295618384982739223055026353093870119637734650695671402196886800379294232694826306609192327108837847109423774316242807710788886545902961566935329488725575424433775416001359407137834222431223588069183910836336963435557633128490071733441789088652042060740714496000]
[20, 4263374507224750254652747946709751036907009890731720806160330060792101908200442231854976249703550510732440932255817411768387265800055035356279767743465046586935783799213627064605070089606422958689740675558147647400901384320375900390925397265681026115099056542471222575925955266135626206309095922246090256122147265738804913109253904934843458466990632702917971742764047620310632779114398031596958284411852848038321222991793804098769489620905040225884507551867559309764993380559572463906816000000]