Editing Chromatic polynomial (section)

===Colorings using all colors===
For a graph ''G'' on ''n'' vertices, let <math>e_k</math> denote the number of colorings using exactly ''k'' colors ''up to renaming colors'' (so colorings that can be obtained from one another by permuting colors are counted as one; colorings obtained by [[Graph automorphism|automorphisms]] of ''G'' are still counted separately).
In other words, <math>e_k</math> counts the number of [[Partition of a set|partitions]] of the vertex set into ''k'' (non-empty) [[Independent set (graph theory)|independent sets]].
Then <math>k! \cdot e_k</math> counts the number of colorings using exactly ''k'' colors (with distinguishable colors).
For an integer ''x'', all ''x''-colorings of ''G'' can be uniquely obtained by choosing an integer ''k ≤ x'', choosing ''k'' colors to be used out of ''x'' available, and a coloring using exactly those ''k'' (distinguishable) colors.
Therefore:
: <math>P(G,x) = \sum_{k=0}^x \binom{x}{k} k! \cdot e_k = \sum_{k=0}^x (x)_k \cdot e_k,</math>
where <math>(x)_k = x(x-1)(x-2)\cdots(x-k+1)</math> denotes the [[falling factorial]].
Thus the numbers <math>e_k</math> are the coefficients of the polynomial <math>P(G,x)</math> in the basis <math>1,(x)_1,(x)_2,(x)_3,\ldots</math> of falling factorials.

Let <math>a_k</math> be the ''k''-th coefficient of <math>P(G,x)</math> in the standard basis <math>1,x,x^2,x^3,\ldots</math>, that is:
: <math>P(G,x) = \sum_{k=0}^n a_k x^k</math>
[[Stirling number]]s give a [[Stirling number#As change of basis coefficients|change of basis]] between the standard basis and the basis of falling factorials.
This implies:
:<math>a_k = \sum_{j=0}^n (-1)^{j-k} \begin{bmatrix}j\\k\end{bmatrix} e_j</math> &nbsp; and &nbsp; <math>e_k = \sum_{j=0}^n \begin{Bmatrix}j\\k\end{Bmatrix} a_j. </math>