en>Yobot: /* References */clean up, checkwiki error #18 using AWB (8863)

2013-01-23T23:35:59Z

References: clean up, checkwiki error #18 using AWB (8863)

← Older revision		Revision as of 01:35, 24 January 2013
Line 1:		Line 1:
	~~Nice to meet you~~, ~~my title~~ is ~~Araceli Oquendo but I don~~'~~t like when people use my full title~~. ~~One~~ of the ~~issues I love most is greeting card gathering but I don't have~~ the ~~time lately~~. ~~Kansas~~ is ~~our birth place and my parents live close~~ by. ~~Interviewing is what she does but quickly she~~'~~ll be on her own.~~<br><br>~~Here~~ is ~~my blog~~ - ~~[http:~~/~~/Www~~.~~Myccos~~.~~com~~/~~UserProfile~~/~~tabid~~/61/~~userId/430/Default~~.~~aspx auto warranty~~]		In [[graph theory]], a discipline within mathematics, a '''recursive tree''' (i.e., unordered tree) is a non-planar labeled rooted [[tree (graph theory)\|tree]]. A size-''n'' recursive tree is labeled by distinct integers 1, 2, ..., ''n'', where the labels are strictly increasing starting at the root labeled 1. Recursive trees are non-planar, which means that the children of a particular node are not ordered. E.g. the following two size-three recursive trees are the same.
			<pre>
			1 1
			/ \ = / \
			/ \ / \
			2 3 3 2

			</pre>
			Recursive trees also appear in literature under the name Increasing Cayley trees.

			==Properties ==
			The number of size-''n'' recursive trees is given by

			:<math> T_n= (n-1)!. \,</math>

			Hence the exponential [[generating function]] ''T''(''z'') of the sequence ''T''<sub>''n''</sub> is given by

			:<math> T(z)= \sum_{n\ge 1} T_n \frac{z^n}{n!}=\log\left(\frac{1}{1-z}\right).</math>

			Combinatorically a recursive tree can be interpreted as a root followed by an unordered sequence of recursive trees. Let ''F'' denote the family of recursive trees.

			:<math> 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),</math>

			where <math>\circ</math> denotes the node labeled by 1, × the Cartesian product and <math>*</math> the partition product for labeled objects.

			By translation of the formal description one obtains the differential equation for ''T''(''z'')

			:<math> T'(z)= \exp(T(z)),</math>

			with ''T''(0) = 0.

			==Bijections==
			There are [[bijection\|bijective]] correspondences between recursive trees of size ''n'' and [[permutation]]s of size ''n'' − 1.

			==Applications ==
			Recursive trees can be generated using a simple stochastic process. Such random recursive trees are used as simple models for epidemics.

			==References==
			*''Analytic Combinatorics'', Philippe Flajolet and Robert Sedgewick, Cambridge University Press, 2008
			*''Varieties of Increasing Trees'', Francois Bergeron, Philippe Flajolet, and Bruno Salvy. In Proceedings of the 17th Colloquium on Trees in Algebra and Programming, Rennes, France, February 1992. Proceedings published in Lecture Notes in Computer Science vol. 581, J.-C. Raoult Ed., 1992, pp. 24–48.
			*''Profile of random trees: correlation and width of random recursive trees and binary search trees'' Michael Drmota and Hsien-Kuei Hwang, Adv. Appl. Prob., 37, 1-21, 2005.
			*''Profiles of random trees: Limit theorems for random recursive trees and binary search trees'', Michael Fuchs, Hsien-Kuei Hwang, Ralph Neininger., Algorithmica, 46:3-4, 2006, 367-407, 2006.

			[[Category:Trees (graph theory)]]

en>VladimirReshetnikov: /* See also */

2012-02-09T22:19:11Z

Admissible set - Revision history

en>Yobot: /* References */clean up, checkwiki error #18 using AWB (8863)

en>VladimirReshetnikov: /* See also */