組合せ数学
![]() | この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。(2024年1月) |
組合せ数学(くみあわせすうがく)あるいは組合せ論(くみあわせろん、英: 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)によって書かれた医学書スシュルタ・サミタ(en:Sushruta Samhita)には六つの味を63通りに組み合わせることができると書かれている。苦味、酸味、塩味、甘味、渋味、辛味を一つだけ使うか二つ一緒に使うか、三つ同時に使うか、などなど。ここで、単純な味は6種類あり、二つの組み合わせは15種類あり、三つの組み合わせは20種類ある、などがいえる。紀元前300年頃にジャイナ教の数学者によって書かれたバガバティ・スートラは