# Find the number of topological sorts in a tree

Find the number of topological sorts in a tree that has nodes that hold the size of their sub-tree including itself.

I've tried thinking what would be the best for m to define it but couldn't get anything specific.

Maybe $\mbox{Number of sorts =}\prod\limits_{x\in \mbox{children}}\mbox{Number of sorts}(x)$ Meaning that starting at the root I call the the method recursively multilying each result by the previous children's result. When we reach a node with size 1 we assume that there's just 1 topological sort;

If this is correct I'd really appreciate some help with proving correctness and if not a explanation why and a clue could be nice :)

Since the formula is used now in another problem, here it is explicitly. Assume the tree $t$ has $n+1$ nodes, and the subtrees $t_1, \dots, t_r$ of the children have $k_1, \dots, k_r$ nodes respectively (so $n=k_1+\dots+k_r$). Let $\operatorname{NoS}(t)$ be the number of topsorts of tree $t$. Then
$$\operatorname{NoS}(t) = {n \choose k_1, k_2, \dots, k_r}\prod_{i=1}^n \operatorname{NoS}(t_i)$$
• something like $n.size\ \mbox{choose} \ topsorts(x)$ where $x$ is each child and multiply those? – SadStudent Jun 17 '13 at 17:56
• Almost, I mean $n \choose {k_1, k_2, \dots, k_r}$ where $n =k_1+\dots+k_r$ is the total size, and $k_i$ the size of the $i$'th subtree. This means you choose the $k_i$ positions of the topsort of the $i$'th subtree among the available positions. – Hendrik Jan Jun 17 '13 at 19:59