記号的方法（組合せ論）

組合せ論において、記号法は組合せオブジェクトを数える手法です。オブジェクトの内部構造を使用して、それらの生成関数の式を導き出します。この手法は主にフィリップ・フラジョレと関連しており、ロバート・セジウィックとの共著である解析的組合せ論のパート A で詳しく説明されています。また、本の残りの部分では、複素解析を使用して対応する生成関数の漸近的および確率的結果を得る方法を説明しています。

2 世紀にわたって、生成関数は、その係数の対応する再帰性を通じて出現しました (ベルヌーイ、オイラー、アーサー・ケイリー、シュレーダー、ラマヌジャン、 リオルダン、クヌース、コンテ [fr]などの独創的な研究に見られるように)。その後、生成関数が初期の離散的組合せオブジェクトの他の多くの側面を捉えていること、そしてこれをより直接的な形式的な方法で行うことができることが徐々に認識されました。いくつかの組合せ構造の再帰的性質は、いくつかの同型性を介して、対応する生成関数の注目すべき恒等式に変換されます。Pólyaの研究に続いて、1970年代には、FoataとSchützenberger ^[1]による順列の研究、BenderとGoldmanによるプレハブの研究、^[2]、Joyalによる組合せ種に関する研究に見られるように、組合せクラスとその生成関数を指定するための言語の一般的な使用によって、この精神でさらなる進歩がなされました。^[3]

列挙におけるこの記号法は、「ブリサードの記号法」とは無関係であることに注意してください。ブリサードの記号法は、単に陰影計算の古い別名です。

組合せ論における記号的方法は、組合せ構造の多くの分析の最初のステップを構成し、その後、高速計算スキーム、漸近特性と極限法則、ランダム生成につながり、それらはすべてコンピュータ代数による自動化に適しています。

生成関数によって与えられたオブジェクトをn個のスロットのセットに分配する問題を考えます。ここで、次数nの順列群G がスロットに作用して、満たされたスロット構成の同値関係を作成し、この同値関係に関する構成の重みによって構成の生成関数について尋ねます。ここで、構成の重みは、スロット内のオブジェクトの重みの合計です。まず、ラベル付きの場合とラベルなしの場合でこの問題を解決する方法を説明し、その解決策を使用して、組み合わせ構造のクラスを作成する動機付けを行います。

ポリア列挙定理は、ラベルなしの場合にこの問題を解決します。f ( z )をオブジェクトの通常の生成関数（OGF）とすると、構成のOGFは置換サイクルインデックスによって与えられます。

