組合せ数学
組合せ論
出典: フリー百科事典『ウィキペディア（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から独立であることが分かる。 このようなフィルターの性質は「無限の組合せ論」等と呼ばれる集合論の分野の一部をなし、集合論的な議論の基礎をなしている。 基本性質 自由な超フィルターがラムゼーであることと選抜的であることは同値。 自由な超フィルターが選抜的であることと、自由な超フィルター全体のルディン・キースラー順序に関する極小元であることが同値。 自由な超フィルターが κ-一様選抜的であることと、κ-一様で自由な超フィルター全体のルディン・キースラー順序に関する極小元であることが同値。
※この「組合せ論」の解説は、「超フィルター」の解説の一部です。
「組合せ論」を含む「超フィルター」の記事については、「超フィルター」の概要を参照ください。
組合せ論
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/13 23:33 UTC 版)
Di Nassoらはα-理論と呼ばれる超準化の反復を可能とする公理的超準解析の枠組みを開発し、これを加法的組合せ論をはじめとした研究に応用している。
※この「組合せ論」の解説は、「超準解析」の解説の一部です。
「組合せ論」を含む「超準解析」の記事については、「超準解析」の概要を参照ください。
組合せ論
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/11/21 03:00 UTC 版)
「カジュダン–ルスティック多項式」の記事における「組合せ論」の解説
カジュダン・ルスティック多項式やその一般化の持つ組合せ論的な性質は現在も活発に研究されている。 表現論や代数幾何におけるカジュダン・ルスティック多項式の重要性に鑑み、カジュダン・ルスティック多項式の理論を純組合せ論的に、すなわち旗多様体の幾何学的考察を用いることはあっても、交叉コホモロジーなどの高級な道具を用いることなしに理解するいくつかの試みがなされている。この試みは、代数的組合せ論において、シューベルト多様体の特異性を組合せ論的に記述し、カジュダン・ルスティック多項式の係数に関する評価を与える pattern-avoidance phenomenon のような興味深い発展を導いた。Björner & Brenti (2005) や Billey & Lakshmibai (2000) を参照。 2005年現在、カジュダン・ルスティック多項式の係数すべてを（何らかの自然な集合の濃度の形で）組合せ論的に解釈する方法は、対称群の場合においてさえ知られていない。しかし、多くの特殊な場合において係数に対する具体的な公式は知られている。
※この「組合せ論」の解説は、「カジュダン–ルスティック多項式」の解説の一部です。
「組合せ論」を含む「カジュダン–ルスティック多項式」の記事については、「カジュダン–ルスティック多項式」の概要を参照ください。
組合せ論
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/07/01 10:24 UTC 版)
階乗を含む公式は数学の多くの分野に現れるけれども、階乗のおおもとの出自は組合せ論にある。相異なる n 個の対象の順列（k-順列）の総数は n! 通りである。 階乗はしばしば「順番を無視する」という事実を反映するものとして分母に現れる。古典的な例としては n 個の元から k 個の元を選ぶ組合せ（k-組合せ）の総数が挙げられる。このような組合せは順列から得ることができる。実際、k-順列の総数 n k _ = n ( n − 1 ) ( n − 2 ) ⋯ ( n − k + 1 ) {\displaystyle n^{\underline {k}}=n(n-1)(n-2)\cdots (n-k+1)} において、順番のみが違う（k-組合せでは違いが無視される）k-順列が k ! 通りずつ存在するから、k-組合せの総数は n k _ k ! = n ( n − 1 ) ( n − 2 ) ⋯ ( n − k + 1 ) k ( k − 1 ) ( k − 2 ) ⋯ 1 {\displaystyle {\frac {n^{\underline {k}}}{k!}}={\frac {n(n-1)(n-2)\cdots (n-k+1)}{k(k-1)(k-2)\cdots 1}}} となる。この数は、二項冪 (1 + X)n における Xk の係数となることから、二項係数 ( n k ) {\displaystyle {\tbinom {n}{k}}} とも呼ばれる。 代数学に現れる階乗にはいくつも理由があるが、既述の如く二項展開の係数として現れたり、ある種の演算の対称化（英語版） において置換による平均化を行うなど、組合せ論的な理由で現れるものもある。 微分積分学においても階乗は例えばテイラー級数の分母として現れるが、これは冪函数 xn の n 階導函数が n ! であることを補正する定数である。確率論でも階乗は用いられる。 階乗は数式操作にも有効である。例えば n の k-順列の総数を n k _ = n ! ( n − k ) ! {\displaystyle n^{\underline {k}}={\frac {n!}{(n-k)!}}} と書けば、（この数値を計算することを考えれば効率が悪くなるが）二項係数の対称性 ( n k ) = n k _ k ! = n ! ( n − k ) ! k ! = n n − k _ ( n − k ) ! = ( n n − k ) {\displaystyle {\binom {n}{k}}={\frac {n^{\underline {k}}}{k!}}={\frac {n!}{(n-k)!k!}}={\frac {n^{\underline {n-k}}}{(n-k)!}}={\binom {n}{n-k}}} を見るには都合がよい。
※この「組合せ論」の解説は、「階乗」の解説の一部です。
「組合せ論」を含む「階乗」の記事については、「階乗」の概要を参照ください。
- 組合せ論のページへのリンク
