内容説明
「トランプカードでツーペアとなる組合せは何通りか」、「4けたの電話番号で、すべての数字が異なるものは何通りか」、「凸十角形をたがいに交わらない対角線で三角形に分割する方法は何通りか」、「階段を1段または2段ごとに上がるとき、n段の階段を上がる方法を列挙せよ」、「長方形の部屋に隙間なく畳を敷く方法を列挙せよ」などのように、与えられた条件を満たすものを数え上げたり、列挙したりする問題が多数考えられる。これらの問題は、具体的で親しみやすいところから、全部調べて条件に適合するものを選べば解けるだろうと思いがちである。ところが、実際に解こうとしても行き詰まったり、解が得られても、解が重複していないだろうかとか、見落としをしていないだろうかなどの不安が残る。本書は、このような問題を解くのに有用な考え方として、順列・組合せ、数学的帰納法、包除原理、漸化式、母関数、ブール技法を紹介し、解説している。
目次
1 組合せ数学の基礎
2 数学的帰納法
3 順列・組合せ
4 包除原理
5 漸化式
6 母関数
7 文字列の組合せ論
8 カタラン数
9 ブール技法