${\displaystyle Z(G)(f(z),f(z^{2}),\ldots ,f(z^{n}).}$

ラベル付きの場合、オブジェクトの指数生成関数（EGF）g（z ）を使用し、ラベル付き列挙定理を適用すると、構成のEGFは次のように表される。

${\displaystyle {\frac {g(z)^{n}}{|G|}}.}$

ラベルなしの場合は PET を、ラベル付きの場合はラベル付き列挙定理を使用して、満たされたスロット構成を列挙することができます。次に、スロットのセットが複数あり、それぞれに置換グループが作用している場合に得られる構成の生成関数について考えます。明らかに、軌道は交差せず、それぞれの生成関数を追加できます。たとえば、セット X に含まれるいくつかのオブジェクトの長さが 2 または 3 のラベルなしシーケンスを列挙するとします。スロットのセットが 2 つあり、最初のセットには 2 つのスロットが含まれ、2 番目のセットには 3 つのスロットが含まれます。最初のセットに作用するグループは で、2 番目のスロットに作用するグループは です。これをXの次の形式的な冪級数で表します。 ${\displaystyle E_{2}}$${\displaystyle E_{3}}$

${\displaystyle X^{2}/E_{2}\;+\;X^{3}/E_{3}}$

ここで、 という用語はGおよびによる軌道の集合を表すために使用され、これは明らかに、Xからのオブジェクトを繰り返してn個のスロットに分配するプロセスを表します。同様に、ラベル付きオブジェクトの集合Xから任意の長さのサイクルを作成するというラベル付き問題を考えます。これにより、巡回群の次の一連のアクションが生成されます。 ${\displaystyle X^{n}/G}$${\displaystyle X^{n}=X\times \cdots \times X}$

${\displaystyle X/C_{1}\;+\;X^{2}/C_{2}\;+\;X^{3}/C_{3}\;+\;X^{4}/C_{4}\;+\cdots .}$

明らかに、このような商（軌道）のべき級数には、置換群に関して意味を割り当てることができます。ここで、n次群を対称群の共役類に制限すると、一意の因数分解領域が形成されます。（同じ共役類からの 2 つの群に関する軌道は同型です。）これが次の定義の根拠となります。 ${\displaystyle \operatorname {Cl} (S_{n})}$${\displaystyle S_{n}}$

組み合わせ構造のクラスは形式的なシリーズである ${\displaystyle {\mathcal {C}}\in \mathbb {N} [{\mathfrak {A}}]}$

${\displaystyle {\mathcal {C}}=\sum _{n\geq 1}\sum _{G\in \operatorname {Cl} (S_{n})}c_{G}(X^{n}/G)}$

ここで（「A」は「原子」の略）はUFDの素数の集合であり、${\displaystyle {\mathfrak {A}}}$${\displaystyle \{\operatorname {Cl} (S_{n})\}_{n\geq 1}}$${\displaystyle c_{G}\in \mathbb {N} .}$

以下では表記を少し簡略化して、例えば次のように書きます。

${\displaystyle E_{2}+E_{3}{\text{ および }}C_{1}+C_{2}+C_{3}+\cdots .}$

上記のクラスの場合。

記号的組合せ論のフラジョレ・セジウィック理論の定理は、組合せ構造を含む方程式をこれらの構造の生成関数の方程式に直接（そして自動的に）変換することを可能にする記号演算子を作成することによって、ラベル付きおよびラベルなしの組合せクラスの列挙問題を扱います。

を組合せ構造のクラスとする。XにOGFがある場合のOGFと、 XにEGFがある場合の EGFは次のように与えられる。 ${\displaystyle {\mathcal {C}}\in \mathbb {N} [{\mathfrak {A}}]}$${\displaystyle F(z)}$${\displaystyle {\mathcal {C}}(X)}$${\displaystyle f(z)}$${\displaystyle G(z)}$${\displaystyle {\mathcal {C}}(X)}$${\displaystyle g(z)}$

${\displaystyle F(z)=\sum _{n\geq 1}\sum _{G\in \operatorname {Cl} (S_{n})}c_{G}Z(G)(f(z),f(z^{2}),\ldots ,f(z^{n}))}$

そして

${\displaystyle G(z)=\sum _{n\geq 1}\left(\sum _{G\in \operatorname {Cl} (S_{n})}{\frac {c_{G}}{|G|}}\right)g(z)^{n}.}$

ラベル付きの場合、 X にサイズ 0 の要素が含まれていないという追加の要件があります。 に 1 を追加して、空セットのコピーが 1 つ存在することを示すと便利な場合があります。 と の両方に意味を割り当てることができます(最も一般的な例は、ラベルなしセットの場合)。定理を証明するには、PET (ポリア列挙定理) とラベル付き列挙定理を適用するだけです。 ${\displaystyle G(z)}$${\displaystyle {\mathcal {C}}\in \mathbb {Z} [{\mathfrak {A}}]}$${\displaystyle {\mathcal {C}}\in \mathbb {Q} [{\mathfrak {A}}].}$

この定理の威力は、組み合わせクラスを表す生成関数の演算子を構築できる点にあります。組み合わせクラス間の構造方程式は、対応する生成関数の方程式に直接変換されます。さらに、ラベル付きの場合、式から、原子zに置き換えて結果の演算子を計算し、それを EGF に適用できることは明らかです。次に、最も重要な演算子の構築に進みます。読者は、サイクル インデックスページのデータと比較することをお勧めします。 ${\displaystyle g(z)}$

この演算子はクラスに対応します

${\displaystyle 1+E_{1}+E_{2}+E_{3}+\cdots }$

シーケンスを表します。つまり、スロットは並べ替えられず、空のシーケンスが1つだけあります。

${\displaystyle F(z)=1+\sum _{n\geq 1}Z(E_{n})(f(z),f(z^{2}),\ldots ,f(z^{n}))=1+\sum _{n\geq 1}f(z)^{n}={\frac {1}{1-f(z)}}}$

そして

${\displaystyle G(z)=1+\sum _{n\geq 1}\left({\frac {1}{|E_{n}|}}\right)g(z)^{n}={ \frac {1}{1-g(z)}}.}$

この演算子はクラスに対応します

${\displaystyle C_{1}+C_{2}+C_{3}+\cdots }$

つまり、少なくとも1つのオブジェクトを含むサイクルです。

${\displaystyle F(z)=\sum _{n\geq 1}Z(C_{n})(f(z),f(z^{2}),\ldots ,f(z^{n}))=\sum _{n\geq 1}{\frac {1}{n}}\sum _{d\mid n}\varphi (d)f(z^{d})^{n/d}}$

または

${\displaystyle F(z)=\sum _{k\geq 1}\varphi (k)\sum _{m\geq 1}{\frac {1}{km}}f(z^{k})^ {m}=\sum _{k\geq 1}{\frac {\varphi (k)}{k}}\log {\frac {1}{1-f(z^{k})}}}$

そして

${\displaystyle G(z)=\sum _{n\geq 1}\left({\frac {1}{|C_{n}|}}\right)g(z)^{n}=\log {\frac {1}{1-g(z)}}.}$

この演算子は、集合演算子SETおよび特定の次数への制限とともに、ランダム順列統計を計算するために使用されます。この演算子には、偶数サイクルと奇数サイクルという 2 つの便利な制限があります。

ラベル付き偶数サイクル演算子 CYCeven_は

${\displaystyle C_{2}+C_{4}+C_{6}+\cdots }$

その結果

${\displaystyle G(z)=\sum _{n\geq 1}\left({\frac {1}{|C_{2n}|}}\right)g(z)^{2n}={\frac {1}{2}}\log {\frac {1}{1-g(z)^{2}}}.}$

これは、ラベル付き奇数サイクル演算子CYC _odd

${\displaystyle C_{1}+C_{3}+C_{5}+\cdots }$

は次のように与えられる。

${\displaystyle G(z)=\log {\frac {1}{1-g(z)}}-{\frac {1}{2}}\log {\frac {1}{1-g(z)^{2}}}={\frac {1}{2}}\log {\frac {1+g(z)}{1-g(z)}}.}$

このシリーズは

${\displaystyle 1+S_{1}+S_{2}+S_{3}+\cdots }$

つまり、対称群がスロットに適用されます。これにより、ラベルなしの場合は多重集合が作成され、ラベル付きの場合は集合が作成されます (ラベルは、異なるスロットに配置される集合から同じオブジェクトの複数のインスタンスを区別するため、ラベル付きの場合は多重集合は作成されません)。ラベル付きの場合とラベルなしの場合の両方に空集合を含めます。

ラベルなしの場合は関数を使って行う。

${\displaystyle M(f(z),y)=\sum _{n\geq 0}y^{n}Z(S_{n})(f(z),f(z^{2}),\ldots ,f(z^{n}))}$

となることによって

${\displaystyle {\mathfrak {M}}(f(z))=M(f(z),1).}$

評価 すると${\displaystyle M(f(z),1)}$

${\displaystyle F(z)=\exp \left(\sum _{\ell \geq 1}{\frac {f(z^{\ell })}{\ell }}\right).}$

ラベル付けされたケースでは、

${\displaystyle G(z)=1+\sum _{n\geq 1}\left({\frac {1}{|S_{n}|}}\right)g(z)^{n}=\sum _{n\geq 0}{\frac {g(z)^{n}}{n!}}=\exp g(z).}$

ラベル付きの場合、演算子はSETで表され、ラベルなしの場合、演算子はMSETで表されます。これは、ラベル付きの場合、多重集合が存在しない（ラベルは複合組み合わせクラスの構成要素を区別する）のに対し、ラベルなしの場合、多重集合と集合が存在し、後者は次のように表されるからです。

${\displaystyle F(z)=\exp \left(\sum _{\ell \geq 1}(-1)^{\ell -1}{\frac {f(z^{\ell })}{\ell }}\right).}$

通常、サイズ 0 の単一のオブジェクト (中立オブジェクト、 と表記されることが多い)を含む中立クラス と、サイズ 1 の単一のオブジェクトを含む1 つ以上の原子クラスから始めます。次に、互いに素な和、積、集合、シーケンス、多重集合などのさまざまな単純な演算を含む集合論的関係により、既に定義されているクラスに基づいて、より複雑なクラスを定義します。これらの関係は再帰的 である場合があります。記号的組合せ論の優れた点は、集合論的 (または記号的) 関係が、生成関数を含む 代数的関係に直接変換される点にあります。${\displaystyle {\mathcal {E}}}$${\displaystyle \epsilon }$ ${\displaystyle {\mathcal {Z}}}$

この記事では、組み合わせクラスを表すためにスクリプトの大文字を使用し、生成関数には対応する普通の文字を使用するという規則に従います (つまり、クラスには生成関数 があります)。 ${\displaystyle {\mathcal {A}}}$${\displaystyle A(z)}$

記号的組合せ論でよく使われる生成関数には 2 種類あります。ラベルなしオブジェクトの組合せクラスに使用される通常の生成関数と、ラベル付きオブジェクトのクラスに使用される 指数生成関数です。

および の生成関数（通常または指数）がそれぞれ、およびであることを示すのは簡単です。 互いに素な和集合も単純で、互いに素な集合およびの場合、が成り立ちます。 他の演算に対応する関係は、ラベル付き構造またはラベルなし構造（および通常の生成関数または指数生成関数）のどちらについて話しているのかによって異なります。 ${\displaystyle {\mathcal {E}}}$${\displaystyle {\mathcal {Z}}}$${\displaystyle E(z)=1}$${\displaystyle Z(z)=z}$${\displaystyle {\mathcal {B}}}$${\displaystyle {\mathcal {C}}}$${\displaystyle {\mathcal {A}}={\mathcal {B}}\cup {\mathcal {C}}}$${\displaystyle A(z)=B(z)+C(z)}$

和集合を互いに素な和集合に限定することは重要ですが、記号的組合せ論の正式な仕様では、どの集合が互いに素であるかを追跡するのは面倒すぎます。代わりに、交差がないことを保証する構成を使用します (ただし、これは演算の意味にも影響するので注意してください)。2つの集合との組合せ和を定義する際に、各集合のメンバーを個別のマーカーでマークします。たとえば、のメンバーについては、のメンバーについては です。この場合、組合せ和は次のようになります。 ${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {B}}}$${\displaystyle \circ }$${\displaystyle {\mathcal {A}}}$${\displaystyle \bullet }$${\displaystyle {\mathcal {B}}}$

