# Number of leaves in a tree that represents a kind of permutations

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

1. if $s(v)$ has a decreasing subsequence, $v$ is a leaf, and
2. 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$.

-
I corrected the description. I made silly mistakes because I was in a hurry. – Pteromys Jul 24 '12 at 12:56
Every sequence contains as many decreasing subsequences as it has terms, since each term by itself forms a decreasing subsequence, as does the empty subsequence. If that's not the case under your definition of a decreasing subsequence, you should provide that definition. – joriki Jul 24 '12 at 13:24
That's not the case; thank you for pointing out. – Pteromys Jul 24 '12 at 13:32
An alternative way to ask the same question: (a) start with all lists that are permutations of $\{1,\ldots,n\}$. (b) cut off each list after the first number that is not the largest so far, (c) how many different lists remain? – Henning Makholm Jul 24 '12 at 14:00

For $n\ge 2$, the sequences $s(v)$ for leaves $v$ are exactly the list $(1,2,3,\ldots,n)$ plus those sequences of length $\ge 2$ without repetition where every number except the last one is greater than its predecessor. Once any number that is smaller than its predecessor gets added, the last two numbers in the list is a decreasing subsequence and makes the node a leaf.
(I'm assuming that you consider the bottommost $n$ node to be a leaf, rather than merely an internal node with $0$ descendants. Otherwise ignore the $+1$ in the following).
Let's count the number of qualifying sequences of length $k$, $2\le k <n$. We select $k$ numbers among $\{1,\ldots,n\}$ to be in the sequence, which can be done in $\binom nk$ ways. For each choice of members, all but the largest one can come at the end of the sequence, but the other ones must appear in increasing order. So there are $(k-1)\binom nk$ lists of length $k$. For $k=n$ we can use the same expression if we remember to add $1$ to account for the list $(1,2,\ldots,n)$.
So the total number of leaves is $$1 + \sum_{k=1}^n (k-1)\binom nk$$ where the $k=1$ termvanishes due to the $k-1$ factor but makes the formula look slightly nicer.
Using some well-known binomial identities we can rewrite this as $$2 + \sum_{k=0}^n (k-1)\binom nk = 2 + \sum_{k=0}^n k\binom nk - \sum_{k=0}^n \binom nk = 2 + n2^{n-1} - 2^n = 2 + (n-2)2^{n-1}$$