組合せ論

組合せ論は、結果を得るための手段と目的の両方としての数え上げと、有限構造の特定の特性に主眼を置く数学の分野です。他の多くの数学の分野と密接に関連しており、論理学から統計物理学、進化生物学からコンピューターサイエンスまで、さまざまな分野に応用されています。

組合せ論は、取り組む問題の幅広さでよく知られています。組合せ論の問題は、純粋数学の多くの分野、特に代数学、確率論、位相幾何学、幾何学で生じ、^[1]またはその多くの応用分野で生じます。多くの組合せ論の問題は歴史的に孤立して考えられ、何らかの数学的文脈で生じる問題に対するアドホックな解決策を与えてきました。しかし、20世紀後半には、強力で一般的な理論的手法が開発され、組合せ論はそれ自体で独立した数学の一分野となりました。^[2]組合せ論の最も古く、最も理解しやすい部分の1つはグラフ理論であり、それ自体が他の分野と数多くの自然なつながりを持っています。組合せ論は、アルゴリズムの分析における公式や推定値を得るために、コンピュータサイエンスで頻繁に使用されます。

組合せ論を研究する数学者は組合せ学者と呼ばれます。

組合せ論の全範囲については、普遍的な合意が得られていません。^[3] HJ Ryserによれば、この分野は数学的に非常に多くの分野にまたがるため、定義が難しいとのことです。^[4]分野が扱う問題の種類によって説明できる限り、組合せ論は以下の分野に関係しています。

• 有限システムに関連する特定の構造（非常に一般的な意味では配置や構成と呼ばれることもある）の列挙（数えること）
• 特定の基準を満たす構造の存在、
• これらの構造物の建設は、おそらくさまざまな方法で、
• 最適化: いくつかの可能性の中から「最大」、「最小」、またはその他の最適基準を満たす「最良」の構造またはソリューションを見つけること。

レオン・ミルスキーは「組合せ論とは、共通点を持ちながらも、目的、方法、達成した一貫性の度合いが大きく異なる一連の関連した研究である」と述べています。^[5]組合せ論を定義する 1 つの方法は、おそらく、その細分化をその問題と手法で説明することです。これは、以下で使用するアプローチです。ただし、一部のトピックを組合せ論の傘下に含めるか含めないかについては、純粋に歴史的な理由もあります。^{[6]主に有限のシステムに関係していますが、一部の組合せ論の問題と手法は、無限 (具体的には}可算) でありながら離散的な設定に拡張できます。

基本的な組合せ論の概念と列挙の結果は古代世界中に現れた。インドの 医師 スシュルタはスシュルタ・サンヒターの中で、6つの異なる味を1つずつ、2つずつなどと組み合わせると63通りの組み合わせができ、2 ⁶  − 1 通りの可能性がすべて計算できると主張している。 ギリシャの 歴史家 プルタルコスは、クリュシッポス（紀元前3世紀）とヒッパルコス（紀元前2世紀）の間で行われた、かなり微妙な列挙問題に関する議論について論じているが、これは後にシュレーダー・ヒッパルコス数に関連していることが示された。^{[7] [8] [9]}それ以前には、オストマキオンでアルキメデス（紀元前3世紀）がタイルパズルの構成の数について考察していた可能性があり、^[10]アポロニウスの失われた著作にも組合せ論への関心が見られた可能性がある。^{[11] [12]}

中世には、組合せ論の研究は主にヨーロッパ文明の外で続けられました。インドの数学者マハーヴィーラ（ 850年頃）は順列と組み合わせの数に関する公式を提供しました[ ^{13] [14]。}これらの公式は6世紀にはインドの数学者によく知られていた可能性があります。 [ ^15] 哲学者で天文学者のラビ・アブラハム・イブン・エズラ（ 1140年頃）は二項係数の対称性を確立し、その後、タルムード学者で数学者のレヴィ・ベン・ゲルソン（ゲルソニデスとして知られる）が1321年に閉じた公式を得ました。^[16] 算術三角形（二項係数の関係を示す図式）は、10世紀にまで遡る論文で数学者によって提示され、最終的にはパスカルの三角形として知られるようになりました。その後、中世イングランドでは、鐘楼学が、順列に関する特定のケーリーグラフで現在ハミルトンサイクルとして知られているものの例を示しました。^{[17] [18]}

ルネサンス期には、他の数学や科学とともに、組合せ論も復活を遂げました。パスカル、ニュートン、ヤコブ・ベルヌーイ、オイラーの著作が、この新興分野の基礎となりました。近代では、 JJシルベスター（19世紀後半）とパーシー・マクマホン（20世紀初頭）の著作が、列挙的組合せ論と代数的組合せ論の基礎を築くのに役立ちました。グラフ理論も、特に4色問題との関連で、同時期に関心が高まりました。

