Consider the following rooted tree, each of whose vertices (except for the root) is labeled with an integer $\in\{1,\dots,n\}$: let $s(v)$ be the sequence consists of the labels on the path from the root to a vertex $v$ (including the label of $v$), and
- if $s(v)$ has a decreasing subsequence, $v$ is a leaf, and
- otherwise, $v$ has $n-|s(v)|$ children, labeled with positive integers not belonging to $s(v)$, where $|s(v)|$ is the length of $s(v)$.
The question is how many leaves this tree has.
Background: I'm analysing the sorting algorithm that examines paths from the root to every leaf.
Addendum: Sequences of length less than 2 are not decreasing.
Addendum 2: Let $r$ be the root, then $s(r)$ is the empty sequence $()$, so $r$ has $n - |s(r)|=n$ children labeled with $1,\dots,n$.