${\displaystyle {\mathcal {A}}+{\mathcal {B}}=({\mathcal {A}}\times \{\circ \})\cup ({\mathcal {B}}\times \{\bullet \})}$

これは形式的には加算に対応する演算です。

ラベルのない構造では、通常の生成関数（OGF）が使用されます。シーケンスのOGFは次のように定義されます。 ${\displaystyle A_{n}}$

${\displaystyle A(x)=\sum _{n=0}^{\infty }A_{n}x^{n}}$

2つの組合せクラスと の積は、順序付きペアのサイズをペアの要素のサイズの合計として定義することによって指定されます。したがって、およびについては となります。これはかなり直感的な定義です。ここで、サイズnの の要素の数は ${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {B}}}$${\displaystyle a\in {\mathcal {A}}}$${\displaystyle b\in {\mathcal {B}}}$${\displaystyle |(a,b)|=|a|+|b|}$${\displaystyle {\mathcal {A}}\times {\mathcal {B}}}$

${\displaystyle \sum _{k=0}^{n}A_{k}B_{n-k}.}$

OGFの定義といくつかの初等代数を用いて、次のことを示すことができる。

${\displaystyle {\mathcal {A}}={\mathcal {B}}\times {\mathcal {C}}}$暗示する${\displaystyle A(z)=B(z)\cdot C(z).}$

