組み合わせ種

組合せ 数学において、組合せ種の理論は、離散構造の生成関数を導く抽象的で体系的な方法であり、これらの構造を単に数えるだけでなく、それらを含む全単射の証明を与えることを可能にする。組合せ種の例としては、（有限）グラフ、順列、木などがあり、これらにはそれぞれ、特定のサイズの構造がいくつあるかを数える関連する生成関数がある。種理論の目標の1つは、複雑な構造をより単純な構造の変換と組み合わせで記述することにより、分析できるようにすることである。これらの操作は、生成関数の同等の操作に対応するため、複雑な構造に対してそのような関数を作成することは、他の方法を使用するよりもはるかに簡単です。この理論は、アンドレ・ジョワイアルを中心としたカナダの研究者によって導入され、慎重に練られ、適用されました。

理論の威力は、その抽象化のレベルから生まれます。種は純粋に代数的なので、構造の「記述形式」（グラフの隣接リストと隣接行列など）は無関係です。カテゴリ理論は、ここで生じる概念に便利な言語を提供しますが、種を扱う前にカテゴリを理解する必要はありません。

種のカテゴリーは有限集合における対称列のカテゴリーと同等である。^[1]

あらゆる種は、ある有限集合の要素に基づいて構築された個々の組み合わせ構造で構成されます。たとえば、組み合わせグラフは、特定の頂点集合間のエッジの構造であり、グラフの種にはすべての有限集合上のすべてのグラフが含まれます。さらに、種のメンバーは、その基礎となる集合を他の同数集合の要素で再ラベル付けできます。たとえば、グラフの頂点を再ラベル付けすると、新しい頂点に「同じグラフ構造」、つまり同型グラフが得られます。

これにより、組合せ論的種の正式な定義が導かれる。を有限集合のカテゴリとし、カテゴリの射はこれらの集合間の全単射である。種は関手である^[2]${\displaystyle {\mathcal {B}}}$

${\displaystyle F\colon {\mathcal {B}}\to {\mathcal {B}}.}$

の各有限集合Aに対して、有限集合F [ A ] ^{[注 1]は}A上のF構造の集合、またはA上の種Fの構造の集合と呼ばれます。さらに、関数の定義により、 φ が集合AとB の間の全単射である場合、F [φ] はF構造の集合F [ A ] とF [ B ]の間の全単射であり、これを φ に沿った F 構造の転送と呼びます。^[3]${\displaystyle {\mathcal {B}}}$

例えば、「順列の種」^[4]は、各有限集合A をAのすべての順列（ A をリストに並べるすべての方法）の集合S [ A ] に写像し、 Aから別の集合Bへの各一対一変換fは、自然に、 Aの各順列をBの対応する順列、すなわち一対一変換にする一対一変換（ラベル付けの変更）を誘導します。同様に、「分割の種」は、各有限集合にそのすべての分割の集合を割り当てることによって定義でき、「べき集合の種」は、各有限集合にそのべき集合を割り当てます。隣の図は、5つの異なる要素（青い点で表される）の集合上に構築された構造（赤い点で表される）を示しています。対応する構造は、任意の5つの要素から構築できます。 ${\displaystyle S[f]:S[A]\to S[B]}$

2つの有限集合は、それらが同じ濃度（要素数）を持つときは常に一対一である。したがって、定義により、対応する種の集合も一対一であり、（有限）濃度はAの濃度のみに依存する。^{[注 2]}特に、種Fの指数生成級数F ( x )は次のように定義できる。^[5]${\displaystyle F[A]}$

${\displaystyle F(x)=\sum _{n\geq 0}\operatorname {Card} F[n]{\frac {x^{n}}{n!}}}$

ここで、 はn個の要素を持つ任意の集合Aの濃度です。たとえば、 です。 ${\displaystyle \operatorname {カード} F[n]}$${\displaystyle F[A]}$${\displaystyle A=\{1,2,\dots ,n\}}$

例: 執筆、 ${\displaystyle f_{n}=\operatorname {カード} F[n]}$

