参考资料
引理
一个排列的逆序对数的奇偶性与（排列的长度-环数）相同。
证明：
观察 1：如果交换排列中的两个元素，逆序对数的奇偶性恰好会改变。
- 假设交换的元素是 $i, j (i < j)$
- $i$ 左侧，$j$ 右侧的元素的贡献不会变化
- 开区间 $(i,j)$ 中的元素的贡献的奇偶性不变
- $i,j$ 的贡献会变化 1（加 1 或者减 1）
观察 2：单位排列的逆序对数为 0，是一个偶数。
观察 3：可以通过（排列 $P$ 的长度-环数）次“交换两个元素”的操作，将单位排列变成 $P$。
定义们
定义有向图 $G$ 的以 $r$ 为根的有向生成树 (oriented spanning tree) 为：$r$ 出度为 $0$、其余点出度为 $1$ 的弱连通生成图。
定义有向图 $G$ 的拉普拉斯矩阵 $L$ 为 $D-A$，其中
而 $A$ 为 $G$ 的邻接矩阵（$A$ 为 01 矩阵且 $A_{i,j}$ 为 $1$ 当且仅当 $G$ 中存在一条从 $i$ 到 $j$ 的边）。
设 $L_r$ 为去掉 $L$ 的第 $r$ 行、第 $r$ 列之后得到的 $(n-1)\times (n-1)$ 的矩阵。
矩阵树定理：$G$ 的以 $r$ 为根的有向生成树个数为 $\det(L_r)$。
容易把矩阵树定理扩展到无向图的生成树计数。
证明
如果选取的根 $r \neq n$，则可以通过重标号让 $r=n$。所以下面我们只考虑 $r=n$ 的情况。
定义 $S_n$ 为长度为 $n$ 在所有排列构成的集合。对于一个排列 $\sigma$，定义 $\operatorname{sgn}(\sigma)$ 为 $(-1)^{\sigma \text{的逆序对个数}}$。
考虑这个式子的组合意义：不考虑正负号，当 $\sigma(i) = i$ 的时候，$L_{i,\sigma(i)}$ 相当于选择一条从 $i$ 出发的边的方案数；当 $\sigma(i) \neq i$ 的时候，$L_{i,\sigma(i)}$ 相当于选择一条从 $i$ 到 $\sigma (i)$ 的边的方案数。注意到这也就相当于是在枚举 $n$ 点出度为 $0$、其余点出度为 $1$ 的子图。
我们要证明的是：在枚举 $\sigma$ 的过程中，所有是树的子图被统计到的系数都是 $1$，所有不是树的子图被统计到的系数都是 $0$。
注意到：由于 $\sigma$ 是一个排列，所以 $i\to \sigma(i)$ 必然形成若干个大小大于 $1$ 的环和一些 $i = \sigma(i)$ 的单点（自环）。
对于树：由于树无环，所以这种子图绝对不可能选择 $i\to \sigma(i)(\sigma(i)\neq i)$ 的边，所以它只会在 $\sigma = \{1,2,\cdots n-1\}$ 的时候被数到，其系数显然为 $1$。
对于不是树的子图：它至少包含了一个环。设子图中的环为 $C_1,C_2,\cdots C_k(k > 0)$（$C_i$ 为第 $i$ 个环上的点构成的点集），设不在环上的点集为 $T$。考虑什么样的 $\sigma$ 会数到这个子图：$T$ 中的每个点 $x$ 一定都有 $\sigma(x) = x$；而对于每个 $C_i$，要么 $C_i$ 中的每个点都有 $\sigma(x) = x$，要么就用 $i\to \sigma(i)(i\neq \sigma(i))$ 这样的形式来表示出 $C_i$ 这个环。假设 $C_{i_1},C_{i_2},\cdots C_{i_l}$ 这些环上的点满足 $\sigma(x) = x$，而 $C_{j_1},C_{j_2},\cdots C_{j_m}$ 这些环是用 $i \to \sigma(i)(i\neq \sigma(i))$ 表示的，那么对应的 $\operatorname{sgn}(\sigma)$ 为（考虑前面的引理）
而 $\prod_{i=1}^{n-1} L_{i,\sigma(i)}$ 所带的系数为
注意到两者的乘积恰好为 $(-1)^m$。
所有可能的 $\sigma$ 的系数之和为
在 $k>0$ 的时候这个系数为 $0$。
扩展
这个证明的本质是：枚举所有的 $n$ 号点出度为 $0$、其余点出度为 $1$ 的子图，并说明这其中每个有环的子图贡献系数为 0，无环的子图贡献系数为 1。
我们可以得到一个更加一般的形式：