再帰木

グラフ理論において、再帰木（順序なし木）は、ラベル付きの根付き木です。サイズn の再帰木の頂点には、異なる正の整数 1、2、…、nがラベル付けされ、ラベルは、ラベル 1 の根から厳密に増加します。再帰木は非平面的であり、つまり、特定の頂点の子は順序付けられていません。たとえば、次の 2 つのサイズ 3 の再帰木は同等です: ₃ / ¹ \ ₂ = ₂ / ¹ \ ₃。

再帰ツリーは、増加ケイリーツリーという名前で文献にも登場します。

プロパティ

サイズnの再帰木 の数は次のように与えられる。

${\displaystyle T_{n}=(n-1)!.\,}$

したがって、数列T _nの指数生成関数 T ( z )は次のように与えられる。

${\displaystyle T(z)=\sum _{n\geq 1}T_{n}{\frac {z^{n}}{n!}}=\log \left({\frac {1}{1-z}}\right).}$

組み合わせ論的に、再帰木は根に続く順序のない再帰木の列として解釈できる。再帰木の族を Fとする。すると、

${\displaystyle F=\circ +{\frac {1}{1!}}\cdot \circ \times F+{\frac {1}{2!}}\cdot \circ \times F*F+{\frac {1}{3!}}\cdot \circ \times F*F*F*\cdots =\circ \times \exp(F),}$

ここで、1 でラベル付けされたノード、×ラベル付けされたオブジェクトの直積と分割積を表します。 ${\displaystyle \circ}$ ${\displaystyle *}$

形式的記述を翻訳すると、T ( z ) の微分方程式が得られる。

${\displaystyle T'(z)=\exp(T(z)),}$

T (0) = 0 となる。

一対一投射

サイズnの再帰木とサイズn  − 1 の順列の間には全単射的な対応関係があります。

アプリケーション

再帰木は単純な確率過程を用いて生成できます。このようなランダムな再帰木は、疫病の単純なモデルとして用いられます。

参考文献

• 解析的組合せ論、フィリップ・フラジョレとロバート・セジウィック、ケンブリッジ大学出版局、2008年。
• 増加木の変種、フランソワ・ベルジェロン、フィリップ・フラジョレ、ブルーノ・サルヴィ。第17回代数とプログラミングにおける木に関するコロキウムの議事録、フランス、レンヌ、1992年2月。議事録はLecture Notes in Computer Science vol. 581、J.-C. Raoult編、1992年、24～48ページに掲載。
• ランダムツリーのプロファイル：ランダム再帰ツリーとバイナリ検索ツリーの相関と幅、Michael Drmota と Hsien-Kuei Hwang、Adv. Appl. Prob.、37、1–21、2005 年。
• ランダムツリーのプロファイル：ランダム再帰ツリーとバイナリ検索ツリーの極限定理、Michael Fuchs、Hsien-Kuei Hwang、Ralph Neininger。、Algorithmica、46、367–407、2006年。