Let's first try to solve this problem by ~O(N^2 * log(N))~.

Instead of iterating for every combination, I'll count how many ways to renumber the tree that has label ~i~ at position ~p~ on the tree, that has an increasing sequence from the root to that position.

The result is ~C(i - 1, h(p) - 1) * (n - h(p))!~, and ~h(p)~ is the height of position ~p~ on the tree, with ~h(1) = 1~. If we precalc ~x!~ for ~x~ not greater than ~n~, each ~C()~ will be calculated in ~O(logN)~.

For each index ~i~, we can group positions with the same level ~x~, which will simplify the expression to sigma of ~C(i - 1, x - 1) * count(x)~, for ~x~ runs from ~1~ to ~N~.

Now, we regroup by height. For each height ~x~, we get ~count(x) * (sigma of C(x - 1, i - 1)~, for ~i~ from ~1~ to ~N~). (~C(j, i) = 0~ if i > j).

To reduce the complexity by ~N~, we have to see that Sigma of ~C(i - 1, x - 1)~, for ~i~ from ~1~ to ~N~ can actually be simplified to ~C(N, x)~.

Complexity ~O(N * log(N))~.