20世紀後半には、組合せ論は急速な成長を遂げ、この分野で数十の新しい雑誌や会議が設立されました。^{[19]この成長は、代数から確率、}関数解析から数論など、他の分野との新たなつながりや応用によって部分的に促進されました。これらのつながりにより、組合せ論と数学や理論計算機科学の一部との間の境界が取り払われましたが、同時にこの分野の一部の断片化にもつながりました。

列挙的組合せ論は、組合せ論の最も古典的な分野であり、特定の組合せオブジェクトの数を数えることに重点を置いています。集合内の要素の数を数えることは、かなり広範な数学的問題ですが、応用で生じる問題の多くは、比較的単純な組合せ論的記述を持っています。フィボナッチ数は、列挙的組合せ論の問題の基本的な例です。12倍の方法は、順列、組み合わせ、および分割を数えるための統一されたフレームワークを提供します。

解析的組合せ論は、複素解析と確率論のツールを使用した組合せ構造の列挙に関係します。明示的な組合せ式と生成関数を使用して結果を記述する列挙的組合せ論とは対照的に、解析的組合せ論は漸近的な式を得ることを目的としています。

分割理論は、整数分割に関連するさまざまな列挙および漸近問題を研究し、q 級数、特殊関数、直交多項式と密接に関連しています。もともと数論と解析学の一部でしたが、現在では組合せ論の一部​​または独立した分野と見なされています。解析学と解析的数論における全単射アプローチとさまざまなツールを組み込んでおり、統計力学とのつながりがあります。分割は、ヤング図またはフェラーズ図を使用してグラフィカルに視覚化できます。分割は、対称多項式と対称群の研究や、一般的な 群表現論を含む、数学と物理学の多くの分野で発生します。

グラフは組合せ論における基本的なオブジェクトです。グラフ理論の検討対象は、列挙（例：n頂点、 k辺のグラフの数）から既存の構造（例：ハミルトン閉路）、代数表現（例：グラフGと 2 つの数xとyが与えられたとき、トゥッテ多項式 T _G ( x , y ) には組合せ論的解釈があるか）まで多岐にわたります。グラフ理論と組合せ論の間には非常に強いつながりがありますが、別々の分野と考えられることもあります。^[20] 組合せ論的手法は多くのグラフ理論の問題に適用されますが、この 2 つの分野は一般に異なるタイプの問題の解決策を模索するために使用されます。

デザイン理論は、特定の交差特性を持つサブセットのコレクションである組み合わせデザインを研究する分野です。ブロックデザインは、特殊なタイプの組み合わせデザインです。この分野は、1850 年に提案されたカークマンの女子高生問題のように、組み合わせ論の最も古い分野の 1 つです。この問題の解決は、有限単純群の分類で重要な役割を果たすシュタイナー システムの特殊なケースです。この分野は、さらに、符号理論や幾何組み合わせ論 とも関連しています。

組み合わせ計画理論は実験計画の分野に応用できる。組み合わせ計画の基本理論の一部は、統計学者ロナルド・フィッシャーの生物学的実験計画に関する研究に由来する。現代では、有限幾何学、トーナメントスケジュール、宝くじ、数理化学、数理生物学、アルゴリズム設計と分析、ネットワーク、グループテスト、暗号化など、幅広い分野で応用されている。^[21]

有限幾何学は、有限個の点のみを持つ幾何学システムの研究です。連続幾何学 (ユークリッド平面、実射影空間など) に見られる構造に類似していますが、組み合わせ的に定義される構造が主な研究対象です。この分野は、設計理論の豊富な例を提供します。離散幾何学 (組み合わせ幾何学) と混同しないでください。

順序理論は、有限集合と無限集合の両方について半順序集合を研究する学問です。これは、「これはあれより小さい」や「これはあれに先行する」などのステートメントを記述するための正式な枠組みを提供します。半順序のさまざまな例は、代数、幾何学、数論、および組合せ論とグラフ理論の全体に現れます。半順序の注目すべきクラスと例には、格子とブール代数があります。

マトロイド理論は幾何学の一部を抽象化します。線形依存関係の特定の係数に依存しないベクトル空間内のベクトルの集合 (通常は有限集合) の特性を研究します。構造だけでなく列挙特性もマトロイド理論に属します。マトロイド理論はハスラー・ホイットニーによって導入され、順序理論の一部として研究されました。現在では、組合せ論の他の部分と多くのつながりを持つ独立した研究分野となっています。

