재귀 트리

그래프 이론에서, 재귀 트리(즉, 순서 없는 트리)는 라벨이 붙은 루트 트리입니다.크기 n의 재귀 트리의 정점은 각각 다른 양의 정수 1, 2, …, n으로 라벨이 지정되며, 라벨은 1로 표시된 루트부터 엄밀하게 증가합니다.재귀 트리는 비재귀 트리이며, 이는 특정 정점의 자식들이 정렬되지 않음을 의미합니다. 예를 들어,¹₂ /\ = /\¹₃ 두 개의 size-3 재귀 트리는 동일합니다.

재귀 트리는 문헌에서 증가 중인 케일리 트리라는 이름으로도 나타납니다.

특성.

size-n 재귀 트리의 수는 다음과 같습니다.

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

따라서 시퀀스_n T의 지수 생성 함수 T(z)는 다음과 같이 주어진다.

${\displaystyle T(z)=\sum _{n\geq 1)T_{n}{\frac {z^{n}}{n!}=\log \leftflac {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 \times F*F*\cdots =\times \exp(F),}$

여기서 ${\$ { $displaystyle \circ }$는 1, × 데카르트 제품 및$$by { $display$ style *$$}으로$$ 라벨이 지정된 오브젝트의 파티션 제품으로 라벨이 지정된 노드를 나타냅니다.

형식 설명을 번역하면 T(z)에 대한 미분 방정식을 얻을 수 있다.

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

T(0) = 0인 경우.

분사션

크기가 n인 재귀적 나무와 크기가 n - 1인 순열 사이에는 비사적 대응 관계가 있습니다.

적용들

재귀 트리는 단순한 확률 프로세스를 사용하여 생성할 수 있습니다.이러한 랜덤 재귀 트리는 전염병의 단순한 모델로 사용됩니다.

레퍼런스

• Analytic Combinatorics, Philippe Flajolet and Robert Sedgewick, Cambridge University Press, 2008년
• 증가하는 나무의 다양성, 프랑수아 베르제롱, 필리프 플라졸레, 브루노 살비.프랑스 렌, 1992년 2월, 제17회 대수학 및 프로그래밍 나무 토론회 회견에서.의사록은 컴퓨터 사이언스 제581, J.-C.강연주석에 게재되어 있다.Raoult Ed, 1992, 페이지 24-48.
• 랜덤 트리 프로파일: 랜덤 재귀 트리 및 바이너리 검색 트리 Michael Drmota와 Hsien-Kuei Hang, Adv. Appl.문제 37, 1-21, 2005년
• 랜덤 트리 프로파일: 랜덤 재귀 트리 및 바이너리 검색 트리, Michael Fuchs, Hsien-Kuei Hang, Ralph Neininger, Algorithmica, 46:3-4, 2006, 367-407, 2006의 정리 제한.