0
$\begingroup$

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$.

  • 1
    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?2012-07-24

1 Answers 1

2

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 . 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}$