この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。(このテンプレートの使い方)
出典検索?: "組合せ数学"
組合せ数学(くみあわせすうがく、英語: combinatorics)あるいは組合せ論(くみあわせろん)とは、特定の条件を満たす(普通は有限の)対象からなる集まりを研究する数学の分野。離散数学の中核の一つとされる。特に問題とされることとして、
集合に入っている対象を数えたり(数え上げ組合せ論)、
いつ条件が満たされるのかを判定し、その条件を満たしている対象を構成したり解析したり(組合せデザイン(英語版))、
「最大」「最小」の対象を求めたり(極値組合せ論(英語版))、
対象が持つ代数的構造を明らかにしたり(代数的組合せ論(英語版))
することが挙げられる。要素同士の繋がりを扱うグラフ理論も組合せ論の一分野とされ、MSC2020(英語版)においては、大分類として組合せ論に05が、中分類として数え上げ組合せ論に05A、デザインと配置(英語版)に05B、グラフ理論に05C、極値組合せ論に05D、代数的組合せ論に05Eが割り当てられている[1]。 組合せ数学は理論構築と同じくらい、(特に20世紀後半以降は)与えられた問題を解決することが目標になっている。組合せ数学のうちで最も古く取っ付きやすいものはグラフ理論であり、今では他の様々な分野と結びつけられている。 組合せ論的な問いの例として、52枚のトランプカードの並べ方は何通りあるか?というものが挙げられる。これに対する答えは 52! (52 の階乗)であり、この数は(だいたい 8.065817517094 × 1067)、8 の後ろにゼロが67個もついている驚くべきスケールの大きさだとも言える。これは例えば無量大数(1068)に匹敵するほど大きい。 別の種類の問題には、n人の人でいくつかのグループを作るとき、それぞれの人が少なくとも1つのグループに属し、どの2人をとっても共通してちょうど1つのグループに属しており、どの2グループをとっても共通の人がちょうど1人ずついて、n-1人以上からなるグループがないような分け方はあるか?というものがある。答えはnにより、今でも部分的な回答しかえられていない。組み合わせ論的な記述の最も古い記録はインドに見いだすことができる。紀元前6世紀にスシュルタ(en:Sushruta
概観と歴史
に対応する組合せと順列の規則を含んでいる(記号C(n, r)とP(n, r)については#繰り返しを許さない組合せと#繰り返しを許さない順列節を参照のこと。)。
n が 2, 3, 4 の場合には実際の数値が計算されていて、さらに著者はより大きい n についても同じ方法で計算できると述べた。
このやり方で 5, 6, 7, ..., 10 など、あるいは数えきれるもの、数えきれないもの、無限のものまでが指定される。一時に一つのものをとる、あるいは二つのものをとる、...、十個のものをとる、組合せの数が構成された以上それらはすべて達成される。
これは算術が様々な無限大の数に拡張されうることを示唆している。組合せの数と二項展開の係数との間の関係は紀元前3世紀にピンガラ(en:Pingala)によって楽曲の形で指摘されている。彼はグル(guru)(長音)とラグ(laghu)(短音)の様々な組み合わせをいわゆるパスカルの三角形(彼はメル・プラスターラ /「メル山(須弥山)の階段」と呼んだ)によって与え、公式 C ( n + 1 , r ) = C ( n , r ) + C ( n , r − 1 ) {\displaystyle \ C(n+1,r)=C(n,r)+C(n,r-1)}
に基づいてパスカルよりも単純な規則を与えている。
6世紀のヴァラーハミヒラは「16 のものが 4 つの方向に行くとしたら 1820 通りの結果がある」と記している。彼はこの事実をパスカルの三角形に似た規則を用いて見いだした。9世紀にはマハーヴィーラが組合せの数を計算するアルゴリズムをはっきりとした形で与え、有名な一般式 C ( n , r ) = n ( n − 1 ) ( n − 2 ) ⋯ ( n − r + 1 ) r ! {\displaystyle C(n,r)={\frac {n(n-1)(n-2)\cdots (n-r+1)}{r!}}}
を示した。
時代が下って、イスラム圏の数学者たちは遅くとも13世紀から組合せの研究をしている。13世紀の初めに北アフリカのマグレブでイブン・ムニーム(Ibn Mun'im)は組合せ論の問題に取り組んでいる。彼は n 種類の色をp回組み合わせる方法の場合をすべて決定する規則を述べ、帰納的に C ( n , p ) = C ( n − 1 , p − 1 ) + C ( n − 2 , p − 1 ) + ⋯ + C ( p − 1 , p − 1 ) {\displaystyle \ C(n,p)=C(n-1,p-1)+C(n-2,p-1)+\dots +C(p-1,p-1)}
の関係の算術三角形を確立させた。彼はさらに類似の公式を、わかりやすくするためにアラビア語のアルファベットを使いながら、繰り返しを許すときや許さない順列について適用した。彼は組合せ的な理由付けについてもいくつかの仕事をしている。
ペルシャの数学者アル・ファリシ(en:Al-Farisi)は13世紀の終わりに因数分解と組み合わせ方法に関連した考え方を導入した。アル・ファリシのアプローチは、彼自身も証明した算術の基本定理である自然数の素因数分解の一意性に基づいたものだった。アル・ファリシは三角数と二項係数の関係を見て取り、数学的帰納法の萌芽的な議論を用いて三角数や三角錐数、五胞体数、などと n 個の対象から k 個のものを選ぶ場合の数の間の関係を示している。
数え上げ的組合せ論は、おきうる事象を数え上げることが17世紀のパスカルらの仕事に始まる初等的な確率論で重要な問題になってからヨーロッパで大きな関心を集めるようになった。現代的な組合せ論は19世紀の終わりに発展を始め、パーシー・アレクサンダー・マクマホンによって1915年に発表された数え上げに関する系統的な書である組合せ解析やロナルド・フィッシャーによる実験計画法に関する1920年代の一連の仕事などをへて、20世紀にははっきりとした研究分野として確立した。