極限的組合せ論は、有限オブジェクト（数値、グラフ、ベクトル、集合など）の集合が、ある一定の制約を満たす場合に、どれだけ大きく、あるいはどれだけ小さくなれるかを研究する。極限的組合せ論の多くは集合系のクラスに関するもので、これは極限的集合論と呼ばれる。たとえば、n要素の集合において、互いに交差できるk要素の部分集合の最大数はいくつだろうか。どの部分集合も他の部分集合を含まない部分集合の最大数はいくつだろうか。後者の質問に対する答えは、極限的集合論の多くを生み出した シュペルナーの定理である。

この場合に扱われるタイプの問題は、特定の特性を満たす最大のグラフに関するものです。たとえば、2n頂点上の最大の三角形のないグラフは、完全な二部グラフK _n,nです。多くの場合、極値解f ( n ) を正確に見つけることさえ困難であり、漸近推定値しか与えることができません。

ラムゼー理論は極限組合せ論の別の部分です。十分に大きな構成には何らかの秩序が含まれると主張しています。これは鳩の巣原理の高度な一般化です。

確率的組合せ論における質問は、次のようなものです。ランダム グラフなどのランダムな離散オブジェクトにおける特定のプロパティの確率はどれくらいでしょうか。たとえば、ランダム グラフ内の三角形の平均数はどれくらいでしょうか。確率的方法は、特定の規定されたプロパティ (明示的な例を見つけるのが難しい場合があります) を持つ組合せオブジェクトの存在を、それらのプロパティを持つオブジェクトをランダムに選択する確率が 0 より大きいことを観察することによって決定するためにも使用されます。このアプローチ (確率的方法と呼ばれることが多い) は、極値組合せ論やグラフ理論への応用において非常に効果的であることが証明されています。密接に関連する分野は、特に組合せオブジェクトにおける有限 マルコフ連鎖の研究です。ここでも、確率的ツールは混合時間を推定するために使用されます。^{[説明が必要]}

確率的組合せ論は、この分野で先駆的な研究を行ったポール・エルデシュと関連付けられることが多く、伝統的には組合せ論の他の分野の問題を研究するためのツールセットと見なされていました。この分野は最近になって、組合せ論の独立した分野に成長しました。

代数的組合せ論は、抽象代数学、特に群論と表現論の手法をさまざまな組合せの文脈で採用し、逆に代数の問題に組合せ論的手法を適用する数学の一分野である。代数的組合せ論は、組合せ論的手法と代数的手法の相互作用が特に強く重要な数学の一分野として、より広範に見られるようになってきた。したがって、組合せ論的トピックは、本質的に列挙的であったり、マトロイド、多面体、半順序集合、有限幾何学に関係したりする。代数側では、群論と表現論の他に、格子理論と可換代数が一般的である。

単語の組合せ論は形式言語を扱う。これは数論、群論、確率論など数学のいくつかの分野から独立して生まれた。これは列挙的組合せ論、フラクタル解析、理論計算機科学、オートマトン理論、言語学に応用されている。多くの応用は新しいが、形式文法のクラスの古典的なチョムスキー-シュッツェンベルガー階層は、おそらくこの分野で最もよく知られている成果である。

幾何組合せ論は、凸幾何学および離散幾何学に関連しています。例えば、凸多面体は各次元の面をいくつ持つことができるかが問われます。多面体 の計量特性も重要な役割を果たします。例えば、凸多面体の剛性に関するコーシーの定理などです。また、パーミュトヘドラ、アソシアヘドラ、バーコフ多面体などの特殊な多面体も考慮されます。組合せ幾何学は、離散幾何学の歴史的な名前です。

これには、多面体組合せ論（凸多面体の面の研究）、凸幾何学（凸集合の研究、特にそれらの交差の組合せ論）、離散幾何学など、多くのサブ領域が含まれており、離散幾何学は計算幾何学に多くの応用があります。正多面体、アルキメデスの立体、キス数などの研究も幾何学的組合せ論の一部​​です。パーミュトヘドロン、アソシアヘドロン、バーコフ多面体などの特殊多面体も考慮されます。

位相幾何学の概念と方法の組み合わせ類似物は、グラフの色付け、公平な分割、分割、半順序集合、決定木、ネックレス問題、離散モース理論の研究に使用されます。代数位相幾何学の古い名前である組み合わせ位相と混同しないでください。

