読者です 読者をやめる 読者になる 読者になる

fortran66のブログ

fortran について書きます。

百万の分割数 p(10**6) および攪乱順列

攪乱分割類?

対称群の指標を手計算するとき、一つ下の指標を利用して6~7割がたはさっさと求まます。下図に S(6) と S(7) の指標の写しを示しますが、緑線で結んだところは、横軸の類の方で言えば、あみだくじで関わらない線を一本新たに付け加えたことに相当します。縦軸の規約表現の方でみると、ヤング図を描いてマスを1個加える先祖の S(6) の規約表現の指標から簡単な足し算で出てきます。

http://cdn-ak.f.st-hatena.com/images/fotolife/f/fortran66/20160623/20160623023251.png?1466616801

のこりのピンクの部分は、あみだくじでいえば全員参加でかき混ぜてあるものに対応します。ただし、全部が完全に混ぜ合わせられているのは (7) だけで、例えば (2 5) では、あみだでいえば2本と5本のあみだの合成になっています。 

いずれにせよ、このピンク側では置換によって元と同じ位置に来るものが無い場合に対応しています。これは、攪乱順列と言われるもので、江戸時代にすでにオイラーが扱っていたものです。これは、数が増えると、総置換数に対する割合が e^-1 に比例することが知られています。

表の位数をみて見ると、S(6) の場合、(120+90+15+40) / 6! = 265 / 720 ~ 0.368055..、S(7) の場合、(504+210+420+720) / 7! = 1854 / 5040 ~ 0.3678571.. となっています。これらの値は、すでに e^-1 = 1/2.718281828 ~ 0.367879.. に近い値になっています。

さて、問題は位数ではなくて、類の方はどうかということです。本に載っている S(10) 以下の表を見る限り、攪乱順列に対応する類の数は 1/3~1/4 くらいを占めているように見えます。位数は一定の比率を占めるようになるわけですから、類の方も一定比になってもいいような気もします。

しかし、このピンク部分にあたる類の数は、(緑の部分が一つ前の分割数なので)、分割数の差分にあたる数となります。よって攪乱順列類(命名 by オレw)の比率は、分割数の計算からすぐに求まることになります。

眠くなってきたのでここでは示しませんがw、計算して見ると S(N) の N が大きくなるにつれて、その比率はどんどん小さくなっていくことが分かります。分割数の漸近形を見ると 0 に近づいていくように思われます。位数の方は一定比なのに、類の方は比率が下がっていくので、N が大きくなるととても混み合った状況になる気がします。



分割数の計算

FMLIBの新版で計算して見ました。Intel Fortran v.17 では、FMLIB のテストプログラムでコンパイラが異常終了します。ライブラリ本体の方は、大丈夫なんですが・・・
fortran66.hatenablog.com

FMLIB を用いた分割数の計算。戯れに百万まで求めてみました。

p(10^6)=
1471684986358223398631004760609895943484030484439142125334612747351666117418918618276330148873983597555842015374130600288095929387347128232270327849578001932784396072064228659048713020170971840761025676479860846908142829356706929785991290519899445490672219997823452874982974022288229850136767566294781887494687879003824699988197729200632068668735996662273816798266213482417208446631027428001918132198177180646511234542595026728424452592296781193448139994664730105742564359154794989181485285351370551399476719981691459022015599101959601417474075715430750022184895815209339012481734469448319323280150665384042994054179587751761294916248142479998802936507195257074485047571662771763903391442495113823298195263008336489826045837712202455304996382144601028531832004519046591968302787537418118486000612016852593542741980215046267245473237321845833427512524227465399130174076941280847400831542217999286071108336303316298289102444649696805395416791875480010852636774022023128467646919775022348562520747741843343657801534130704761975530375169707999287040285677841619347472368171772154046664303121315630003467104673818

~1.47E1107

漸近形での見積もり

p(n)\sim{1\over4n\sqrt{3}}\exp(\pi\sqrt{2n\over3})

1.472337561814659748200821928561558E+1107
続行するには何かキーを押してください . . .

桁数上四倍精度で…

program test
  implicit none
  integer, parameter :: kd = 16
  real(kd), parameter :: pi = 4 * atan(1.0_kd)
  real(kd) :: r, p
  integer :: n = 10**6
  r = real(n, kd)
  p = 1.0_kd / (4.0_kd * r * sqrt(3.0_kd)) *exp(pi * sqrt(2.0_kd * r / 3.0_kd))
  print *, p
end program test