I am currently making a research project on ILP based optimal unpacking of CHs and can not figure out a specific question. To compare my approach, I would like to know the total amount of possible unpacks.
Long story short:
The CH can be presented as a binary tree containing n internal nodes. The tree is not balanced, however a node has either two or zero children. I want to figure out how many orderings of internal nodes exist such that each internal node comes before its children.
Of course, I know that the number of potential paths along a binary tree with $n$ nodes lies within $\mathcal{O}(2^n)$. Yes, this number can be more precised since with $n$ nodes you won't have a full balanced tree of depth $n$, but thats not part of the question. The problem i have is that a single path only regards the structure along this single path, however all the other remaining nodes that are not on the path still have an ordering too. Since each node not taken along the path has its on subtree, those also have impact on the number of total orderings and i can't figure out how to compute that. It kind of sounds like an easy recursive question since each node not taken is an own subtree but i am not sure if i can simply compute it like that.
Therefore i would appreaciate any help.
As a starting point, let's represent the binary tree as a root node with two subtrees $A$ and $B$. Let $a$ be the total number of nodes in $A$ and let $b$ be the total number of nodes in $B$, with $a + b = 2n$ (because our binary tree with $n$ internal nodes has $2n+1$ total nodes, one of which is the root).
Then every ordering of the tree must begin with the root, and then somehow interleave an ordering of $A$ with an ordering of $B$. There are $\binom{2n}{a} = \frac{(2n)!}{a!\,b!}$ ways to interleave the orderings: we must simply choose which $a$ of the $2n$ following positions contain a node of $A$. We must also multiply this number by the number of ways to order $A$ and the number of ways to order $B$, which gives us a recursive calculation to do.
We can simplify this, however. The number of ways to order $A$ will be equal to $\frac{(a-1)!}{c!\,d!}$ for some $c$ and $d$ adding up to $a-1$. We can cancel this $(a-1)!$ in the numerator with the $a!$ we had in the denominator earlier, simplifying our calculation. In fact, every time there is an internal node, other than the root, whose subtree has $k$ nodes total, we will divide by $k!$ and then later multiply by $(k-1)!$: the net effect is to divide by $k$.
It's not elegant to say "every internal node other than the root". To include the root as part of the general pattern, let's rewrite our initial factor of $(2n)!$ as $\frac{(2n+1)!}{2n+1}$. Now we start with a factor of $(2n+1)!$ and divide by the total number of nodes in every subtree. In other words, the formula is $$\frac{(2n+1)!}{\displaystyle \prod_{k=1}^n t_k}$$ where $t_1, t_2, \dots, t_n$ are the total number of nodes (counting both leaf nodes and internal nodes) in the subtrees at the $n$ internal nodes.
Let's do an example. Here is a binary tree, where I've labeled each internal node with the number of nodes in its subtree:
The formula says that the number of orderings of this binary tree is $$\frac{13!}{13 \cdot 3 \cdot 9 \cdot 3 \cdot 5 \cdot 3}.$$
This calculation has a probabilistic interpretation. The $13!$ (and in general, the $(2n+1)!$) is the total number of orderings of the nodes. The fractions $\frac1{13}, \frac13, \frac19, \frac13, \frac15, \frac13$ (and in general, $\frac1{t_1}, \dots, \frac1{t_n}$) are the probabilities that each internal node ends up the first in its subtree, in a random ordering. For our formula to work, it must be the case that these events are independent (so that we can just multiply these probabilities together). From some points of view, this may be intuitively clear; if not, the preceding answer can serve as a formal proof.