で表されるシーケンス構築は次のように定義されます。 ${\displaystyle {\mathcal {A}}={\mathfrak {G}}\{{\mathcal {B}}\}}$

${\displaystyle {\mathfrak {G}}\{{\mathcal {B}}\}={\mathcal {E}}+{\mathcal {B}}+({\mathcal {B}}\times {\mathcal {B}})+({\mathcal {B}}\times {\mathcal {B}}\times {\mathcal {B}})+\cdots .}$

言い換えれば、シーケンスは中立要素、またはの要素、または順序付きペア、順序付きトリプルなどです。これは、関係 ${\displaystyle {\mathcal {B}}}$

${\displaystyle A(z)=1+B(z)+B(z)^{2}+B(z)^{3}+\cdots ={\frac {1}{1-B(z)}}.}$

で表される集合（または冪集合）構成は次のように定義 される。${\displaystyle {\mathcal {A}}={\mathfrak {P}}\{{\mathcal {B}}\}}$

${\displaystyle {\mathfrak {P}}\{{\mathcal {B}}\}=\prod _{\beta \in {\mathcal {B}}}({\mathcal {E}}+\{\beta \}),}$

これは関係につながる

${\displaystyle {\begin{aligned}A(z)&{}=\prod _{\beta \in {\mathcal {B}}}(1+z^{|\beta |})\\&{}=\prod _{n=1}^{\infty }(1+z^{n})^{B_{n}}\\&{}=\exp \left(\ln \prod _{n=1}^{\infty }(1+z^{n})^{B_{n}}\right)\\&{}=\exp \left(\sum _{n=1}^{\infty }B_{n}\ln(1+z^{n})\right)\\&{}=\exp \left(\sum _{n=1}^{\infty }B_{n}\cdot \sum _{k=1}^{\infty }{\frac {(-1)^{k-1}z^{nk}}{k}}\right)\\&{}=\exp \left(\sum _{k=1}^{\infty }{\frac {(-1)^{k-1}}{k}}\cdot \sum _{n=1}^{\infty }B_{n}z^{nk}\right)\\&{}=\exp \left(\sum _{k=1}^{\infty }{\frac {(-1)^{k-1}B(z^{k})}{k}}\right),\end{aligned}}}$

