組合せ数学

組合せ数学（くみあわせすうがく、combinatorics）や組合せ論（くみあわせろん）とは、特定の条件を満たす（普通は有限の）対象からなる集まりを研究する数学の分野。特に問題とされることとして、集合に入っている対象を数えたり（数え上げ的組合せ論）、いつ条件が満たされるのかを判定し、その条件を満たしている対象を構成したり解析したり（組合せデザインやマトロイド理論）、「最大」「最小」「最適」な対象をみつけたり（極値組合せ論や組合せ最適化）、それらの対象が持ちうる代数的構造をみつけたり（代数的組合せ論）することが挙げられる。

概観と歴史

組合せ数学は理論構築と同じくらい、（特に20世紀後半以降は）与えられた問題を解決することが目標になっている。組合せ数学のうちで最も古く取っ付きやすいものはグラフ理論であり、今では他の様々な分野と結びつけられている。

組合せ論的な問いの例として、52枚のトランプカードの並べ方は何通りあるか？というものが挙げられる。これに対する答えは 52! （52 の階乗）であり、この数は（だいたい 8.065817517094 × 10⁶⁷）、8 の後ろにゼロが67個もついている驚くべきスケールの大きさだとも言える。これは例えば無量大数（10⁶⁸）に匹敵するほど大きい。

別の種類の問題には、n人の人でいくつかのグループを作るとき、それぞれの人が少なくとも1つのグループに属し、どの2人をとっても共通してちょうど1つのグループに属しており、どの2グループをとっても共通の人がちょうど1人ずついて、n-1人以上からなるグループがないような分け方はあるか？というものがある。答えはnにより、今でも部分的な回答しかえられていない。組み合わせ論的な記述の最も古い記録はインドに見いだすことができる。紀元前6世紀にスシュルタ(en:Sushruta)によって書かれた医学書スシュルタ・サミタ(en:Sushruta Samhita)には六つの味を63通りに組み合わせることができると書かれている。苦味、酸味、塩味、甘味、渋味、辛味を一つだけ使うか二つ一緒に使うか、三つ同時に使うか、などなど。ここで、単純な味は6種類あり、二つの組み合わせは15種類あり、三つの組み合わせは20種類ある、などがいえる。紀元前300年頃にジャイナ教の数学者によって書かれたバガバティ・スートラは

[math]\ C(n,1) = n[/math], [math]C(n,2) = \frac{n(n - 1)}{1\cdot 2}[/math], [math]C(n,3) = \frac{n(n - 1)(n - 2)}{1\cdot 2\cdot 3}[/math]

[math]\ P(n,1) = n[/math], [math]\ P(n,2) = n(n - 1)[/math], [math]\ P(n,3) = n(n - 1)(n - 2)[/math]

に対応する組合せと順列の規則を含んでいる（記号C(n, r)とP(n, r)については#繰り返しを許さない組合せと#繰り返しを許さない順列節を参照のこと。）。

n が 2, 3, 4 の場合には実際の数値が計算されていて、さらに著者はより大きい n についても同じ方法で計算できると述べた。

このやり方で 5, 6, 7, ..., 10 など、あるいは数えきれるもの、数えきれないもの、無限のものまでが指定される。一時に一つのものをとる、あるいは二つのものをとる、...、十個のものをとる、組合せの数が構成された以上それらはすべて達成される。

これは算術が様々な無限大の数に拡張されうることを示唆している。組合せの数と二項展開の係数との間の関係は紀元前3世紀にピンガラ(en:Pingala)によって楽曲の形で指摘されている。彼はグル(guru)（長音）とラグ(laghu)（短音）の様々な組み合わせをいわゆるパスカルの三角形（彼はメル・プラスターラ /「メル山（須弥山）の階段」と呼んだ）によって与え、公式

[math]\ C(n + 1, r) = C(n, r) + C(n,r - 1)[/math]

に基づいてパスカルよりも単純な規則を与えている。

6世紀のヴァラーハミヒラは「16 のものが 4 つの方向に行くとしたら 1820 通りの結果がある」と記している。彼はこの事実をパスカルの三角形に似た規則を用いて見いだした。9世紀にはマハーヴィーラが組合せの数を計算するアルゴリズムをはっきりとした形で与え、有名な一般式

[math]C(n,r) = \frac{n(n - 1)(n - 2)\cdots (n - r + 1)}{r!}[/math]

を示した。