• 集合の種（伝統的にはフランス語の「ensemble 」（集合）からEと呼ばれます）は、 A を{ A }にマップする関数です。 このとき、 なので です。${\displaystyle f_{n}=1}$${\displaystyle E(x)=e^{x}}$
• 上で説明した順列の種Sには、. .${\displaystyle f_{n}=n!}$${\displaystyle S(x)=1/(1-x)}$
• 順序付きペア（2組）の種T ₂は、集合AをA ²に取る関手である。そして、である。${\displaystyle f_{n}=n^{2}}$${\displaystyle T_{2}(x)=x(x+1)e^{x}}$

生成関数の算術は、種に対する特定の「自然な」演算に対応します。基本的な演算は、加算、乗算、合成、微分です。また、種に対する等式を定義する必要があります。カテゴリ理論には、2 つの関数が等しい場合を記述する方法がすでにあります。それは、自然同型です。このコンテキストでは、それは各Aについて、 A上のF構造とA上のG構造の間に一対一の関係があり、トランスポートとの相互作用において「行儀が良い」ことを意味します。同じ生成関数を持つ種は同型ではない可能性がありますが、同型の種は常に同じ生成関数を持ちます。

種の加算は、集合の非結合和によって定義され、構造の選択に対応します。^[6]種FとGについて、 ( F + G )[ A ] をF [ A ] とG [ A ]の非結合和 (「+」とも表記) として定義します。したがって、 ( F  +  G )( x ) =  F ( x ) +  G ( x ) となります。デモンストレーションとして、E ^{+ を}空でない集合の種 (その生成関数はE ⁺ ( x ) =  e ^x  − 1)、1 を空集合の種(その生成関数は1 ( x ) = 1) とします。したがって、2 つの種の合計はE  =  1  +  E ⁺となります。つまり、「集合は空か非空かのどちらかです」。このような式は、単一の構造を参照していることも、構造のコレクション全体を参照していることも読み取ることができます。

種の乗算はもう少し複雑です。定義として集合の直積を取ることも可能ですが、これの組み合わせ論的解釈は完全には正しくありません。（この種の積の使用については以下を参照してください。） 同じ集合に無関係な2つの構造をまとめるのではなく、乗算演算子は集合を2つの要素に分割し、一方にF構造、もう一方にG構造を構築するというアイデアを使用します。^[7]

${\displaystyle (F\cdot G)[A]=\sum _{A=B+C}F[B]\times G[C].}$

これは、 Aのすべての可能な二分分割上の互いに素な和です 。乗算は結合法則と可換法則（同型性を除く ）があり、加算に対して分配法則があることは簡単に示せます。生成級数に関しては、 ( F  ·  G )( x ) =  F ( x ) G ( x ) です。

下の図は、5 つの要素を持つセット上の( F  ·  G ) 構造の 1 つを示しています。 F構造 (赤) は基本セットの 3 つの要素を取り、G構造 (水色) は残りを取ります。他の構造では、FとG がセットを別の方法で分割します。セット ( F  ·  G )[ A ] ( Aは基本セット) は、このようなすべての構造の互いに素な和集合です。

種の加算と乗算は、数え上げの和と積の規則を最も包括的に表現したものです。^[要出典]

合成は置換とも呼ばれ、さらに複雑です。基本的な考え方は、Fの要素をG構造に置き換えて ( F  ∘  G ) を形成することです。^{[8]乗算と同様に、これは入力セット}A を分割することによって行われます。つまり、互いに素な部分集合をGに与えてG構造を作成し、部分集合の集合をFに与えてG構造をリンクするF構造を作成します。合成が機能するためには、 G が空集合を自身にマッピングする必要があります。正式な定義は次のとおりです。

${\displaystyle (F\circ G)[A]=\sum _{\pi \in P[A]}(F[\pi ]\times \prod _{B\in \pi }G[B]).}$