拡大が

${\displaystyle \ln(1+u)=\sum _{k=1}^{\infty }{\frac {(-1)^{k-1}u^{k}}{k}}}$

4 行目から 5 行目まで移動するために使用されました。

多重集合構成は、集合構成の一般化です。集合構成では、各要素は0回または1回出現します。多重集合では、各要素は任意の回数出現します。したがって、 ${\displaystyle {\mathcal {A}}={\mathfrak {M}}\{{\mathcal {B}}\}}$

${\displaystyle {\mathfrak {M}}\{{\mathcal {B}}\}=\prod _{\beta \in {\mathcal {B}}}{\mathfrak {G}}\{\beta \}.}$

これは次のような関係につながる。

${\displaystyle {\begin{aligned}A(z)&{}=\prod _{\beta \in {\mathcal {B}}}(1-z^{|\beta |})^{-1}\\&{}=\prod _{n=1}^{\infty }(1-z^{n})^{-B_{n}}\\&{}=\exp \left(\ln \prod _{n=1}^{\infty }(1-z^{n})^{-B_{n}}\right)\\&{}=\exp \left(\sum _{n=1}^{\infty }-B_{n}\ln(1-z^{n})\right)\\&{}=\exp \left(\sum _{k=1}^{\infty }{\frac {B(z^{k})}{k}}\right),\end{aligned}}}$

