# Number of k-colorings as a fraction of all possible ways to color a graph

I have a graph with $n$ verices, and I want to compute the number of ways to color the graph (with no adjacent vertices having the same color) using anywhere between $1$ and $n$ colors. This number (including permutations of colors) should be given by the chromatic polynomial for the graph.

However, I would like to present this number as a fraction of all possible ways to color the graph (without a restriction on not coloring adjacent vertices with the same color). The number of unique ways to do this for any $k<=n$ is $k$ multichoose $n$, or $(k+n-1)$ choose $n$.

The issue then is that the chromatic polynomial counts color permutations, whereas the multiset does not.

How do we place these on equivalent terms? In other words, how to we exclude color permutations from the chromatic polynomial or incorporate color permutations into the multichoose number?

The number of ways to color the vertices of a labelled graph on $n$ vertices if there are $k$ colors available is $k^n$. Thus if the graph has chromatic polynomial $f$ then the probability a random coloration where there are $k$ colors available is $\dfrac{f(k)}{k^n}$
• Yes, of course, thank you @Bananarama! Is there a way to account for graph symmetry - in other words, some of the $k^n$ possibilities will be identical under the graph symmetry (for example, octahedral symmetry)? – user156167 Jun 9 '14 at 21:04