異なる自然数からなる順列の中から2つの数をとりだして順番を保ったまま順序対を作ったとき、その順序対を構成する1つ目の数が2つ目の数よりも大きければ、その順序対は転倒しているといいます。さらに、順列から取り出し得るすべての順列を調べたとき、転倒している順序対の個数が偶数ならばその順列を偶順列と呼び、転倒している順序対の個数が奇数ならばその順列を奇順列と呼びます。

順列の転倒

\(n\)個の異なる自然数からなる順列(permutation)\begin{equation}
\left( p_{1},p_{2},\cdots ,p_{i},\cdots ,p_{j},\cdots ,p_{n}\right) \tag{1}
\end{equation}について考えます。この順列の中から 2 つの数\(p_{i},p_{j}\)を任意に選び取り出した上で、もとの順列\(\left( 1\right) \)の中でのそれらの順序を保ったまま組\(\left( p_{i},p_{j}\right) \)をつくります。この組を順序対(ordered pair)と呼びます。このとき、\( p_{i}<p_{j} \)であれば順序対\(\left( p_{i},p_{j}\right) \)は転倒していない(not inverse)といい、\(p_{i}>p_{j}\)であれば順序対\(\left( p_{i},p_{j}\right) \)は転倒している(inverse)といいます。

順列\(\left( 1\right) \)からつくることのできる順序対の個数は、\(n\)個の異なる自然数の中から\(2\)個の自然数を選ぶ場合の数に等しいため、全部で\(\binom{n}{2}\)個だけ存在します。その中でも転倒している順序対の個数を順列\(\left( 1\right) \)の転倒の個数(number of swaps)と呼びます。

転倒の個数が偶数個である順序対を偶順列(even permutations)と呼び、転倒の個数が奇数個である順序対を奇順列(odd permutations)と呼びます。ちなみに、順列\(\left( 1\right) \)においてすべての数が小さい順に並んでいる場合、その順列の転倒の個数は\(0\)ですが、これを偶順列として扱います。

例(順列の転倒の個数)
異なる3個の数\(1,2,3\)からなる順列\begin{equation*}
\left( 2,3,1\right)
\end{equation*}からは\(\binom{3}{2}=3\)個の順列を取り出せます。その中でも転倒しているものは\(\left( 2,1\right) ,\left( 3,1\right) \)の2個であるため、この順列は偶順列です。
例(順列の転倒の個数)
異なる5個の数\(1,2,3,4,5\)からなる順列\begin{equation*}
\left( 2,1,3,5,4\right)
\end{equation*}からは\(\binom{5}{2}=10\)個の順列を取り出せます。その中でも転倒しているものは\(\left( 2,1\right) ,\left( 5,4\right) \)の2個であるため、この順列は偶順列です。
例(順列の転倒の個数)
異なる\(n\)個の数\(1,2,3,\cdots ,n\)からなる順列\begin{equation*}
\left( n,n-1,n-2,\cdots ,3,2,1\right)
\end{equation*}からは\(\binom{n}{2}=\frac{n\left( n-1\right) }{2}\)個の順列を取り出せます。さらに、この\(\frac{n\left( n-1\right) }{2}\)個の順列はすべて転倒しているため、\(\frac{n\left( n-1\right) }{2}\)が偶数の場合にはこの順列は偶順列であり、\(\frac{n\left( n-1\right) }{2}\)が奇数の場合には奇順列です。

 

順列の転倒に関する規則

順列の中の隣り合う 2 つの数を入れ替える場合、以下の命題が成り立ちます。

補題(隣り合う2つの数を入れ替える)
\(n\)個の異なる自然数からなる順列\begin{equation*}
\left( p_{1},p_{2},\cdots ,p_{i},\cdots ,p_{j},\cdots ,p_{n}\right)
\end{equation*}において、隣り合う任意の 2 つの数\(p_{i},p_{i+1}\)だけを入れ替えた順列をつくると、この順列ともとの順列とでは、転倒の個数の差は常に\(1\)である。

上の補題を利用すると、順列の中の(隣り合うとは限らない)任意の 2 つの数を入れ替える場合に関して、以下の命題が成り立つことを示すことができます。

