分割数計算

暑いので、またぞろ分割数計算を。

fortran66.hatenablog.com

Haskell で書いて見ましたが、文法が頭に入っていないので面倒です。途中結果などをプリントできないのも困ります。

オイラーの制限付き分割の漸化式による方法を参考に書きます。

制限付き分割 p n k は、整数 n が分割される数ですが、分割したかけらの大きさに k による何らかの制限を置くものです。分割数は p n k の関数として得られます。

このような制限付き分割を経由することで、ヤング図のマスを書きながら色々な漸化式を作ることが出来ます。

分割の生成

ここでは制限付き分割 p n k で、k は分割した破片の最大数とする。横第一行と二行目以下の再帰的合体で漸化式を作る。

制限のない分割は p n n で得られる。

main = print (partition 6) 

partition n = p n n
  where    
    p 0 _ = [[]]
    p _ 0 = []
    p n k | n  < k = []
          | otherwise = concat [p' n i| i <-[1..k]]
          
    p' n i = map (i:) (p (n-i) (min i (n-i)))      

実行結果

[[1,1,1,1,1,1],[2,1,1,1,1],[2,2,1,1],[2,2,2],[3,1,1,1],[3,2,1],[3,3],[4,1,1],[4,2],[5,1],[6]]

分割数

main = print (map (length . partition) [1..20]) 

partition n = p n n
  where    
    p 0 _ = [[]]
    p _ 0 = []
    p n k | n  < k = []
          | otherwise = concat [p' n i| i <-[1..k]]
          
    p' n i = map (i:) (p (n-i) (min i (n-i)))    

実行結果

[1,2,3,5,7,11,15,22,30,42,56,77,101,135,176,231,297,385,490,627]

制限付き漸化式による分割数の計算

fortran66.hatenablog.com

その１

横第一行と二行目以下の再帰的合体。

main = print (map q [1..20])

q n = p n n
  where
    p 0 m = 1
    p n 1 = 1
    p n m | n < 0 = 0
          | m < 0 = 0
          | otherwise = p (n - m) m  +  p n (m-1)

その２

横最下行とそれより上の行の再帰的合体。

main = print (map q [1..20])

q n = p n 1
  where
    p 0 m = 0
    p n 0 = 0
    p n m | n  < m = 0
          | n == m = 1
          | otherwise = p (n-m) m + p n (m+1)

その３

縦第一列と二列目以降の再帰的合体。

main = print (map q [1..20])

q n = sum (map (p n) [1..n]) 
  where
    p 0 m = 0
    p n 0 = 0
    p n m | n  < m = 0
          | n == m = 1
          | otherwise = p (n-1) (m-1) + p (n-m) m

実行結果

[1,2,3,5,7,11,15,22,30,42,56,77,101,135,176,231,297,385,490,627]

オンライン・コンパイラ（Fortran 無し）にて
https://repl.it