Counting trees (order matters)

Question

As a follow up to this question (the number of rooted binary trees of size n), how many possible binary trees can you have if the nodes are now labeled, so that abc is different than bac cab etc ? In other words, order matters. Certainly it will be much more than the Catalan number.

What would the problem be if you have n-ary trees instead of binary ?

Are these known problems? reference ?

Answer 1

As partially answered above by Syzygy, for labelled binary trees, it is $n!C_n$, where $C_n$ being the Catalan number. Generalized this to labelled $k$-ary trees, it is $n!C^k_n$ where $C^k_n$ is the Fuzz-Catalan number $ \begin{equation} C^k_n= \binom{kn}{n}\frac{1}{(k-1)n+1} \end{equation} $

Answer 2

I am not sure, if I understood the question correctly, but are you asking for the number of rooted binary trees of size $n$, with nodes labeled from $1,...,n$, where isomorphic trees with different labelings are counted as different?

If so, isn't your labeling just adding $n!$ different possible labelings for each class of isomorphic trees? I.e. your total number of trees would be $n!C_n$, where $C_n$ is the $n$-th Catalan number.