1
$\begingroup$

We numberd nodes from $1$ to $N$ for convinent.

We firstly color node $1$. Then we will color $N - 1$ remaining nodes, in any order which satisfied condition:

node are chosen to color must be adjacent to one of nodes colored before. Two nodes are consider adjacent if there is a direct edge between them.

I found this statement explaining the solution:

Let $S[i]$ be the number of nodes in subtree rooted at node $i$. Let $F[i]$ be the number of ways coloring subtree rooted at node $i$, in which we always colored node $i$ first. The answer of this problem is $F[1]$.

And:

$$F_i = \binom{S[i]}{S[c_1]} \binom{S[i] - S[c_1]}{S[c_2]} \cdots \binom{S[i] - S[c_1] - S[c_2] - \cdots - S[c_{k - 1}]}{ S[c_k]} F[c_1] F[c_2] \cdots F[c_k]$$

Assuming that node $i$ have $k$ direct child: $c_1, c_2,\ldots , c_k$. The order of coloring nodes in each subtree rooted at node $c_j$ are independent to each other

I could not understand it , How we came to this formula , Please Explain me

$\endgroup$

1 Answer 1

1
$\begingroup$


Hi mosd. You want the number permutations $\sigma$ in $S_N$ such that for all $i$, there is and $j$ such that $\sigma _j$ is a parent of $\sigma _i$.
Now, suppose you have already calculate the orderings in the subtrees $S[c_1],S[c_2],\ldots S[c_k]$ which are denoted by $F[c_1],\ldots ,F[c_k]$. So in $\sigma$ you can color $\sigma _i$ in the color of the subtree it belongs(see picture below).
In other words, you must treat $\sigma _i$ to be equal to $\sigma _j$ iff nodes $i,j$ belong to the same subtree. So, by doing that you must consider using multinomial to look for every possible rearange of these $\underbrace{\color{blue}{* \cdots *}}_{S[c_1]}\underbrace{\color{green}{* \cdots *}}_{S[c_2]}\ldots \underbrace{\color{red}{* \cdots *}}_{S[c_{k-1}]}\underbrace{\color{yellow}{* \cdots *}}_{S[c_k]}$(1). That can be done in $\binom{N-1}{S[c_{1}],S[c_{2}],\ldots ,S[c_{k-1}],S[c_{k}]}=\binom{N-1}{S[c_{1}]}\binom{N-1-S[c_{1}]}{S[c_{2}]}\ldots \binom{N-1-(\sum _{i=1}^{k-1} S[c_{i}])}{S[c_{k}]}$ which is the multinomial number.
Now, as every subtree has it's own ordering, that you have pre calculated (DP i guess), and those orders are in fact $F[c_1],\ldots ,F[c_k]$ then, by the multiplication principle, you must multiply those numbers to the order on the colored permutation (1) to have all the ways you can have a permutation $\sigma$ with the characteristics proposed.

enter image description here

Hope it helps.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .