喜びの全単射について詳しく解説

導入

Joyal の全単射は、Foata の基本的な対応を使用した「展開」、つまり、

でケイリーツリーを作ります。 Joyal の全単射によって、Arthur Cayley による公式のエレガントなデモンストレーションが可能になります。これによると、 n個の頂点でラベル付けされた木の数( Cayley 木とも呼ばれます) は次のようになります。

n ^{( n −2)} 。

Joyal 全単射は、n 個の頂点を持つラベル付きツリーの計量プロパティを研究するのにも非常に役立ちます。

アプリケーション: Cayley の公式のデモンストレーション

注意しましょう

n個の頂点を持つ Cayley 木のセット。基数を計算するにはデモンストレーションの 1 つは、 と一連のアプリケーションの間にJoyal 全単射と呼ばれる全単射を確立することで構成されます。 で 、通常注目される 。したがって、私たちは

$$ {n^n\ =\ \text{Card}\ [\![1,n]\!]^{[\![1,n]\!]}\ =\ \text{Card}\ \left(\mathcal{C}_n\times[\![1,n]\!]^2\right)\ =\ n^2\,\text{Card}\ \mathcal{C}_n.} $$

このデモンストレーションは、アイグナーとジーグラー、さらにはピットマンによってアンドレ・ジョヤルによるものであると考えられています。

n個の頂点を持つケイリー ツリーのセットとして見ることができ、そのうちの 2 つの頂点には 2 つの異なるマークが付いています。最初のマークが付いた頂点は、ツリーのルートとして解釈できます。 2つの異なるブランドを同じサミットで着用できます。

Joyal 全単射を使用すると、ランダムな木の 2 つのランダムな頂点間の距離を調べることで、サイズnの木のトポロジーをより深く理解できるようになります。実際、等確率でランダムに抽出された要素は、

は、ランダムに描画された 2 つのマークされた点を持つケイリー木です。ランダムに描画された 2 つのマークされた点を持つケイリー木に関するさまざまな統計の法則を計算することは、宇宙のさまざまな部分の基数を計算することになります。 このためには、 Joyal 全単射によってこれらの部分のイメージの基数を計算する方が簡単です。

周期的要素と過渡的要素

fの定義セットでは、周期的(または反復的) 要素を一時的要素から区別できます。青色で反対側に示されている周期的要素は、次のようなn _x > 0が存在する要素xです。

$$ {f^{n_x}(x)=x.} $$

たとえば、逆に、 n ₁₂ = 1 、 n ₁₆ = 2 、およびn ₈ = 6 です。各アプリケーションでƒの

で遷移確率が次のように定義されるマルコフ連鎖を関連付けることができます。

$$ {p_{i,f(i)}=1,\qquad \forall i\in[\![1,n]\!].} $$

したがって、 fの繰り返し要素と一時的要素は、まさにこのマルコフ連鎖の繰り返し要素と一時的要素になります。

アプリケーションのグラフィック表現

Joyal の全単射を説明するには、次の各マップƒの表現を使用すると便利です。

で頂点のセットが次のような有向グラフを使用します。 そしてエッジは各要素をその画像にƒで接続します。たとえば、 f = (12, 15, 2, 13, 10, 10, 13, 9, 19, 17, 18, 12, 15, 16, 20, 14, 2, 2, 13, 8) の場合、つまり、 ƒ(1) = 12 、 ƒ(2) = 15 、 ƒ(3) = 2 、 … の場合、反対のグラフィック表現が得られます。

ジョヤルの独断

fの循環要素間のエッジが消去されると、こうして変更されたƒの表現はフォレスト(循環のないグラフ、おそらく接続されておらず、接続されているコンポーネントが正確にツリーであるグラフ) になることが観察されます。フォレストの各ツリーは、 ƒの循環要素の 1 つに根ざしていると見なされます。 Foata対応によって生成されたCのすべての要素の配置に関連付けられた線形グラフの対応する頂点にこれらのツリーのそれぞれを「再植」することにより、2 つのマークされた頂点を持つ Cayley ツリーが得られます。

逆に、2 つの点xとy がマークされ、おそらく等しい、一方が「開始」、もう一方が「終了」とマークされたケイリー木Tのデータは、次のように定義されます。

• Tの各エッジの方向(たとえば、 Tの各エッジは、端 ( y ) から最も遠い頂点からyに最も近い頂点に向かって方向付けられます)。
• xからyまでの最小長の単一パス (ツリーは接続されたグラフであるためパスが存在し、ツリーはサイクルのないグラフであるため単一の最小パスが存在します)。
• 順序付けられた一連の数字
  $$ {\scriptstyle\ [\![1,n]\!], \ } $$
  ωで示されます: このパスがxからyに移動するときに、 xとy の間の最小長のパス上に現れる頂点ラベルのシーケンス。したがって、シーケンスωは頂点ラベルxで始まり、頂点ラベルyで終わります。シーケンスωの長さは厳密にn未満になる可能性があります。

このシーケンスωに Foata 対応を適用して、 ωを構成する数値の順列τ 、つまりグラフがサイクルの集合である順列を見つけることができます。これらのサイクルは、シーケンスω を逆にすることによって得られるシーケンスの下向きのレコード、つまりyからxへのパスをトラバースすることによって観察されるレコードによって区切られます。

反対の例では、 x = 9およびy = 14で、最小パスはω = (9, 19, 13, 15, 20, 8, 12, 16, 14)です。反転シーケンス(14、16、12、8、20、15、13、19、9)のレコードは連続して14 、 12 、および8となり、 τが素サイクルに分解されます。

$$ {\tau\ =\ (9, 19, 13, 15, 20, 8) (12) (16,14).} $$

したがって、 fのサイクルを見つけます。

xとy の間の最小長のパスを構成するエッジが消去されると、このように変更された Cayley T木はフォレストになり、フォレスト内の各木はxとy の間のパスの頂点の 1 つに根を下ろしているように見えます。これらのツリーのそれぞれをτのグラフの対応する頂点に「再植」することにより、 fのグラフが得られます。

たとえば、 xとyの役割を交換すると、次の新しい要素が得られます。

Joyal 全単射によってその逆画像g を調べてみましょう。y からxへのパス上に現れる頂点のラベルのセットは同じままですが、得られたシーケンスη は、以前に観察されたシーケンスωの逆シーケンスです。 ηの反転シーケンス (つまり、シーケンスω ) の下向きレコードは 9、次に 8 となり、循環式のサイクル(14, 16, 12, 8) (20, 15, 13, 19, 9)への分解につながります。 gの部分。次に、予想通り、マップg = (12, 15, 2, 13, 10, 10, 13, 14, 20, 17, 18, 8, 19, 16, 13, 12, 2, 2, 9, 15)最初に持っていたアプリケーションƒとは異なります(上記を参照)。