ここで、上記の集合構築と同様に、 を展開し、和を交換し、 の OGF を代入します。 ${\displaystyle \ln(1-z^{n})}$${\displaystyle {\mathcal {B}}}$

その他の重要な基本構造は次のとおりです。

• サイクル構造（）は、循環回転が別個とは見なされない点を除いてシーケンスに似ている。${\displaystyle {\mathfrak {C}}\{{\mathcal {B}}\}}$
• ポインタ（）では、Bの各メンバーに、その原子の1つを指す中立（サイズ0）ポインタが追加されます。${\displaystyle \Theta {\mathcal {B}}}$
• 置換（）では、Bのメンバーの各原子がCのメンバーに置き換えられます。${\displaystyle {\mathcal {B}}\circ {\mathcal {C}}}$

これらの構造の導出はここで示すには複雑すぎます。結果は次のとおりです。

これらの基本構成を使用して、多くの組み合わせクラスを構築できます。たとえば、平面木（つまり、平面に埋め込まれた木であり、部分木の順序が重要）のクラスは、再帰関係 によって指定されます。

${\displaystyle {\mathcal {G}}={\mathcal {Z}}\times \operatorname {SEQ} \{{\mathcal {G}}\}.}$

言い換えれば、木は長さ1のルートノードと一連の部分木から成ります。これは次のようになります。

${\displaystyle G(z)={\frac {z}{1-G(z)}}}$

G ( z )を求めるには、 ${\displaystyle 1-G(z)}$

${\displaystyle G(z)-G(z)^{2}=z}$

zを引いて二次方程式の公式を使ってG(z)を解くと、

${\displaystyle G(z)={\frac {1-{\sqrt {1-4z}}}{2}}.}$

もう 1 つの例 (古典的な組合せ論の問題) は、整数分割です。まず、各整数のサイズがその値である 正の整数のクラスを定義します。${\displaystyle {\mathcal {I}}}$

${\displaystyle {\mathcal {I}}={\mathcal {Z}}\times \operatorname {SEQ} \{{\mathcal {Z}}\}}$

のOGFは ${\displaystyle {\mathcal {I}}}$

${\displaystyle I(z)={\frac {z}{1-z}}.}$

ここで、パーティションのセットを次のように 定義します。${\displaystyle {\mathcal {P}}}$

${\displaystyle {\mathcal {P}}=\operatorname {MSET} \{{\mathcal {I}}\}.}$

OGFは ${\displaystyle {\mathcal {P}}}$

${\displaystyle P(z)=\exp \left(I(z)+{\frac {1}{2}}I(z^{2})+{\frac {1}{3}}I(z^{3})+\cdots \right).}$

残念ながら、 の閉じた形式は存在しません。しかし、OGF を使用して再帰関係を導出したり、解析的組合せ論のより高度な方法を使用して、計数列の漸近挙動を計算したりすることができます。 ${\displaystyle P(z)}$

上記の基本的な構成により、仕様の概念を定義することができます。この仕様により、複数の組み合わせクラスを持つ再帰方程式のセットを使用できます。

正式には、組み合わせクラスのセットの仕様は、方程式のセットです。ここで、は式であり、そのアトムは、およびであり、その演算子は、上記にリストされた基本構造です。 ${\displaystyle ({\mathcal {A}}_{1},\dots ,{\mathcal {A}}_{r})}$${\displaystyle r}$${\displaystyle {\mathcal {A}}_{i}=\Phi _{i}({\mathcal {A}}_{1},\dots ,{\mathcal {A}}_{r})}$${\displaystyle \Phi _{i}}$${\displaystyle {\mathcal {E}},{\mathcal {Z}}}$${\displaystyle {\mathcal {A}}_{i}}$

組み合わせ構造のクラスは、仕様を許容する場合、 構築可能または指定可能であると言われます。