ここで、P は分割の種類なので、P [ A ] はAのすべての分割の集合です。この定義は、 ( F  ∘  G )[ A ]の元がAの何らかの分割上のF構造と、分割の各要素上のG構造から構成されることを示しています。生成する級数は です。 ${\displaystyle (F\circ G)(x)=F(G(x))}$

そのような構造の 1 つを以下に示します。3 つのG構造 (水色) が 5 要素の基本セットを分割し、次にG構造を接続するためにF構造 (赤) が構築されます。

最後の 2 つの操作は、木の例で説明できます。まず、X を、生成系列がX ( x ) =  xである種「シングルトン」として定義します。次に、根付き木の種Ar (フランス語の「樹木化」に由来) がAr  =  X  ·  E ( Ar ) によって再帰的に定義されます。この式は、木が単一の根と一連の (サブ) 木で構成されることを示しています。再帰には明示的な基本ケースは必要ありません。再帰は、ある有限集合に適用されるコンテキストでのみ木を生成します。これについて考える 1 つの方法は、Ar関数が集合からの要素の「供給」に繰り返し適用されていると考えることです。つまり、そのたびに、 1 つの要素がXによって取得され、他の要素がEによってArサブツリーに分配され、 Eに渡す要素がなくなるまで続きます。これは、種の代数的記述がHaskellなどのプログラミング言語の型仕様とはまったく異なることを示しています。

同様に、種P はP  =  E ( E ⁺ )として特徴付けることができます。「パーティションは、空でない集合のペアワイズ分離集合です (入力集合のすべての要素を使用します)。」Pの指数生成級数はであり、これはベル数の級数です。 ${\displaystyle P(x)=e^{(e^{x}-1)}}$

種の分化は、直感的には、下の図に示すように、「穴のある構造物」を構築することに相当します。

正式には、^[9]

