【メモ帳】制限付き分割 p(n,5)

Andrews & Eriksson 「整数の分割」演習 88

だいぶ昔に読んでたアンドリューズとエリクソンの「整数の分割」の演習問題 88. が面倒くさかったので飛ばしていたのですが、夏休みなので暇つぶしに Maple/Mathematica の手を借りてやってみました。すぐ忘れるのでメモしておきます。

整数の分割

きんもーっ☆・エリクソン

Integer Partitions

演習 88.

であることを証明せよ。

（ここで p(n,5) は整数ｎを１から５までの数に分割するときの組み合わせの個数、中括弧は四捨五入、 は床関数になってます。）

例 p(n, 4)、 4 までの制限つき分割

-n=1　p(1, 4)=1 
O
-n=2　p(2 ,4)=2
O, OO
O
-n=3　p(3, 4)=3
O, OO, OOO
O, O
O
-n=4　p(4, 4)=5
O, OO, OO, OOO, OOOO
O, O,  OO, O
O, O
O
-n=5　p(5, 4)=6
O, OO, OO, OOO, OOO, OOOO
O, O,  OO, O,   OO,  O
O, O,  O,  O
O, O
O   

導出

部分分数に展開の上で、いくつかの項をまとめた。（部分分数展開 Maple convert(f, parfrac), Mathematica Apart[f]）　

級数に展開すると

ここで、二段目の項は区間 [0, 14/45] に収まるので、とりあえず無視しておく。

１段目の項をさらに変形すると、

ここで、因数分解の係数を合わせるために（答えから逆算して）余分な項を付け足し、二段目でそれをキャンセルさせている。この項は先ほど無視することにした項と合わせて値は区間 [-7/64, 99/320] になるが、四捨五入に影響しないので無視できる。また前の方の項から値を借りてきて後ろの項を整えている。

ここで 、

であるので、これを用いて一段目の式を変形すると、

ここで、 の項は因数分解の都合合わせで出る余りで、今までの半端な項と合わせてやって区間 [-163/576,391/2880] となって絶対値は 1/2 に満たないので四捨五入に影響しない。よって無視できる。

以上のことから

であることが示せた。

無視できるカスの項は適当な計算なので間違ってたらゴメンｗ

その他

演習87. は、上記と同じ方法で求まる。

演習86. は等式変形としては求められるが、何か求め方があってこの形になっているのではないかと思われるがよく分からんｗ

いじっているうちに、副産物として が出てきた。こっちの方があぶれるカス項が小さい。

Fortran にて

４までの分割は、３までの分割の和で表わせるので、それをプログラムする。

４段のヤング図の４段目を０から１個づつ増やして行くと、残りの n-4i 個を３段のヤング図にするだけの可能性がある。その総和を求めれば p(n, 4)。なお p(n,3)=round((n+3)^2/12)。これは上記の論法を３段と２段でやれば求まる。２段は１段とやればよい。

この方法で演習86. が出来ないかと思ったが、うまくいかなかったｗ

Modern Fortran Explained: Incorporating Fortran 2018 (Numerical Mathematics and Scientific Computation)

ソース・プログラム

    module m_mod
        implicit none
    contains
        integer function p4(n) 
            integer, intent(in) :: n
            integer :: i
            p4 = 0
            do i = 0, n / 4
                p4 = p4 + p3(n - 4 * i) 
            end do
        end function p4
        
        integer function p3(n)
            integer, intent(in) :: n
            p3 = nint((n + 3)**2 / 12.0)        
        end function p3
    end module m_mod
        
    program partition4
      use m_mod
      implicit none
      integer :: i
      do i = 1, 10
          print *, i, p4(i)
      end do 
    end program partition4

実行結果

           1           1
           2           2
           3           3
           4           5
           5           6
           6           9
           7          11
           8          15
           9          18
          10          23
続行するには何かキーを押してください . . .