時代が下って、イスラム圏の数学者たちは遅くとも13世紀から組合せの研究をしている。13世紀の初めに北アフリカのマグレブでイブン・ムニーム(Ibn Mun'im)は組合せ論の問題に取り組んでいる。彼は n 種類の色をp回組み合わせる方法の場合をすべて決定する規則を述べ、帰納的に

[math]\ C(n,p) = C(n-1, p-1) + C(n-2,p-1) + \dots + C(p-1,p-1)[/math]

の関係の算術三角形を確立させた。彼はさらに類似の公式を、わかりやすくするためにアラビア語のアルファベットを使いながら、繰り返しを許すときや許さない順列について適用した。彼は組合せ的な理由付けについてもいくつかの仕事をしている。

ペルシャの数学者アル・ファリシ(en:Al-Farisi)は13世紀の終わりに因数分解と組み合わせ方法に関連した考え方を導入した。アル・ファリシのアプローチは、彼自身も証明した算術の基本定理である自然数の素因数分解の一意性に基づいたものだった。アル・ファリシは三角数と二項係数の関係を見て取り、数学的帰納法の萌芽的な議論を用いて三角数や三角錐数、五胞体数、などと n 個の対象から k 個のものを選ぶ場合の数の間の関係を示している。

数え上げ的組合せ論は、おきうる事象を数え上げることが17世紀のパスカルらの仕事に始まる初等的な確率論で重要な問題になってからヨーロッパで大きな関心を集めるようになった。現代的な組合せ論は19世紀の終わりに発展を始め、パーシー・アレクサンダー・マクマホンによって1915年に発表された数え上げに関する系統的な書である組合せ解析やロナルド・フィッシャーによる実験計画法に関する1920年代の一連の仕事などをへて、20世紀にははっきりとした研究分野として確立した。近年の主要な組合せ論学者には、主に極値組合せ論に関する仕事をしてすばらしい問題を提起し解き続けたポール・エルデシュや、1960年代における数え上げ化・代数化の定式化に大きな役割を果たしたジアン=カルロ・ロタがいる。ものをどうやって数え上げるかという研究は時に数え上げ論とよばれて別の分野だと見なされることもある。

順列と組合せ

繰り返しを許した順列

ものを順番に並べることを考えていて、一つのものが何回も選ばれてもよいとき、可能な並べかたの数は

[math] n^r [/math]

になる。ここで n は選ぶ候補として考えているものの数で r は選択の回数である。

たとえば A, B, C, D の四つの文字を使って長さ三文字の文字列を作るやり方は 4³ 通り、つまり 64 通りある。つまり、一文字目について四つの文字のどれを選んでもよく、二文字目についてもふたたび四つの文字のどれを選んでもよく、最後の文字についてもまた四つの文字のどれを選んでもよいからである。これらをすべて掛け合わせて全体の可能性の数をえる。

繰り返しを許さない順列

ものが並ぶ順番を考えていて、それぞれものは一回しか選べないときに可能な並べ方の数は

[math]P(n, r) = \frac{n!}{(n-r)!} = n_{(r)}[/math]

になる。ここで n は選ぶ候補として考えているものの数で r は選択の回数、! 記号は階乗を表す慣用的な記号、[math]n_{(r)}[/math]は降冪を意味するポッホハマー記号である。

例えば5人の人から3人を選び出して並べる方法は 5!/(5-3)! = 60 通りある。

r = n のとき（つまり選ぶ候補になっているものをすべて選ぶとき）には公式は

[math] \frac{n!}{(n-n)!} = \frac{n!}{0!} = n![/math]

となる。ただし 0! = 1 と解釈することにする。

例えば、3人の人がいるとき、その人たちを並べる方法は 3! つまり 3 × 2 × 1 = 6 通りある。これは、最初の人として3人のうち一人を選ぶことができ、2番目の人として残りの二人のうちどちらかを選ぶことができるが、そうすると最後に並ぶ人はもう選択の余地がないからである。これらを掛け合わせて全体の可能性の数をえる。

繰り返しを許さない組合せ

選んだものがどの順番で並ぶかは問題でなくて、それぞれのものは一回までしか選べないときあり得る組合せの数は

[math]C(n, r) = {{n!} \over {r!(n - r)!}} = {n \choose r}[/math]

になる。ここで n は選ぶ候補の数で、r は選択の回数である。

たとえば10個の数があってそのうちから5個を選ぶ選び方は 10!/5!(10 - 5)! = 252 通りある。

繰り返しを許した組合せ

選んだものがどの順番で並ぶかは問題でなくて、それぞれのものを何回でも選べるとき、あり得る組合せの数は

[math]{{(n + r - 1)!} \over {r!(n - 1)!}} = {{n + r - 1} \choose {r}} = {{n + r - 1} \choose {n - 1}}[/math]

になる。ここで n は選ぶ候補の数で、r は選択の回数である。

例えば、10種類のドーナッツがあるとき3つのドーナッツを選ぶ選び方は (10 + 3 − 1)! / 3!(10 − 1)! = 220 通りある。多重集合も参照のこと。

数え上げ組合せ論

組合せ論の始まりは特定のパターンが形成される場合の数を計算することだった。S を n 個の元からなる集合とすると、S から k 個のものを選ぶ組合せは S の部分集合で k 個の元を持つもの（要素が並ぶ順番は区別されない）に対応する。S から k 個のものを選んで並べることは k 個の相異なる S の元による順列（長さが違ったり、元が同じでも順番が違う順列は区別される）に対応する。組合せや順列の数の公式は簡単に見て取れるが組合せ論のいたるところで重要な役割を果たしている。

より一般的に、数え上げ組合せ論では、(通常、自然数全体の集合を添字集合とする) 有限集合の無限族 {S_i} が与えられたとき、任意のnに対してS_nの要素の数を数える数え上げ関数 f(n)を記述する様々な方法を探究している。集合の要素数を数えるという行為はかなり大きな数学的問題であるが、組合せ的な問題では集合S(n)は割と単純な組合せ的記述を持ち、付加的な構造が少ししかないことが普通である。

そのような関数で最も簡単なものは閉じた公式であり、階乗、べき乗のような単純な関数の合成で表現できるものである。例えば、上でも述べたように、n枚のトランプの異なる並べ方の数はf(n) = n!である．

このアプローチが常に満足いくもの (すなわち実用的なもの) であるとは限らない。例えば、f(n)を区間[1,n]における異なる整数から成る部分集合で連続する2つの整数を含まないものの数であるとする。例えば、n = 4の場合、{}, {1}, {2}, {3}, {4}, {1,3}, {1,4}, {2,4}という集合が得られるので、f(4) = 8である。実際、f(n)がn+2番目のフィボナッチ数F(n+2)であることが分かるので、

[math]f(n) = \frac{\phi^{n+2}-(1-\phi)^{n+2}}{\sqrt{5}}[/math]

という閉じた公式で表現できる。ここで、[math]\phi = (1 + \sqrt 5) / 2[/math]は黄金比である。しかしながら、ここでは数え上げ関数を見ているので、結果に[math]\sqrt 5[/math]が現れていることは美的に好ましくないと考えられる。f(n)が正整数であることを確認する他の方法として、f(n)が

[math]f(n) = f(n-1) + f(n-2) \,\![/math]

という再帰関係で表現できることを考えることもできる。ただし、初期条件はf(1) = 1とf(2) = 1である。

他のアプローチには、漸近公式

[math]f(n) \sim g(n) \,[/math]

を見つけるというものがある。ここで、g(n)は「よく知られた」関数であり、 nが無限に近づくときにf(n)がg(n)に近づくものとする。いくつかの場合では、漸近関数として複雑すぎる閉じた公式を使っても数える対象の振舞に関して何も感覚を得られないので、単純な漸近関数が好まれる。上の例では、nが大きいとき、

[math]f(n) \sim \frac{\phi^{n+2}}{\sqrt{5}}[/math]

となる漸近公式が導かれる。

最後に、f(n)を母関数と呼ばれる形式級数で表現することもできる。母関数は大抵の場合、通常母関数

[math]\sum_{n\ge 0} f(n) x^n[/math]

であるか、あるいは指数型母関数

[math]\sum_{n \ge 0} f(n) \frac{x^n}{n!}[/math]

である。母関数が一旦定まると、そこから今までに説明したアプローチで得られる全ての情報を抽出することができる。それに加えて、加算、乗算、微分などの自然な演算を母関数に施すことができることも組合せ的に意味深い。それによって、１つの組合せ的問題に対する結果を他の問題を解くために拡張することができるようになる。

構造的組合せ論

組合せ的パターンや組合せ的構造に関係する定理が多く存在する。これらは集合の分割や順序付分割に焦点を当てることが多い。特に述べておきたい結果を下では紹介する。

デザイン理論

組合せ論のこの分野の単純な結果は序で述べたような集合を構成する問題に答えがあるのはnがq² + q + 1という形をしたときのみである、というものである。しかし、qが素数べきのときには解が存在し、qが2つの平方数の和であるときは解が存在するかもしれず、そして、それ以外の正整数qに対して解が存在しないということを証明するのはそれ程簡単ではない。この最後の結果はBruck-Chowla-Ryserの定理と呼ばれ、有限体に基づく構成的手法と二次形式の応用を組み合わせて証明された。

このような構造が存在するとき、その構造は有限射影平面と呼ばれる。有限幾何と組合せ論が交わっていることを示す例である。

ラムゼー理論

フランク・ラムゼイはどのような6人が集まっても、その中には常に互いに知り合いの3人か、互いに全く知らない3人が見つけられる、ということを証明した。

証明は背理法による短いものである。この主張が正しくないと仮定する。これは、どの3人を見てもその中の2人は知り合いで、2人は知り合いではない、ということを意味している。ここで、この6人の中の1人を"A"としよう。残りの5人の中には"A"と知り合いである3人か、知り合いでない3人が存在する。これは、片方の否定がもう片方になることから明らかである。では、始めの方の条件をまず仮定する。このとき3人中2人以上は互いに知り合いである。なぜなら、そうでないとすると、互いに知り合いでない3人がいることになり仮定に反するからである。しかし、そうすると、その2人はAも知っているので、この3人が互いに知り合いになってしまう。これは最初の仮定に矛盾する。もう一方の条件 (残りの5人には"A"と知り合いでない3人が存在すること) を仮定する場合も同様な矛盾が導かれる。

これはラムゼーの定理の特殊な場合である。

無秩序な配置に秩序を見出すという考えからラムゼー理論は生まれた。一言で言うと、この理論は任意に大きな配置にはある別の種類の配置を少なくとも1つは含むことを主張している。

マトロイド理論

組合せ数学のこの分野は幾何学の一部を抽象化して、線形従属関係における特定の係数に依存しないベクトル空間におけるベクトルの (普通は有限な) 集合の性質を研究している。構造的な性質だけでなく数え上げ的性質もマトロイド理論の範疇に含まれる。

例えば、ユークリッド空間におけるn個のベクトルの集合が与えられたとき、それらが生成できる平面の最大数はいくつだろうか？ (答えは二項係数C(n,2)である。) では、生成する平面の数がこれよりもちょうど1つだけ数が少なくなるベクトルの集合は存在するだろうか？これらは幾何学における極値的な問題である。

極値組合せ論

多くの極値的な問題では集合族を扱う。次はその簡単な例である。「要素数nの集合の部分集合の族で、どの2つも交わるようものの最大サイズはいくつだろうか？」答えは、部分集合全体の数の半分であり、すなわち、2^n-1である。証明：Sを要素数nの集合とする。任意の部分集合Tとその補集合S − Tの中で高々1つしか選ぶことができない。これによって、選ぶ部分集合の最大数が部分集合の総数の半分以下になることが証明された。実際にこの数を達成できることを示すためには、Sの1要素xを持ってきて、xを含む全ての部分集合を選べばよい。

より難しい問題は、極値解を特徴付けることである。この場合は、要求を満たしたまま他の選び方をすると最大数が達成できないことを示すことになる。

極値f(n)を見つけることでさえ難しい場合もよくあり、そのときには漸近的な評価を与えることになる。

確率との関係

組合せ数学を確率の基礎として応用することがある。組合せの数がわかり、それぞれの個別の事象が独立であれば、確率は組合せの数で割れば求めることができるからである^[1]。

参考文献

Graham, R.L., Groetschel M., and Lovász L., eds. (1996). Handbook of Combinatorics, Volumes 1 and 2. Elsevier (North-Holland), Amsterdam, and MIT Press, Cambridge, Mass. ISBN 0-26207169-X .
Joseph, George Gheverghese (2000). The Crest of the Peacock: Non-European Roots of Mathematics, 2nd Edition. Penguin Books. ISBN 0-14-027778-1.
Katz, Victor J. (1998). A History of Mathematics: An Introduction, 2nd Edition. Addison-Wesley Education Publishers. ISBN 0-32101618-1.
van Lint, J.H., and Wilson, R.M. (2001). A Course in Combinatorics, 2nd Edition. Cambridge University Press. ISBN 0-521-80340-3.
O'Connor, John J. and Robertson, Edmund F. (1999-2004). MacTutor History of Mathematics archive. St Andrews University.
Rashed, R. (1994). The development of Arabic mathematics : between arithmetic and algebra. London.
Stanley, Richard P. (1997, 1999). Enumerative Combinatorics, Volumes 1 and 2. Cambridge University Press. ISBN 0-521-55309-1, 0-521-56069-1.

脚注

↑ 伏見康治「確率論及統計論」第I章　数学的補助手段１節　組合わせの理論 p.3 ISBN 9784874720127 http://ebsa.ism.ac.jp/ebooks/ebook/204

組合せ数学

Contents