組合せ数学
(組合せ論 から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/02/08 14:45 UTC 版)
|
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 (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年頃にジャイナ教の数学者によって書かれたバガバティ・スートラは
組合せ論
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/11/14 14:14 UTC 版)
組合せ論の中で特に大きい分野の一つであるラムゼー理論の中心的定理、ラムゼーの定理 はある集合上に与えられた一件無秩序な構造にたいし、十分大きく等質な部分集合が取れることを表している。以下のラムゼーフィルターはこの大きさを表すものとみなすことが出来る。以下 X を無限集合 U を X 上の自由な超フィルターとする。このとき U がラムゼーとは、X の二元集合上の関数 f: [X]2 → {0, 1} が与えられたとき、「ある A ∈ U が存在して、[A]2 ⊆ f−1({0}) または [A]2 ⊆ f−1{1})」となること。 U が κ-一様選抜的（英: uniformly selective）とは、X の任意の κ の分割 P が与えられたとき、「Q⊆ P が存在して |Q| < κ かつ ⋃ Q ∈ U {\textstyle \bigcup Q\in U} であるかさもなくば、ある A ∈ U が存在して、任意の B ∈ P に対し、|B ∩ A| = 1」となること。 U がP-点 とは、X の任意の可算分割 P が与えられたとき、「P ∩ U ≠ ∅ であるかさもなくば、ある A ∈ U が存在して、任意の B ∈ P に対し、|B ∩ A| < ∞」となること。 ただし、P ⊆ P(X) が互いに素な集合からなる集合族でその合併が X と一致するとき X の分割といい、[A]2 := {B ⊆ A : |B| = 2} とする。特に U が ω-一様選抜的なとき単に選抜的といい、|X|-一様選抜的なとき一様選抜的という。 無限グラフとその頂点集合上のラムゼーフィルター U を固定する。このとき有限色の辺彩色が任意に与えられれば、彩色に関する等質集合を U の元に取れる。これがラムゼーという呼び名の由来である。 このP-点の定義は β(X) ∖ X 上の位相的なP-点の定義と一致する。明らかに選抜的ならP-点である。ウォルター・ルーディンは連続体仮説から可算集合上のラムゼーフィルターの存在を証明している。更にマーティンの公理を始めとする様々な仮定からラムゼーフィルターの存在は証明されている。逆にサハロン・シェラハはP-pointの存在がZFCから示せないことを証明した。以上からこれらの存在はZFCから独立であることが分かる。 このようなフィルターの性質は「無限の組合せ論」等と呼ばれる集合論の分野の一部をなし、集合論的な議論の基礎をなしている。 基本性質 自由な超フィルターがラムゼーであることと選抜的であることは同値。 自由な超フィルターが選抜的であることと、自由な超フィルター全体のルディン・キースラー順序に関する極小元であることが同値。 自由な超フィルターが κ-一様選抜的であることと、κ-一様で自由な超フィルター全体のルディン・キースラー順序に関する極小元であることが同値。
※この「組合せ論」の解説は、「超フィルター」の解説の一部です。
「組合せ論」を含む「超フィルター」の記事については、「超フィルター」の概要を参照ください。
- 組合せ論のページへのリンク
