Combinatorics – Understanding OEIS A139383

combinatoricsgraph theoryoeis

Because it resembles another thing that I am counting, I would like to understand the OEIS sequence A139383, "Number of $n$-level labeled rooted trees with $n$ leaves".

I think I understand what the level is, it should be the depth plus one, i.e. the number of edges between root and another node plus one.

However I don't understand if here $n$-level should apply to all the $n$ leaves.

I have tried the cases $n=2$ and $n=3$ but I can't get the $2$ and respectively $12$ trees. Anyone could help me with these cases?

Best Answer

This appears to be counting the number of rooted trees of depth $n$ with $n$ leaves, where all the leaves are at distance $n$ from the root, and the leaves (but not the other vertices) are labeled.

For example, here are the $12$ trees counted in the $n=3$ case:

  *       *         *         *
  |       |         |         |
  *       *         *         *
  |      / \       / \       / \
  *     *   *     *   *     *   *
 /|\    |  / \    |  / \    |  / \
1 2 3   1 2   3   2 1   3   3 1   2

  *       *         *         *
  |      / \       / \       / \
  *     *   *     *   *     *   *
 /|\    |   |     |   |     |   |
* * *   *   *     *   *     *   *
| | |   |  / \    |  / \    |  / \
1 2 3   1 2   3   2 1   3   3 1   2

  *       *         *         *
 /|\     / \       / \       / \
* * *   *   *     *   *     *   *
| | |   |  / \    |  / \    |  / \
* * *   * *   *   * *   *   * *   *
| | |   | |   |   | |   |   | |   |
1 2 3   1 2   3   2 1   3   3 1   2

We can also represent these by nested sets of sets of sets (again to a depth of $n$) where at the bottom level are the elements $1, 2, \dots, n$. For example, the $12$ trees above correspond to

\begin{array}{cccc} \{\{\{1,2,3\}\}\} & \{\{\{1\},\{2,3\}\}\} & \{\{\{2\},\{1,3\}\}\} & \{\{\{3\},\{1,2\}\}\} \\ \{\{\{1\},\{2\},\{3\}\}\} & \{\{\{1\}\}, \{\{2,3\}\}\} & \{\{\{2\}\}, \{\{1,3\}\}\} & \{\{\{3\}\}, \{\{1,2\}\}\} \\ \{\{\{1\}\},\{\{2\}\},\{\{3\}\}\} & \{\{\{1\}\},\{\{2\},\{3\}\}\} & \{\{\{2\}\},\{\{1\},\{3\}\}\} & \{\{\{3\}\},\{\{1\},\{2\}\}\} \end{array}

If you scroll down to the "examples" section of the OEIS entry, then instead of examples, you will see a 2D table of OEIS sequences where the diagonal is A139383. In that table of OEIS sequences, the $k^{\text{th}}$ row counts the number of rooted trees of depth $k$ with $n$ leaves, where again all the leaves are at maximum depth from the root, and the leaves, but not the other vertices, are labeled.

For example, the second row gives us the Bell numbers. That's because if our tree has depth $2$, then it is completely described by listing the partition of the $n$ leaves into the sets of leaves with a common parent, and the Bell numbers exactly count such partitions.

Here is some Mathematica code for generating all such partitions.

Needs["Combinatorica`"]
a139383[n_] := Nest[Flatten[SetPartitions /@ #, 1] &, {Range[n]}, n - 1]

If we want to compute the values in the sequence, this is not the most efficient approach, compared to the Stirling number recursion on OEIS. (I am not patient enough for $n=7$.) However, this also shows us what the sequence is counting!

Compare this to A261280, which is described on OEIS entirely in the language of partitions. Actually, the definitions of A261280 and A139383 are almost identical, except A261280 counts trees of depth $n+1$ with $n$ leaves (under all the same restrictions). If you look at the 2D table in the "examples" section of A139383 that I mentioned, then the diagonal below the main diagonal is exactly A261280.

Symmetrically, if you look at the square table given by A144150, then its main diagonal is A261280, and the diagonal below the main diagonal is A139383.

Related Question