数学書房選書7 個数を数える
大島利雄 著
A5判・並製・240頁・定価2600円+税
高校数学を前提として、組合せ論、特に「数え上げ」を中心に解説。
離散数学入門をめざす。
数学的思考の理解のために「母関数」の概念を導入した。
まえがき
はじめに
この本は，2013年度の城西大学での理学部数学科の初年度講義「離散数学」に
関連して書かれ，他の講義でも一部参考としたノートを基にしたものである．
離散数学は，連続的でない離散的対象を扱う数学，ということで，有限なもの
を主な対象とする．組合せ論やグラフ理論が中核をなすと考えられるが，情報数
学の分野で離散数学が扱われることが多く，アルゴリズム，プログラミング，初
等整数論などと共に，情報科学に必要な数学の基礎的概念，すなわち，集合，順
列・組合せ，行列，論理と証明，帰納法，漸化式，数列なども含めた広い内容とし
て講義されることが多い．
ここに書かれた内容は，グラフ理論の部分は含めず，組合せ論，特に「数え上
げ」を中心に扱う．数学的思考のためということで，「母関数」の概念を導入し，
それを用いているが，どの部分も高校までの数学で理解できるよう，大学で初め
て習う内容の線形代数や微積分などは使わないように努めた．一方，数学的理解
を深めるため，組合せの問題のみに限らず，幅広く数学と関わる話をいくつか取
り入れている．また，最初からでなく，興味を持った話題のみを読むことも想定
している．本書の中から一つのトピックを取り上げ，より深い学修に発展させて
いくことも可能と期待している．
「数え上げ」や漸化式など，実際の計算がコンピュータのプログラムとして実
現できるものが多く，それは証明の論理やアルゴリズムを理解する上で役立つ
ので，いくつかのコンピュータ・プログラムを載せてある1）．それには，無料で
公開されていて，ほとんどのパソコンで実行できる十進BASICを用いた．十進
BASICは，初心者にも理解が容易で扱いやすいインタプリタ言語2）のBASICで
あるが，桁数に制限のない整数や分数，複素数も扱うことができる．さらに，再帰
呼び出しが可能，グラフィックの描画が可能，などの特徴があるので，数の計算
や曲線の手軽な描画に便利である．筆者はプログラミング言語としては，主にC
言語を使っているが，多項式や有理式などの文字式を扱う場合は数式処理言語3）
Risa/Asir4）を使うことが多い．これらはすべて無料で手に入り，自由に使うこと
ができる．現在のコンピュータは手計算ではとても不可能な膨大な計算をしてくれ
るので，与えられた問題を解決するための基礎となるアルゴリズムを理解すること
が重要である．他のCなどの言語や数式処理言語にも変換しやすいように，載せ
た十進BASICのプログラムでは行番号は用いていない，などの配慮をしている．
一例として取り上げたものとして，インタネット上で公開鍵暗号として用いられ
ているRSA暗号がある．初等整数論に基づいており，とても大きな素数を扱う．
その原理を解説すると共に，たとえば1000桁の最小素数を求める，とか，1000
億以下の素数の個数を求める，などが可能なプログラムやその実行結果を載せて
ある．初等整数論の話題として，m^2−2n^2＝1を満たす自然数5）mとnをすべ
て求めよ，というようなペル方程式も扱った．
大島利雄
1）本書に載せたプログラムはhttp://www.ms.u-tokyo.ac.jp/~oshima/index-j.htmlか
らダウンロードできる
2）プログラムの処理には，インタプリタとコンパイルの2通りある．前者は，人が理解でき
る言葉で書かれたプログラムを，あるいはそれをコンピュータが解釈しやすい形に直したも
のを，逐次解釈しながら実行していくもの．後者は，コンパイルを行ってから，すなわちコン
ピュータの命令に翻訳する作業を行って，言語解釈の必要のない独立して実行可能なプログラ
ムに変換してから実行するもの．両者に厳密な区別があるわけではないが，BASICはインタ
プリタ言語，Cはコンパイル言語の代表的なものである．インタプリタ言語は，プログラムの
ミスに対して優しく，ミスを発見しやすい．後者はコンパイル作業が必要であるが，様々な最
適化ができて，プログラムのより高速な実行が可能．
3）Computer algebraという．
4）竹島卓・横山和弘・野呂正行らにより富士通研究所で開発されたオープンソースの計算代
数（数式処理）システムであり，一般公開されている．Windows，Macintosh，各種Unixの
上で動作する．
5）正の整数．