補題(任意の2つの数を入れ替える)
\(n\)個の異なる自然数からなる順列\begin{equation*}
\left( p_{1},p_{2},\cdots ,p_{i},\cdots ,p_{j},\cdots ,p_{n}\right)
\end{equation*}において、任意の 2 つの数\(p_{i},p_{j}\)だけを入れ替えた順列をつくると、この順列ともとの順列とでは、転倒の個数の差は常に奇数である。

転倒の個数の差が奇数であるとは、数を入れ替える前後で順列の奇・偶が逆になることを意味するため、以下の命題が成り立ちます。

定理(任意の2つの数を入れ替える)
\(n\)個の異なる自然数からなる順列\begin{equation*}
\left( p_{1},p_{2},\cdots ,p_{i},\cdots ,p_{j},\cdots ,p_{n}\right)
\end{equation*}において、任意の 2 つの数\(p_{i},p_{j}\)だけを入れ替えた順列をつくると、この順列ともとの順列とでは、順列の奇・偶が逆になる。つまり、もとの順列が偶順列ならば入れ替え後の順列は奇順列であり、もとの順列が奇順列ならば入れ替え後の順列は偶順列である。

 

順列の符号

異なる自然数からなる順列\(\left( p_{1},p_{2},\cdots ,p_{n}\right) \)の転倒の個数を\(N\)とするとき、この順列の符号(sign)を、\begin{equation*}
\varepsilon \left( p_{1},p_{2},\cdots ,p_{n}\right) =\left( -1\right) ^{N}
\end{equation*}と定義します。定義より、\begin{equation*}
\varepsilon \left( p_{1},p_{2},\cdots ,p_{n}\right) =\left\{
\begin{array}{c}
1,\quad \left( p_{1},p_{2},\cdots ,p_{n}\right) \text{が偶順列のとき} \\
-1,\quad \left( p_{1},p_{2},\cdots ,p_{n}\right) \text{が奇順列のとき}\end{array}\right.
\end{equation*}となります。

例(順列の符号)
異なる 3 個の数\(1,2,3\)からなる順列\begin{equation*}
\left( 2,3,1\right)
\end{equation*}は偶順列ですので、\(\varepsilon \left( 2,3,1\right) =1\)となります。
例(順列の符号)
異なる 5 個の数\(1,2,3,4,5\)からなる順列\begin{equation*}
\left( 2,1,3,5,4\right)
\end{equation*}は偶順列ですので、\(\varepsilon \left( 2,1,3,5,4\right) =1\)となります。
例(順列の符号)
異なる\(n\)個の数\(1,2,3,\cdots ,n\)からなる順列\begin{equation*}
\left( n,n-1,n-2,\cdots ,3,2,1\right)
\end{equation*}は、\(\frac{n\left( n-1\right) }{2}\)が偶数の場合には偶順列であり、\(\frac{n\left( n-1\right) }{2}\)が奇数の場合には奇順列ですので、\begin{equation*}
\varepsilon \left( n,n-1,n-2,\cdots ,3,2,1\right) =\left\{
\begin{array}{c}
1,\quad \frac{n\left( n-1\right) }{2}\text{が偶数のとき} \\
-1,\quad \frac{n\left( n-1\right) }{2}\text{が奇数のとき}\end{array}\right.
\end{equation*}となります。

先ほど、異なる自然数からなる順列において任意の 2 つの数を入れ替えると順列の奇・偶が逆になることを指摘しました。この事実を順列の符号を用いて表現したものが以下の命題です。

系(任意の2つの数を入れ替える)
\(n\)個の異なる自然数からなる順列\begin{equation*}
\left( p_{1},p_{2},\cdots ,p_{i},\cdots ,p_{j},\cdots ,p_{n}\right)
\end{equation*}において、任意の 2 つの数\(p_{i},p_{j}\)だけを入れ替えた順列をつくると、順列の符号が逆になる。つまり、もとの順列の符号が\(1\)ならば入れ替え後の順列の符号は\(-1\)であり、もとの順列の符号が\(-1\)ならば入れ替え後の順列の符号は\(1\)である。