[Solved]: Find the number of topological sorts in a tree

Problem Detail: 

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 :)

Asked By : SadStudent

Answered By : Hendrik Jan

A clue then.

It seems you have to multiply with a multinomial coefficient in each step. Here the size of the subtree comes in handy.

Explanation: if children have certain topsorts, then these sequences may be shuffled in the topsort for the parent. We 'color' the positions where the various topsorts for the respective children are placed, and at each color we write one of the possible topsorts for that child.

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) $$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12713