increasing tree

An increasing binary tree is a tree with vertices that are labelled by numbers such that the label of a child is larger than that of a parent.

Properties

the number of such trees is $(n - 1)!$
- We may interpret this as the number of arborescences on the directed graph on $[n]$ where there is an edge $i \to j$ if $i < j$
- Then, its Laplacian (Kirchoff) matrix will have $0, 1, 2, \dots, n - 1$ on the main diagonal with $0$ below it and $- 1$ above it. Then, $L^{1 k} = (n - 1)!$ and by directed matrix tree theorem, this is the number of aborescences on this graph.