排列与逆序数
定义1.1 由 \(1,2,3,\cdots,n\) 组成的有序数组称为一个 \(n\) 阶排列。
需要注意的是，\(n\) 阶排列是一个有序数组。例如，\((1,2)\) 与 \((2,1)\) 尽管都是由元素 \(1,2\)组成的，但是它们是两个不同的排列，因为它们的顺序不同。以下，我们在没有歧义的情况下，将 \(n\) 阶排列 \((j_1,j_2,j_3,\cdots,j_n)\) 简记为 \(j_1 j_2j_3\cdots j_n\) .
定义1.2 我们称 \(j_1j_2j_3\cdots j_n\) 中的一对元素 \(j_p,j_q\) 为一对逆序，当且仅当 \(j_p > j_q\) 且 \(p<q\) . 这个排列中所有不同的逆序的个数称为这个排列的逆序数，记为 \(\tau(j_1j_2j_3\cdots j_n)\)
定义1.3 逆序数为奇数的排列为奇排列，逆序数为偶数的排列为偶排列。特别地，我们称\(123\cdots n\) 为自然排列。
对于排列的一个基本的操作称为对换，指将排列中的两个元素互换位置。我们可以得到下面的命题
定理1.1 对换改变排列的奇偶性。
证明：分类讨论。当对换的两个元素是相邻的时候，如
\[\cdots jk\cdots\Rightarrow\cdots kj\cdots \]对于这个排列中的一对元素 \(i_1i_2\) ,若这两个元素都不是 \(j\) 或 \(k\) ,则 \(i_1i_2\) 为顺序或逆序并不受该对换影响。若 \(i_1i_2\) 中的只一个元素是 \(j\) 或 \(k\) ，则易见它的排序仍然不变。若 \(i_1i_2\) 就是 \(jk\) 则经过这个对换将 \(jk\) 由顺序变为逆序(由逆序变为顺序)。可以看出相邻对换会将逆序数加或减一，由定义知改变了排列的奇偶性。
接下来考虑对换两元素不相邻的情况。若对换两元素不相邻，即
\[\cdots i_{n-1}ji_{n+1}\cdots i_{m-1}ki_{m+1}\cdots\Rightarrow \cdots i_{n-1}ki_{n+1}\cdots i_{m-1}ji_{m+1}\cdots \]则这个对换可以由若干次相邻对换得到。首先将 \(j\) 通过 \(m-n\) 次相邻对换移到 \(k\) 的左侧
\[\cdots i_{n-1}ki_{n+1}\cdots i_{m-1}ji_{m+1}\cdots\Rightarrow\cdots i_{n-1}jki_{n+1}\cdots i_{m-1}i_{m+1}\cdots \]然后再将 \(k\) 通过 \(m-n-1\) 次相邻对换移到 \(i_{m-1}\) 与 \(i_{m+1}\) 中间
\[\cdots i_{n-1}jki_{n+1}\cdots i_{m-1}i_{m+1}\cdots\Rightarrow\cdots i_{n-1}ji_{n+1}\cdots i_{m-1}ki_{m+1}\cdots \]这样就得到了最初的对换，此时我们进行了 \((m-n)+(m-n-1)\) 次相邻对换，奇数次改变了奇偶性，易见最终这个对换也改变了奇偶性。 \(\Box\)
有了这个重要的定理，我们可以证明一些重要的结论
定理1.2 所有的 \(n\) 阶排列中奇排列与偶排列数量相同
证明：设偶排列个数为 \(s\) ，奇排列个数为 \(t\) .若两个偶排列不同，则至少有两个位置对应的元素不同。对于所有的偶排列，对换它们的前两个元素，则得到了 \(s\) 个不同的奇排列，得 \(s\ge t\) ，反之，又可以得到 \(s\le t\) ，故 \(s=t\) . \(\Box\)
行列式的定义
对于一个 $ n$ 行 \(n\) 列的数组，行列式是这样的一种运算，它将这个数组计算为一组数。
定义1.3
\[\begin{vmatrix} {a_{11}}&{a_{12}}&{\cdots}&{a_{1n}}\\ {a_{21}}&{a_{22}}&{\cdots}&{a_{2n}}\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\ {a_{n1}}&{a_{n2}}&{\cdots}&{a_{nn}}\\ \end{vmatrix} =\sum_{j_1j_2j_3\cdots j_n} (-1)^{\tau(j_1j_2j_3\cdots j_n)}a_{1j_1}a_{2j_2}\cdots a_{nj_n} \]又记为 \(\det(A)\) 或 \(|A|\)
其中 \(\sum\limits_{j_1j_2j_3\cdots j_n}\) 表示对所有可能的 n 阶排列进行求和。
在定义时我们要求 \(a\) 的第一个指标按照顺序排列，而对第二个指标求逆序数，实际上这是不必要的
定理1.3
\[\det(A)=\sum_{j_1j_2j_3\cdots j_n} (-1)^{\tau(j_1j_2j_3\cdots j_n)+\tau(i_1i_2i_3\cdots i_n)}a_{i_{1}j_1}a_{i_{2}j_2}\cdots a_{i_{n}j_n} \]其中
\[A=\begin{pmatrix} {a_{11}}&{a_{12}}&{\cdots}&{a_{1n}}\\ {a_{21}}&{a_{22}}&{\cdots}&{a_{2n}}\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\ {a_{n1}}&{a_{n2}}&{\cdots}&{a_{nn}}\\ \end{pmatrix} \]
此处的 \(A\) 为矩阵，尽管我们并没有引入矩阵的概念，但在此处，我们只需要知道 \(\det(A)\) 与定义1.3中的行列式形式一致即可。
标签：prime,tau,排列,对换,笔记,cdots,行列式,代数,2j From： https://www.cnblogs.com/XingMath/p/16977136.html证明：这两种求和有着相同的项数，且每项之间只有前方符号不同，因此只需证明对应项符号相等即可。对于 \(a_{i_{1}j_1}a_{i_{2}j_2}\cdots a_{i_{n}j_n}\) ，设它进行了 \(t\) 次对换后将第一个指标 \(i_n\) 变为自然排列，即
\[a_{i_{1}j_1}a_{i_{2}j_2}\cdots a_{i_{n}j_n}\Rightarrow a_{1j_1^{\prime}}a_{2j_2^{\prime}}\cdots a_{nj_n^{\prime}} \]若 \(\tau(i_1i_2i_3\cdots i_n)\) 与 \(\tau(j_1j_2j_3\cdots j_n)\) 有相同的奇偶性，则它们经过相同次数的对换后仍具有相同的奇偶性，得 \(j_1^{\prime}j_2^{\prime}j_3^{\prime}\cdots j_n^{\prime}\) 为偶排列，于是有
\[(-1)^{\tau(j_1j_2j_3\cdots j_n)+\tau(i_1i_2i_3\cdots i_n)}=(-1)^{\tau{({j_1^{\prime}j_2^{\prime}j_3^{\prime}\cdots j_n^{\prime}}})} \]若 \(\tau(i_1i_2i_3\cdots i_n)\) 与 \(\tau(j_1j_2j_3\cdots j_n)\) 有不同的奇偶性，则它们经过相同次数的对换后仍具有不同的奇偶性，得 \(j_1^{\prime}j_2^{\prime}j_3^{\prime}\cdots j_n^{\prime}\) 为奇排列，于是有
\[(-1)^{\tau(j_1j_2j_3\cdots j_n)+\tau(i_1i_2i_3\cdots i_n)}=(-1)^{\tau{({j_1^{\prime}j_2^{\prime}j_3^{\prime}\cdots j_n^{\prime}}})} \]这样就证明了命题。 \(\Box\)