CODEWITHSUNDEEP
algorithmtreegraph-coloring
newbie
newbie

Reputation: 247

How to calculate the ways to paint a tree?

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.

Upvotes: 6

Views: 925

Answers (1)

Dave
Dave

Reputation: 9085

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).

Upvotes: 3

Related Questions