概観と歴史
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/20 09:41 UTC 版)
組合せ数学は理論構築と同じくらい、（特に20世紀後半以降は）与えられた問題を解決することが目標になっている。組合せ数学のうちで最も古く取っ付きやすいものはグラフ理論であり、今では他の様々な分野と結びつけられている。 組合せ論的な問いの例として、52枚のトランプカードの並べ方は何通りあるか？というものが挙げられる。これに対する答えは 52! （52 の階乗）であり、この数は（だいたい 8.065817517094 × 1067）、8 の後ろにゼロが67個もついている驚くべきスケールの大きさだとも言える。これは例えば無量大数（1068）に匹敵するほど大きい。 別の種類の問題には、n人の人でいくつかのグループを作るとき、それぞれの人が少なくとも1つのグループに属し、どの2人をとっても共通してちょうど1つのグループに属しており、どの2グループをとっても共通の人がちょうど1人ずついて、n-1人以上からなるグループがないような分け方はあるか？というものがある。答えはnにより、今でも部分的な回答しかえられていない。組み合わせ論的な記述の最も古い記録はインドに見いだすことができる。紀元前6世紀にスシュルタ(en:Sushruta)によって書かれた医学書スシュルタ・サミタ(en:Sushruta Samhita)には六つの味を63通りに組み合わせることができると書かれている。苦味、酸味、塩味、甘味、渋味、辛味を一つだけ使うか二つ一緒に使うか、三つ同時に使うか、などなど。ここで、単純な味は6種類あり、二つの組み合わせは15種類あり、三つの組み合わせは20種類ある、などがいえる。紀元前300年頃にジャイナ教の数学者によって書かれたバガバティ・スートラは C ( n , 1 ) = n {\displaystyle \ C(n,1)=n} , C ( n , 2 ) = n ( n − 1 ) 1 ⋅ 2 {\displaystyle C(n,2)={\frac {n(n-1)}{1\cdot 2}}} , C ( n , 3 ) = n ( n − 1 ) ( n − 2 ) 1 ⋅ 2 ⋅ 3 {\displaystyle C(n,3)={\frac {n(n-1)(n-2)}{1\cdot 2\cdot 3}}} P ( n , 1 ) = n {\displaystyle \ P(n,1)=n} , P ( n , 2 ) = n ( n − 1 ) {\displaystyle \ P(n,2)=n(n-1)} , P ( n , 3 ) = n ( n − 1 ) ( n − 2 ) {\displaystyle \ P(n,3)=n(n-1)(n-2)} に対応する組合せと順列の規則を含んでいる（記号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世紀にははっきりとした研究分野として確立した。近年の主要な組合せ論学者には、主に極値組合せ論に関する仕事をしてすばらしい問題を提起し解き続けたポール・エルデシュや、1960年代における数え上げ化・代数化の定式化に大きな役割を果たした ジャン・カルロ・ロタがいる。ものをどうやって数え上げるかという研究は時に数え上げ論とよばれて別の分野だと見なされることもある。
※この「概観と歴史」の解説は、「組合せ数学」の解説の一部です。
「概観と歴史」を含む「組合せ数学」の記事については、「組合せ数学」の概要を参照ください。
- 概観と歴史のページへのリンク
