Графы. Раскрашивание деревьев

[CYHDYK]

Каждая вершина дерева независимо от остальных окрашивается в один из $m$ цветов. Пусть $q(n,m)$ количество раскрашенных корневых деревьев с $n$ вершинами. Доказать, что $q(4,m)=4m+44C^2_m+64C^4_m$.

Вообще не понятно, что за ерунда, а что, если у нас $m<4$?
И почему нельзя рассуждать так: всего у нас $m^4$ способов раскрасить 4 вершины разными цветами. Также имеем $n^{n-2}$ различных деревьев, следовательно, результат - перемножение: $m^4 n^{n-2}$.

[Xaositect]

Если $m>n$, то $C_n^m = 0$.
Деревья неупорядоченные, т.е. если из вершины выходит несколько веток, мы можем их переставлять, и такое дерево считается 1 раз.

[zhoraster]

Возвращено из "Карантина".