The number of regions of the inversion arrangement of a permutation. The inversion arrangement $\mathcal{A}_w$ consists of the hyperplanes $x_i-x_j=0$ such that $(i,j)$ is an inversion of $w$. Postnikov [4] conjectured that the number of regions in $\mathcal{A}_w$ equals the number of permutations in the interval $[id,w]$ in the strong Bruhat order if and only if $w$ avoids $4231$, $35142$, $42513$, $351624$. This conjecture was proved by Hultman-Linusson-Shareshian-Sjöstrand [1]. Oh-Postnikov-Yoo [3] showed that the number of regions of $\mathcal{A}_w$ is $|\chi_{G_w}(-1)|$ where $\chi_{G_w}$ is the chromatic polynomial of the inversion graph $G_w$. This is the graph with vertices ${1,2,\ldots,n}$ and edges $(i,j)$ for $i\lneq j$ $w_i\gneq w_j$. For a permutation $w=w_1\cdots w_n$, Lewis-Morales [2] and Hultman (see appendix in [2]) showed that this number equals the number of placements of $n$ non-attacking rooks on the south-west Rothe diagram of $w$.

The number of elements less than or equal to the given element in Bruhat order.

The total displacement of a permutation. This is, for a permutation $\pi$ of $n$, given by $\sum_{i = 1}^n | \pi(i) - i |.$ This is twice the statistic [[St000029]] and can be found in [3, Problem 5.1.1.28] and also in [1, 2].

The sign of a permutation.

The number of acyclic orientations of a graph.

The number of forests contained in a graph. That is, for a graph $G = (V,E)$ with vertices $V$ and edges $E$, the number of subsets $E' \subseteq E$ for which the subgraph $(V,E')$ is acyclic. If $T_G(x,y)$ is the Tutte polynomial [2] of $G$, then the number of forests contained in $G$ is given by $T_G(2,1)$.

The number of spanning subgraphs of a graph. This is the number of subsets of the edge set of the graph, or the evaluation of the Tutte polynomial at $x=y=2$.

The sum of the vertex degrees of a graph. This is clearly equal to twice the number of edges, and, incidentally, also equal to the trace of the Laplacian matrix of a graph. From this it follows that it is also the sum of the squares of the eigenvalues of the adjacency matrix of the graph. The Laplacian matrix is defined as $D-A$ where $D$ is the degree matrix (the diagonal matrix with the vertex degrees on the diagonal) and where $A$ is the adjacency matrix. See [1] for detailed definitions.

The sum of the number of descents and the number of recoils of a permutation. This statistic is the sum of [[St000021]] and [[St000354]].

The composition number of a graph. This is the number of set partitions of the vertex set of the graph, such that the subgraph induced by each block is connected.