たとえば、葉の深さが偶数（それぞれ奇数）である木の集合は、 と の 2 つのクラスを持つ仕様を使用して定義できます。これらのクラスは、方程式と を満たす必要があります。 ${\displaystyle {\mathcal {A}}_{\text{even}}}$${\displaystyle {\mathcal {A}}_{\text{odd}}}$${\displaystyle {\mathcal {A}}_{\text{odd}}={\mathcal {Z}}\times \operatorname {Seq} _{\geq 1}{\mathcal {A}}_{\text{even}}}$${\displaystyle {\mathcal {A}}_{\text{even}}={\mathcal {Z}}\times \operatorname {Seq} {\mathcal {A}}_{\text{odd}}}$

オブジェクトの各原子が非負の整数ラベルを持ち、これらのラベルがそれぞれ異なる場合、そのオブジェクトは弱くラベル付けされます。さらに、これらのラベルが連続する整数を構成する場合、オブジェクトは（強くまたは適切に）ラベル付けされます。 注: 一部の組み合わせクラスは、ラベル付き構造またはラベルなし構造として指定するのが最適ですが、両方の指定が容易に許可されるものもあります。ラベル付き構造の良い例は、ラベル付きグラフ のクラスです。 ${\displaystyle [1\ldots n]}$

ラベル付けされた構造では、指数生成関数（EGF）が使用される。配列のEGFは次のように定義される。 ${\displaystyle A_{n}}$

${\displaystyle A(x)=\sum _{n=0}^{\infty }A_{n}{\frac {x^{n}}{n!}}.}$

ラベル付き構造の場合、ラベルなし構造とは異なる積の定義を使用する必要があります。実際、単に直積を使用した場合、結果の構造は適切にラベル付けされません。代わりに、いわゆるラベル付き積を使用します。これは次のように表されます。${\displaystyle {\mathcal {A}}\star {\mathcal {B}}.}$

と のペアについて、2 つの構造を 1 つの構造に結合したいとします。結果を適切にラベル付けするには、および の原子に何らかの再ラベル付けが必要です。元のラベルの順序と一致する再ラベル付けに限定して注意します。再ラベル付けを行う方法は複数あることに注意してください。つまり、各メンバーのペアは、積の 1 つのメンバーを決定するのではなく、新しいメンバーのセットを決定します。この構築の詳細については、ラベル付き列挙定理のページを参照してください。 ${\displaystyle \beta \in {\mathcal {B}}}$${\displaystyle \gamma \in {\mathcal {C}}}$${\displaystyle \beta }$${\displaystyle \gamma }$

この発展を助けるために、関数 を定義しましょう。これは、引数として（おそらく弱く）ラベル付けされたオブジェクトを取り、順序一貫性のある方法でその原子を再ラベル付けして、 が適切にラベル付けされるようにします。次に、2つのオブジェクトとに対するラベル付き積を次のように 定義します。${\displaystyle \rho }$${\displaystyle \alpha }$${\displaystyle \rho (\alpha )}$${\displaystyle \alpha }$${\displaystyle \beta }$

${\displaystyle \alpha \star \beta =\{(\alpha ',\beta '):(\alpha ',\beta '){\text{ is well-labelled, }}\rho (\alpha ')=\alpha ,\rho (\beta ')=\beta \}.}$

最後に、2つのクラスとラベル付き積は ${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {B}}}$

${\displaystyle {\mathcal {A}}\star {\mathcal {B}}=\bigcup _{\alpha \in {\mathcal {A}},\beta \in {\mathcal {B}}}(\alpha \star \beta ).}$

EGFは、サイズが と のオブジェクトに対して、再ラベル付けを行う方法があることに注目することで導出できます。したがって、サイズが のオブジェクトの総数は ${\displaystyle k}$${\displaystyle n-k}$${\displaystyle {n \choose k}}$${\displaystyle n}$

${\displaystyle \sum _{k=0}^{n}{n \choose k}A_{k}B_{n-k}.}$

この項の 二項畳み込み関係は、EGFを掛け合わせることと同等である。