${\displaystyle (F')[A]=F[A\uplus \{\star \}],}$

には存在しない、いくつかの新しい特徴的な要素があります。 ${\displaystyle \star}$${\displaystyle A}$

関連する指数級数を微分するには、係数のシーケンスを 1 つ「左」にシフトする必要があります (最初の項が失われます)。これは、種の定義を示唆しています: F' [ A ] =  F [ A  + {*}]、ここで {*} は単一のセット、"+" は互いに素な和です。種の理論のより高度な部分では、種と級数に関する微分方程式を構築して解くために、微分化が広範に使用されています。構造の 1 つの部分を追加 (または削除) するというアイデアは強力です。これは、一見無関係な種間の関係を確立するために使用できます。

たとえば、線形順序の種Lの構造、つまり基底集合の要素のリストを考えてみましょう。リストの要素を削除すると、リストは 2 つの部分 (空の場合もあります) に分割されます。記号で表すと、これはL'  =  L · Lです。Lの指数生成関数はL ( x ) = 1/(1 −  x )であり、実際次のようになります。

${\displaystyle {\frac {d}{dx}}{(1-x)}^{-1}={(1-x)}^{-2}.}$

一般化された微分化の公式は、1964 年に発表された NG de Bruijn による以前の研究に記載されています。

巡回置換の種Cは、集合A をA上のすべての巡回の集合にします。巡回から 1 つの要素を削除すると、リストC'  =  Lになります。Lの生成関数を積分して、 Cの生成関数を生成 できます。

${\displaystyle C(x)=1+\int _{0}^{x}{\frac {dt}{1-t}}=1+\log {\frac {1}{1-x}}.}$

種の統合の良い例は、（体によって座標化された）直線を無限点と完成させ、射影直線を得ることです。

種に対して実行できる操作は他にも様々あります。これらは、有向グラフやバイグラフなどのより複雑な構造を表現するために必要です。

指示は構造内の単一の要素を選択します。^[10]種Fが与えられた場合、対応する指示された種F ^{• は}F ^• [ A ] = A × F [ A ]で定義されます。したがって、各F ^•構造は、 1つの要素が区別されたF構造です。指示は、関係F ^• = X · F'によって微分化に関連付けられているため、F ^• ( x ) = x F' ( x ) です。指示された集合の種E ^•は、多くのより複雑な構成の構成要素として特に重要です。

2 つの種の直積^{[要出典]は}、同じセット上に同時に 2 つの構造を構築できる種です。基本セットのすべての要素が 2 つの構造間で共有されるという点で、通常の乗算​​演算子とは異なります。 ( F × G ) 構造は、 F構造とG構造の重ね合わせとして考えることができます。バイグラフは、グラフとツリーのセットの重ね合わせとして説明できます。バイグラフの各ノードはグラフの一部であると同時に、ノードがどのようにネストされているかを説明するツリーの一部でもあります。生成関数 ( F × G )( x ) は、 F ( x ) とG ( x )のアダマール積または係数ごとの積です。

種E ^• × E ^•は、基本セットから 2 つの独立した選択を行っていると見ることができます。2 つの点は、異なるように強制されるX · X · Eとは異なり、一致する可能性があります。

関数者として、種FとG は関数合成によって組み合わせることができます: ^[要出典] (ボックス記号が使用されています。これは、円がすでに置換に使用されているためです)。これにより、集合AのすべてのG構造の集合上にF構造が構築されます。たとえば、F が集合をその冪集合に取る関数である場合、合成された種の構造はA上のG構造の何らかのサブセットです。ここで、上からG をE ^• × E ^•とすると、自己ループが許される有向グラフの種が得られます。(有向グラフはエッジの集合であり、エッジはノードのペアです。したがって、グラフはノード集合Aの要素のペアの集合のサブセットです。) 他のグラフ族、および他の多くの構造も、この方法で定義できます。 ${\displaystyle (F\,\Box \,G)[A]=F[G[A]]}$

種に対する演算はSageMath ^[11]でサポートされており、特別なパッケージを使用することでHaskellでもサポートされている。^{[12] [13]}

• k ソートの種は関数です。ここで、生成される構造は異なるソースから抽出された要素を持つことができます。^[要出典]${\displaystyle {\mathcal {B}}^{k}\rightarrow {\mathcal {B}}}$
• への関数、すなわちRが冪級数の環であるRの重み付き集合のカテゴリは、重み付き種である。^[要出典]${\displaystyle {\mathcal {B}}_{R}}$

「全単射を持つ有限集合」を「線型変換を持つ有限ベクトル空間」に置き換えると、 （有限性条件を課した後）多項式関数の概念が得られます。 ^[要出典]

• コンテナ（型理論）

• ジョヤル、アンドレ（1981年10月）。 「一連の形式を組み合わせた理論」。数学の進歩。42 (1): 1-82。土井：10.1016/0001-8708(81)90052-9。
• Bruijn, de, NG (1964). Pólya の計数理論。EF Beckenbach (編)、応用組合せ数学 (pp. 144-184)
• ラベル、ジャック。プチ カルディナリテのアンサンブル シュール エスペセス。、アン。 Sc.数学。ケベック 9.1 (1985): 31-58。
• Labelle, J.; Yeh, YN (1989). 「バーンサイド環と組み合わせ種の関係」.組み合わせ理論ジャーナル. シリーズ A. 50 (2): 269–284. doi : 10.1016/0097-3165(89)90019-8 .
• Yves Chiricota、高度分子の分類 6 および 7、Ann.科学。数学。ケベック 17 (1993)、いいえ。 1、11–37。
• François Bergeron、Gilbert Labelle、Pierre Leroux、「Théorie des espèces et combinatoire des Structure arborescentes」、LaCIM、モントリオール (1994)。英語版: Combinatorial Species and Tree-like Structures 2006 年 10 月 2 日にWayback Machineにアーカイブ、Cambridge University Press (1998)。
• ケルバー、アダルベルト (1999)、「応用有限群作用」、アルゴリズムと組合せ論、19 (第 2 版)、ベルリン、ニューヨーク: Springer-Verlag、ISBN 978-3-540-65941-9、MR 1716962、OCLC 247593131 

• ワイスタイン、エリック W.「種」。MathWorld。
• nラボの種