組合せ数学のソースを表示

{{出典の明記|date=2024-01}}
'''組合せ数学'''（くみあわせすうがく）あるいは'''組合せ論'''（くみあわせろん、{{Lang-en-short|combinatorics}}）とは、特定の性質を備えた（普通は有限の）対象からなる集まりについて[[研究]]する[[数学]]の分野であり、[[離散数学]]と呼ばれる分野の一つである。

組合せ論において研究されるのは主に以下のような問題である：
* 特定の性質を備えた対象を数えること。（[[数え上げ組合せ論]]）
* 様々な対象が特定の性質を帯びるか判定したり、特定の性質を備えた対象を構成あるいは解析すること。（{{仮リンク|組合せデザイン|en|combinatorial design}}）
* 要素同士の関連性がなす部分的または全体的な構造について調べること。（[[グラフ理論]]）
* 特定の性質を有する対象の中で、何らかの観点における「最大（最小）」あるいは「極大（極小）」のものを特定すること。（{{仮リンク|極値組合せ論|en|extremal combinatorics}}）
* [[代数的構造]]を伴う対象について、あるいは対象に代数的構造を与えることで、上記のような組合せ論の問題に答えること。（{{仮リンク|代数的組合せ論|en|algebraic combinatorics}}）

[[数学の諸分野]]の分類体系である{{仮リンク|Mathematics Subject Classification|en|Mathematics Subject Classification|label=MSC2020}}においては、大分類として組合せ論に05が、その下の中分類として数え上げ組合せ論に05A、デザインと{{仮リンク|配置 (幾何学)|en|configuration (geometry)|label=配置}}に05B、グラフ理論に05C、極値組合せ論に05D、代数的組合せ論に05Eが、それぞれ割り当てられている<ref>{{cite web|title=Mathematics Subject Classification 2020 (MSC2020)|url=https://msc2020.org|accessdate=2024-01-19}}</ref>。

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

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

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

:<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'' についても同じ方法で計算できると述べた。
<blockquote>''このやり方で 5, 6, 7, ..., 10 など、あるいは数えきれるもの、数えきれないもの、[[無限]]のものまでが指定される<!-- "or an enumerable, unenumerable or infinite number of things may be specified." : incomprehensive to me -->。一時に一つのものをとる、あるいは二つのものをとる、...、十個のものをとる、組合せの数が構成された以上それらはすべて達成される。''</blockquote>
これは[[算術]]が様々な無限大の数に拡張されうることを示唆している。組合せの数と[[二項展開]]の[[係数]]との間の関係は紀元前3世紀にピンガラ([[:en:Pingala]])によって楽曲の形で指摘されている。彼はグル(guru)（長音）とラグ(laghu)（短音）の様々な組み合わせ<!-- 六つの音節にグルとラグをどう割り振るかを、needs more research -->をいわゆる[[パスカルの三角形]]（彼はメル・プラスターラ<!-- Meru-prasta(a)ra --> /「メル山（[[須弥山]]）の階段」と呼んだ）によって与え、公式

:<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>

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

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

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

== 順列と組合せ ==
=== 繰り返しを許した順列 ===
ものを順番に並べることを考えていて、一つのものが何回も選ばれてもよいとき、可能な並べかたの数は

:<math> n^r </math>

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

たとえば A, B, C, D の四つの文字を使って長さ三文字の文字列を作るやり方は 4<sup>3</sup> 通り、つまり 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個を選ぶ選び方は <math>{{10!} \over {5!(10 - 5)!}} = 252</math> 通りある。

=== 繰り返しを許した組合せ ===
選んだものがどの順番で並ぶかは問題でなくて、それぞれのものを何回でも選べるとき、あり得る組合せの数は
:<math>{{(n + r - 1)!} \over {r!(n - 1)!}} = {{n + r - 1} \choose {r}} = {{n + r - 1} \choose {n - 1}}</math>
になる。ここで ''n'' は選ぶ候補の数で、''r'' は選択の回数である。

例えば、10種類のドーナッツがあるとき3つのドーナッツを選ぶ選び方は <math>{{(10 + 3 - 1)!} \over {3!(10 - 1)!}} = 220</math> 通りある。[[多重集合]]<!-- multiset -->も参照のこと。

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

より一般的に、数え上げ組合せ論では、(通常、自然数全体の集合を添字集合とする) 有限集合の無限族 {''S''<sub>''i''</sub>} が与えられたとき、任意の''n''に対して''S''<sub>''n''</sub>の要素の数を数える''数え上げ関数'' ''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{\varphi^{n+2}-(1-\varphi)^{n+2}}{\sqrt{5}}</math>

という閉じた公式で表現できる。ここで、<math>\varphi = (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{\varphi^{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>

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

== 構造的組合せ論 ==
組合せ的パターンや組合せ的構造に関係する定理が多く存在する。これらは集合の分割や順序付分割に焦点を当てることが多い。<!-- See the [[List of partition topics]] for an expanded list of related topics or the [[List of combinatorics topics]] for a more general listing. --> 特に述べておきたい結果を下では紹介する。

=== デザイン理論 ===
組合せ論のこの分野の単純な結果は序で述べたような集合を構成する問題に答えがあるのは''n''が''q''<sup>2</sup> + ''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<sup>''n''-1</sup>である。証明：''S''を要素数''n''の集合とする。任意の部分集合''T''とその補集合''S'' − ''T''の中で高々1つしか選ぶことができない。これによって、選ぶ部分集合の最大数が部分集合の総数の半分以下になることが証明された。実際にこの数を達成できることを示すためには、''S''の1要素''x''を持ってきて、''x''を含む全ての部分集合を選べばよい。

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

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

== 確率との関係 ==
組合せ数学を[[確率]]の基礎として応用することがある。組合せの数がわかり、それぞれの個別の事象が独立であれば、確率は組合せの数で割れば求めることができるからである<ref>[[伏見康治]]「[[確率論及統計論]]」第I章　数学的補助手段 １節　組合わせの理論 p.3 ISBN 9784874720127 </ref><ref>{{Cite web|和書|url =https://ndlsearch.ndl.go.jp/books/R100000002-I000004069444|title =確率論および統計論 復刻版  |publisher =現代工学社  |date =  |accessdate =2019-02-28 }}</ref>。

== 関連文献 ==
* 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.
**ヴァン・リント&ウィルソン 組合せ論 上 [[神保雅一]] (監修, 翻訳), [[澤正憲]] (翻訳), [[萩田真理子]] (翻訳), 丸善出版, ISBN 978-4-62130-245-3, (2018).
* 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.
* [[Richard P. Stanley|Stanley, Richard P.]] (1997, 1999).  [http://www-math.mit.edu/~rstan/ec/ ''Enumerative Combinatorics'', Volumes 1 and 2]. [[Cambridge University Press]].  ISBN 0-521-55309-1, 0-521-56069-1.
和書：
* C.ベルジェ、野崎昭弘(訳)：「組合せ論の基礎」、サイエンス社（1973年）。
* 高橋磐郎：「組合せ理論とその応用」、岩波書店（岩波全書 316)、(1979年6月22日).
* G.ポリア、R.E.タージャン、D.R.ウッズ、今宮淳美(訳)：「組合せ論入門」、近代科学社、ISBN 4-7649-0119-6 (1986年9月10日).
* 日比孝之：「数え上げ数学」、朝倉書店、ISBN 4-254-11474-5 (1997年2月20日).
*  [[西岡弘明]]：「やさしい組合せ数学」、コロナ社、ISBN 978-4-339-02362-6 (1999年).
* 坂内英一、坂内悦子：「球面上の代数的組合せ理論」、シュプリンガー・フェアラーク東京、ISBN 4-431-70771-9 (1999年9月8日).
* 藤重悟：「グラフ・ネットワーク・組合せ論」、共立出版、ISBN 4-320-01617-3 (2002年4月15日).
* 高崎金久：「線形代数と数え上げ」、日本評論社、ISBN 978-4-535-78680-6 (2012年6月30日).
* 田澤新成：「グラフの数え上げ：母関数を礎にして」、共立出版、ISBN 978-4-320-11086-1 (2014年5月25日).

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 関連項目 ==
* [[順列]]
* [[場合の数]]
* [[数え上げ]]
* [[数え上げ数学]]
* [[組合せ (数学)]]
* [[組合せ爆発]]
* [[置換 (数学)]]
* [[重複置換]]
* [[写像12相]]
* [[樹形図]]
* [[離散数学]]
* [[グラフ理論]]
* [[数論]]

==外部リンク==
*[https://www.mat.univie.ac.at/~slc/divers/software.html Combinatorial Software and Databases]

{{DEFAULTSORT:くみあわせすうかく}}
{{数学}}
{{Normdaten}}
[[Category:組合せ論|*]]
[[Category:離散数学]]
[[Category:数学に関する記事]]