${\displaystyle A(z)\cdot B(z).}$

シーケンスの構築は 、ラベルなしの場合と同様に定義されます。 ${\displaystyle {\mathcal {A}}={\mathfrak {G}}\{{\mathcal {B}}\}}$

${\displaystyle {\mathfrak {G}}\{{\mathcal {B}}\}={\mathcal {E}}+{\mathcal {B}}+({\mathcal {B}}\star {\mathcal {B}})+({\mathcal {B}}\star {\mathcal {B}}\star {\mathcal {B}})+\cdots }$

そしてまた、上記と同様に、

${\displaystyle A(z)={\frac {1}{1-B(z)}}}$

ラベル付き構造では、要素の集合は正確にシーケンスに対応します。これは、いくつかの順列が一致する可能性があるラベルなしの場合とは異なります。したがって、 については、${\displaystyle k}$${\displaystyle k!}$${\displaystyle {\mathcal {A}}={\mathfrak {P}}\{{\mathcal {B}}\}}$

${\displaystyle A(z)=\sum _{k=0}^{\infty }{\frac {B(z)^{k}}{k!}}=\exp(B(z))}$

サイクルもラベルなしの場合より簡単です。長さ のサイクルは異なるシーケンスに対応します。したがって、 について は、${\displaystyle k}$${\displaystyle k}$${\displaystyle {\mathcal {A}}={\mathfrak {C}}\{{\mathcal {B}}\}}$

${\displaystyle A(z)=\sum _{k=0}^{\infty }{\frac {B(z)^{k}}{k}}=\ln \left({\frac {1}{1-B(z)}}\right).}$

ラベル付き構造では、最小ボックス積は、最小ラベルを持つ積の要素を必要とする元の積のバリエーションです。同様に、同じ方法で、 で表される最大ボックス積も定義できます。すると、${\displaystyle {\mathcal {A}}_{\min }={\mathcal {B}}^{\square }\star {\mathcal {C}}}$${\displaystyle {\mathcal {B}}}$${\displaystyle {\mathcal {A}}_{\max }={\mathcal {B}}^{\blacksquare }\star {\mathcal {C}}}$

${\displaystyle A_{\min }(z)=A_{\max }(z)=\int _{0}^{z}B'(t)C(t)\,dt.}$

または同等に、

${\displaystyle A_{\min }'(t)=A_{\max }'(t)=B'(t)C(t).}$

増加ケイリー木は、根から分岐する任意の枝に沿ったラベルが増加するシーケンスを形成する、ラベル付きの非平面根付き木です。次に、そのような木のクラスをとします。再帰仕様は、${\displaystyle {\mathcal {L}}}$${\displaystyle {\mathcal {L}}={\mathcal {Z}}^{\square }\star \operatorname {SET} ({\mathcal {L}}).}$

演算子 CYC _even、 CYC _odd、 SET _even、 および SET _{odd は} 、偶数と奇数の長さのサイクルと、偶数と奇数の基数のセットを表します。

第二種スターリング数は構造分解を用いて導出し、解析することができる。

${\displaystyle \operatorname {SET} (\operatorname {SET} _{\geq 1}({\mathcal {Z}})).}$

分解

${\displaystyle \operatorname {SET} (\operatorname {CYC} ({\mathcal {Z}}))}$

は、第一種符号なしスターリング数の研究や、ランダム順列の統計の導出に使用されます。記号的組合せ論におけるスターリング数に関連する指数生成関数の詳細な検討については、 「記号的組合せ論におけるスターリング数と指数生成関数」のページを参照してください。

• 組み合わせ種

• 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、Cambridge University Press (1998)。
• Philippe Flajolet および Robert Sedgewick、「Analytic Combinatorics」、Cambridge University Press (2009)。(オンラインで入手可能: http://algo.inria.fr/flajolet/Publications/book.pdf)
• ミカ・ホフリ、「アルゴリズムの分析：計算方法と数学ツール」、オックスフォード大学出版局（1995年）。