In Topcoder SRM 460, div2 1000, it asks for the number of labelled trees with a set of connected components. Each component is itself a tree of course. If each component is a single node, then Cayley's formula gives the result, |T_n| = n^(n-2). Now we have each component may be a tree, suppose there are k components with size c_1, c_2, ..., c_k, now what is the number of trees?
The formula is: n^(k-2)*c_1*c_2*...*c_k. But why?
http://en.wikipedia.org/wiki/Cayley%27s_formula
From this wiki page, the proof can be generalized to prove the above formula. Notice that if a component has c_i nodes, and it has degree d_i when collapsed as a single node in the tree, then there are actually c_i^d_i different trees derived from the tree with component C_i collapsed, because every node in C_i can be used to connect to the outside node for one degree. Now we have additional terms c_1^d_1 * c_2^d_2 * ... * c_k^d_k in the lemma, in addition to (k-2)! Now the multinomial formula that we are to use is to take x_1 = c_1, x_2=c_2, ... x_k = c_k, and
(c_1+c_2+...+c_k)^(k-2)
is what we are looking for.
An interesting alternative proof might be from the elegant Prüfer sequence,
but I am not sure how to extend this sequence to show the generalized formula.
