両替問題

両替問題の続きである. 前回の話題はSICPの再帰関数の解法であった. コンピュータの数学やPolyaの解法は, 母関数による. コンピュータの数学は, 「この問題はPolyaが母関数を用いて解くよい教材であることを示して, 一躍有名になった」と書く.

母関数

数列を閉じた式で表す摩可不思議な方法である. Fibonacci数は0,1,1,2,3,5,8,...であるが, The Art of Computer Programmingの1.2.8の式(11)には, その母関数がG(x)=x/(1-x-x²)であると書いてある. (元はxでなくzだが) これをばか正直に割ってみると, 商のx^nの係数がfib(n)になる. つまり無限数列0,1,1,2,3,5,8,...を「閉じた式」にしたものが母関数である.



日本語は母関数だが, 英語ではgenerating functionという. なにかを産み出すという意味で, 母関数という訳語は悪くない. 統計には母集団があり, 円柱や円錐には母線があり, 分数には分母があり, 音声には母音がある. 母国語もある. 航空母艦や潜水母艦や捕鯨母船もあるが, 残念にも父の出番はあまりない.

「閉じた式」にするとなにがいいか. 例えば1,1,1,1,...に1,1,1,1,...を掛けると1,2,3,4,...になりそうである. 一方 1,1,1,1,...は閉じた形では1+x+x²+x³+...=1/(1-x)である. 従って1,1,1,1,...掛ける1,1,1,1,...は
1/(1-x)*1/(1-x)=1/(1-2x+x²)
これをばか正直に割ってみると
1+2x+3x²+4x³+...
が得られる.

私も真面目に読んだのではないが, TAOCPの1.2.9項や, コンピュータの数学の7章(ともに母関数)のところは, そのうちきちんと読みたい.

そのもっとも入門的な使い方が, Polyaの講義ノートにある両替問題なので, 簡単に説明しよう.

1セント硬貨で1セント, 2セント, ...にする方法はどれも1通りなので,
1+x+x²+x³+x⁴...
のように書く. 最初の1は1セント硬貨をまったく使わない場合である.

5セントでは
1+x⁵+x¹⁰+x¹⁵+x²⁰...
xやx²の項は, 作れないから係数が0で, 省略してある.

これを10セント, 25セント, 50セントで書き, (1)式のように掛け合わせれば, x¹⁰⁰の係数のところに, 両替法の数が出るわけである.

(2)は1セントの可能性の式を閉じた形にしたもので, (1)の因子をすべて閉じた式にしたのが(3)である. 最後は(8)が欲しいのだが, それを求めるために, 1セントだけの式(4), 1セントと5セントだけの式(5), などを作る. (4)の係数Aはすべて1だから, それと(5)とからBが(9), (10)のように得られ, 順にC, D, Eが(11), (12), (13)のように得られる.

早速Schemeのプログラムを書く.

(define (a n) (if (< n 0) 0 1))
(define (b n) (if (< n 0) 0 (+ (a n) (b (- n 5)))))
(define (c n) (if (< n 0) 0 (+ (b n) (c (- n 10)))))
(define (d n) (if (< n 0) 0 (+ (c n) (d (- n 25)))))
(define (e n) (if (< n 0) 0 (+ (d n) (e (- n 50)))))

(e 100) => 292

(a b c d e)の呼ばれた回数は(292 332 49 12 4)であった.

メモ化すると(21 40 24 8 4)に減った.
メモ化にはalistを使った.

(define (e n) (set! ec (+ ec 1))
 (let ((x (assoc n ea)))
  (if x (cadr x)
   (let ((r (if (< n 0) 0 (+ (d n) (e (- n 50))))))
    (set! ea (cons (list n r) ea)) r))))

のように書いてある.