仙波一郎：組合せ数学

概要

まえがきから引用する：

（前略）与えられた条件を満たすものを数え上げたり，列挙したりする問題が多数考えられる。（中略） 本書は，このような問題を解くのに有用な考え方として，順列・組合せ，数学的帰納法， 包除原理，漸化式，母関数，ブール技法を紹介し，解説している．（後略）

章末には演習問題がある。数学の問題だけでなく、プログラミングの問題もある。巻末には演習問題の解答がある。

感想

要再読である。

カタラン数

第８章の演習問題（８）は、「カタラン数の近似値を求めるプログラムを書け」である。近似値というのはどういうことか、すぐにはわからなかったが、 p.118 の表 8.2 に「カタラン数 `c_n` の近似値」が載っていた。`n = 100` では `0.89652 times 10^57` であり、 `n = 9000` では `0.22904 times 5413` である。なるほどこれでは、近似値にならざるを得ない。

解答となるプログラムを見ても、なぜこの式になるかどうかがわからない。p.116 に書かれているカタラン数の定義は次のとおりである。`n` は0 以上の整数である。

`C_n = 1/(n+1) ((2n),(n)) = ((2n),(n)) - ((2n),(n-1))`

BDD パッケージ

第 9 章では「ブール技法」と題して、二分決定グラフ（binary decision diagram, BDD）を利用した各種問題の解法について述べられている。 p.130 で BDD パッケージが紹介されているが、BDD パッケージの利用方法については示されていない。 少し調べると、現京都大学教授である湊真一氏が GitHub で公開している SAPPOROBDD があり、 本書で言及されている BDD パッケージはおそらくこの SAPPROBDD であろうという見当がついた。 というのは、仙波氏の論文である下記ページ
https://repository.kulib.kyoto-u.ac.jp/dspace/bitstream/2433/59445/1/0906-24.pdf
ブール処理のパズルへの応用(アル ゴリズムと計算量理論)
の謝辞に BDD パッケージの利用を許可していただいた平石教授、 湊氏に感謝いたします。 とあることあり、湊氏と BDD パッケージの関連について調べた結果 SAPPROBDD にたどりついたからだ。

数式の記述

数式は ASCIIMathML を、 数式表記は MathJax を用いている。

書誌情報