2
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ something like $n.size\ \mbox{choose} \ topsorts(x)$ where $x$ is each child and multiply those? $\endgroup$ – SadStudent Jun 17 '13 at 17:56
  • $\begingroup$ 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. $\endgroup$ – Hendrik Jan Jun 17 '13 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.