Recursive tree

Definition

Recursive trees are non-planar labeled rooted trees. A size n tree recursive tree is labeled by distinct integers 1, 2,\dots, n, where the labels are strictly increasing starting at the root labeled 1. Since recursive trees are non-planar there is no left to right order. E.g. the following two size three recursive trees are the same.

       1          1   
      / \   =    / \           
     /   \      /   \
    2     3    3     2

Properties

Let T_n denote the number of size n recursive trees.

$T_{n}=(n-1)!$

There are bijective correspondances between recursive trees of size n and permutations of size n-1.

Applications

Recursive Trees are used as simple models for epidemics.