順列の偶奇性

σ を順位付けされた領域S上の順列とする。すべての順列は転置（2要素の交換）のシーケンスによって生成できる。以下はそのような分解の1つである。

σ = T ₁ T ₂ ... T _k

kの偶奇がσの反転数の偶奇に等しいことを示したい。

あらゆる転置は、隣接する要素の奇数個の転置の積として表すことができます。例えば、

(2 5) = (2 3) (3 4) (4 5) (4 3) (3 2)。

一般に、集合 {1,..., i ,..., i+d ,...} 上の転置 ( i  i+d ) は、 d上の再帰による2 d −1 個の隣接する転置の合成として表すことができます。

• 基本ケースd=1は簡単です。

• 再帰的なケースでは、まず ( i , i+d ) を ( i , i +1) ( i +1, i+d ) ( i , i +1 ) と書き換えます。次に、 ( i +1, i+d ) を隣接する転置として再帰的に書き換えます。

上記の転置T ₁  ...  T _kをそれぞれこのように分解すると、新しい分解が得られます。

σ = A ₁ A ₂ ... A _m

ここで、 A ₁ ... A _{m は}すべて隣接しています。また、 mの偶奇性はkの偶奇性と同じです。

これは事実です。すべての順列τと隣接する転置a について、 aτ はτよりも反転が 1 つ少ないか、1 つ多くなります。言い換えると、順列の反転数の偶奇性は、隣接する転置と合成されると入れ替わります。

したがって、 σの反転数のパリティはまさにmのパリティであり、 kのパリティでもあります。これが私たちが証明しようとしたことです。

別の証明では、ヴァンデルモンド多項式を使用する。

${\displaystyle P(x_{1},\ldots ,x_{n})=\prod _{i<j}(x_{i}-x_{j}).}$

例えばn = 3の場合、

${\displaystyle P(x_{1},x_{2},x_{3})=(x_{1}-x_{2})(x_{2}-x_{3})(x_{1}-x_{3}).}$

ここで、与えられた数{1, ...,  n }の順列 σに対して、次のように定義する。

${\displaystyle \operatorname {sgn}(\sigma )={\frac {P(x_{\sigma (1)},\ldots ,x_{\sigma (n)})}{P(x_{1},\ldots ,x_{n})}}.}$

多項式は符号を除いて同じ因数を持つので、sgn( σ )は+1か-1のいずれかとなる。さらに、σとτが2つの順列である場合、 ${\displaystyle P(x_{\sigma (1)},\dots ,x_{\sigma (n)})}$${\displaystyle P(x_{1},\dots ,x_{n})}$

${\displaystyle {\begin{aligned}\operatorname {sgn}(\sigma \tau )&={\frac {P(x_{\sigma (\tau (1))},\ldots ,x_{\sigma (\tau (n))})}{P(x_{1},\ldots ,x_{n})}}\\[4pt]&={\frac {P(x_{\sigma (1)},\ldots ,x_{\sigma (n)})}{P(x_{1},\ldots ,x_{n})}}\cdot {\frac {P(x_{\sigma (\tau (1))},\ldots ,x_{\sigma (\tau (n))})}{P(x_{\sigma (1)},\ldots ,x_{\sigma (n)})}}\\[4pt]&=\operatorname {sgn}(\sigma )\cdot \operatorname {sgn}(\tau ).\end{aligned}}}$

3番目のアプローチは、群S _nを生成元τ ₁ , ..., τ _{n −1}と関係 式で表現するものである。

• ${\displaystyle \tau _{i}^{2}=1}$  すべての私
• ${\displaystyle \tau _{i}^{}\tau _{i+1}\tau _{i}=\tau _{i+1}\tau _{i}\tau _{i+1}}$すべてのi < n  − 1   に対して
• ${\displaystyle \tau _{i}^{}\tau _{j}=\tau _{j}\tau _{i}}$   もし${\displaystyle |i-j|\geq 2.}$

${\displaystyle \tau _{i}}$

x < yかつσ ( x ) > σ ( y )となるようなx、yのペアは反転と呼ばれることを思い出してください。反転のカウントが 2 要素のスワップのカウントと同じパリティを持つことを示します。そのためには、どの 2 つの要素がスワップされるか、およびどのような順列がすでに適用されているかに関係なく、すべてのスワップが反転のカウントのパリティを変更することを示します。i番目の要素とj番目の要素を交換するとします。明らかに、 iまたはjと[ i、j ]の外部の要素によって形成される反転は影響を受けません。区間( i、j )内のn = j − i − 1個の要素について、それらのv _{i が}iと反転を形成し、それらのv _jがjと反転を形成すると仮定します。iとj が交換されると、iとのv _i反転はなくなりますが、n − v _i反転が形成されます。したがって、得られる反転iの数はn − 2 v _iとなり、これはnと同じパリティを持ちます。

同様に、 jで得られた反転の数もnと同じパリティを持ちます。したがって、両方を合わせた得られた反転の数のパリティは 2 nまたは 0 と同じです。ここで、i番目とj番目の要素を交換することで得られた (または失われた) 反転の数を数えると、この交換によって反転の数のパリティが変わることがわかります。これは、ペア(i,j)で得られた (または失われた) 反転の数に 1 が加算 (または減算) されるためです。

転置の 2 つの要素に挟まれた要素について考えてみましょう。各要素は、2 つの転置要素の完全に上、完全に下、またはその間に位置します。

完全に上または完全に下にある要素は、転置が適用されたときに反転カウントに何も寄与しません。中間の要素は寄与します。 ${\displaystyle 2}$

${\displaystyle \pm 1}$