Число раскрашенных деревьев

[nandreao]

Есть две похожие задачи по теории графов.
Пусть q(n,m) - количество корневых деревьев с n раскрашенными с помощью m красок вершинами.
1. Доказать, что q(4,m) = $4m+44C_{m}^2+64C_{m}^4$
2. Если не существует двух смежных вершин одинаковой раскраски, то
q(4,m) = $8C_{m}^2+54C_{m}^3+64C_{m}^4$
Не могу понять, как подступиться.