Stanley's Formula for Counting Acyclic Orientations

From a Polynomial Evaluation to an Orientation Count

A chromatic polynomial is usually used to count proper colorings when the number of available colors is a positive integer. Stanley’s identity gives it another role: its value at \(-1\), after a sign correction determined by the number of vertices, counts the acyclic orientations of the graph. The evaluation at \(-1\) is algebraic; it does not mean that a graph is being colored with a negative number of colors.

Throughout, graphs are finite and simple. An orientation of an undirected graph \(G=(V,E)\) assigns exactly one direction to each edge: an edge \(uv\) becomes either \(u\to v\) or \(v\to u\), but not both. A directed cycle is a cycle whose edges all point consistently around it. An orientation is acyclic if it contains no directed cycle. Write \(a(G)\) for the number of acyclic orientations of \(G\), and let \(n=|V(G)|\).

For the empty graph, with no vertices and no edges, use \(P_G(x)=1\). It has one empty coloring and one orientation, so \(n=0\) and \(a(G)=1\). This convention is consistent with the identity below.

The factor \((-1)^n\) is essential: \(P_G(-1)\) itself may be negative. The identity is a standard result; its general proof is treated in the proof of Stanley’s formula. Here we apply it and independently verify it for paths, cycles and complete graphs. In each case, the direct orientation count also checks that the polynomial evaluation has the intended meaning.

Paths: Every Edge Can Be Oriented Freely

For \(n\geq 1\), the path \(P_n\) has \(n\) vertices and \(n-1\) edges. Its chromatic polynomial is $$ P_{P_n}(x)=x(x-1)^{n-1}. $$ Indeed, the first vertex has \(x\) color choices, and each subsequent vertex has \(x-1\) choices because it must differ from its one already-colored neighbor.

Proof. There are \(n-1\) edges, and each has two possible directions, so there are \(2^{n-1}\) orientations in total. None contains a directed cycle, since a directed cycle would require an undirected cycle in the underlying graph, while \(P_n\) has none. For the polynomial evaluation, $$ (-1)^nP_{P_n}(-1) =(-1)^n(-1)(-2)^{n-1} =(-1)^n(-1)^n2^{n-1} =2^{n-1}. $$ Here \((-1)(-2)^{n-1}=(-1)^n2^{n-1}\), so the two sign factors multiply to \(1\). For \(n=1\), this gives \(2^0=1\), as required: the one-vertex graph has no edges and exactly one orientation. \(\square\)

Cycles: Exclude the Two Directed Cycles

For \(n\geq3\), the cycle \(C_n\) has \(n\) vertices and \(n\) edges. Its chromatic polynomial is $$ P_{C_n}(x)=(x-1)^n+(-1)^n(x-1). $$ This standard cycle formula counts proper colorings with the requirement that the last vertex also differ in color from the first. Substituting \(-1\) gives $$ P_{C_n}(-1)=(-2)^n+(-1)^n(-2)=(-1)^n(2^n-2). $$ Thus \((-1)^nP_{C_n}(-1)=2^n-2\).

Proof. Each of the \(n\) edges has two possible directions, giving \(2^n\) orientations. A directed cycle in an orientation of \(C_n\) must follow the full underlying cycle, so it occurs precisely when all edges point consistently around the cycle. There are two such orientations. Removing them leaves \(2^n-2\) acyclic orientations. The displayed cycle-polynomial calculation gives \((-1)^nP_{C_n}(-1)=2^n-2\), proving the claimed equality. \(\square\)

Complete Graphs: Acyclic Orientations Are Total Orders

The complete graph \(K_n\) has every pair of distinct vertices adjacent, and its chromatic polynomial is the falling factorial $$ P_{K_n}(x)=x(x-1)(x-2)\cdots(x-n+1). $$ For positive integer \(x\), this follows by choosing distinct colors for all \(n\) vertices in order. At \(-1\), its factors are \(-1,-2,\ldots,-n\), so $$ P_{K_n}(-1)=(-1)^n n!,\qquad (-1)^nP_{K_n}(-1)=n!. $$

Proof. A total order of the vertices orients each edge from its earlier endpoint to its later endpoint. This orientation is acyclic, because following a directed edge strictly increases position in the order, which cannot happen all the way around a cycle. Conversely, consider an acyclic orientation of \(K_n\). It has a vertex with no incoming edge: otherwise, starting at any vertex and repeatedly following an incoming edge backwards would, by finiteness, revisit a vertex and produce a directed cycle. Remove such a vertex and repeat on the remaining acyclic orientation. This gives an order in which every edge points from earlier to later. At each stage the vertex with no incoming edge is unique, since any two vertices are adjacent and the edge between them points into one of them. Thus the order is unique. There are \(n!\) total orders, including one empty order when \(n=0\), so there are \(n!\) acyclic orientations. Finally, the falling-factorial formula gives \(P_{K_n}(-1)=(-1)^n n!\), and multiplication by \((-1)^n\) gives \(n!\). \(\square\)

Sign Checks and Common Uses

The three families illustrate how the same polynomial evaluation reflects different orientation counts: every edge direction is allowed on a path; a cycle excludes its two consistently directed orientations; and a complete graph encodes an ordering. The identity is useful when a chromatic polynomial is already known or computed: it turns one exact evaluation into a count of acyclic orientations without enumerating orientations individually.

A common mistake is to mishandle the sign when evaluating at \(-1\). For the four-vertex path, an incorrect calculation might write $$ (-1)(-2)^3=-8. $$ The correction is \((-2)^3=-8\), so \((-1)(-8)=8\). Then \((-1)^4=1\), and the signed value remains \(8\). The sign factor in Stanley’s identity is applied to the correctly evaluated polynomial; it is not an extra factor to insert inside the polynomial calculation.

Another useful check is that the final signed value must be a nonnegative integer, since it equals a number of orientations. That check can reveal an error but does not replace the calculation: a positive answer alone does not establish that the polynomial or orientation count was computed correctly. Verify both, as in the examples.