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

  • 0
    I corrected the description. I made silly mistakes because I was in a hurry.2012-07-24
  • 0
    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.2012-07-24
  • 0
    That's not the case; thank you for pointing out.2012-07-24
  • 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

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