算術的組合せ論は、数論、組合せ論、エルゴード理論、調和解析の相互作用から生まれました。算術演算（加算、減算、乗算、除算）に関連する組合せ推定に関するものです。加法数論（加法的組合せ論と呼ばれることもあります）は、加算と減算の演算のみが関係する特殊なケースを指します。算術的組合せ論の重要な手法の 1 つに、動的システムのエルゴード理論があります。

無限組合せ論、あるいは組合せ集合論は、組合せ論の考え方を無限集合に拡張したものである。これは数理論理学の一分野である集合論の一部であるが、集合論と極限組合せ論の両方のツールと考え方を使用する。研究対象には、連続グラフと連続木、ラムゼーの定理の拡張、マーティンの公理などがある。最近の発展は、連続体の組合せ論^[22]と特異基数の継承者に関する組合せ論に関するものである。 ^[23]

ジャン・カルロ・ロータは、数え上げと測度の間に多くの類似点があるため、幾何学的確率を説明するために連続組合せ論^[24]という名前を使用しました。

組み合わせ最適化は、離散的および組み合わせ的オブジェクトにおける最適化の研究です。組み合わせ論とグラフ理論の一部として始まりましたが、現在ではオペレーションズ・リサーチ、アルゴリズム理論、計算複雑性理論に関連する応用数学とコンピュータサイエンスの分野と見なされています。

符号理論は、誤り訂正符号の初期の組み合わせ構成とともに設計理論の一部として始まりました。この主題の主な考え方は、効率的で信頼性の高いデータ伝送方法を設計することです。現在では、情報理論の一部である大規模な研究分野となっています。

離散幾何学（組合せ幾何学とも呼ばれる）も組合せ論の一部​​として始まり、凸多面体やキス数に関する初期の成果がありました。離散幾何学の計算幾何学への応用の出現により、これら 2 つの分野は部分的に統合され、別の研究分野になりました。幾何学的組合せ論や位相的組合せ論とのつながりは数多く残っており、それ自体が初期の離散幾何学の派生と見ることができます。

動的システムの組み合わせ的側面は、もう 1 つの新しい分野です。ここでは、組み合わせオブジェクト上で動的システムを定義できます。たとえば、 グラフ動的システムを参照してください。

組合せ論と物理学、特に統計物理学との相互作用は増加しています。例としては、イジングモデルの正確な解や、一方ではポッツモデルと他方では 彩色多項式およびタット多項式との関係が挙げられます。

• ビョルナー、アンダース、スタンレー、リチャード P. (2010)、コンビナトリアル雑集
• ボナ、ミクロス。 (2011);組み合わせ論のウォークスルー (第 3 版)。ISBN 978-981-4335-23-2、978-981-4460-00-2​​ 
• グラハム、ロナルド L.、グロッシェル、マーティン、およびロヴァース、ラースロー編 (1996);組合せ論ハンドブック、第 1 巻および第 2 巻。アムステルダム、オランダ、およびケンブリッジ、マサチューセッツ州: エルゼビア (ノースホランド) および MIT プレス。ISBN 0-262-07169 -X 
• Lindner, Charles C.;およびRodger, Christopher A.;編(1997); Design Theory 、 CRC -Press。ISBN 0-8493-3986-3。 
• リオーダン、ジョン（2002）[1958]、組合せ分析入門、ドーバー、ISBN 978-0-486-42536-8
• ライザー、ハーバート・ジョン（1963）、組合せ数学、カルス数学モノグラフ（＃14）、アメリカ数学協会
• スタンレー、リチャード P. ( 1997、1999); 列挙的組合せ論、第 1 巻および第 2 巻、ケンブリッジ大学出版局。ISBN 0-521-55309-1、0-521-56069-1 
• スティンソン、ダグラス R. (2003)、コンビナトリアルデザイン：構築と分析、ニューヨーク：シュプリンガー、ISBN 0-387-95487-2
• van Lint, Jacobus H.; および Wilson, Richard M.; (2001); A Course in Combinatorics 、第 2 版、ケンブリッジ大学出版局。ISBN 0-521-80340-3 

• 「組合せ解析」、数学百科事典、EMS Press、2001 [1994]
• 組み合わせ分析 –ブリタニカ百科事典第 11 版の記事
• Combinatorics、多くの参考文献があるMathWorld の記事。
• MathPages.comポータルからの組合せ論。
• 数学記事のリンクを集めた「The Hyperbook of Combinatorics」。
• WT Gowers 著「数学の 2 つの文化」、問題解決と理論構築に関する記事。
• 「組合せ論用語集」は 2017-08-17 にWayback Machineにアーカイブされました
• 組合せ論ソフトウェアとデータベースのリスト