How to calculate the ways to paint a tree?

Question

How to calculate the ways to paint a tree's nodes with m colors so that the ends of each edge have different colors?

Any polynomial solution is welcome.

Lowborn

Yeah, I'm looking for number of ways. – Lowborn

Does it have to use all m colors? – Thelmathem

You don't need any algorithm, you just need to apply a O(1) formula (assuming you don't have to count nodes first): en.wikipedia.org/wiki/Chromatic_polynomial#Examples – Thelmathem

Answer 1

You have m choices for the root. If you paint going down from the root, you have m-1 choices for each additional node. If the number of nodes is n, then the number of ways to paint the tree is m * (m-1)^(n-1).

Zahn

what about n=1 and m=1 in your solution? – Styx

@dd2 put n=1 and m=1 in the given formula and you will get the correct answer as I mentioned in the comment to your answer. – Venereal

@dd2 0^0=1. It's a convention, and not one that's commonly taught. quora.com/What-is-0-0-the-zeroth-power-of-zero-1 – Zahn