転倒数

同義語:inversion numbernumber of inversionsLehmerコードLehmer コードLehmer code

概要

転倒数(inversion number)とは、置換 $\sigma\in S_n$ について $i< j$ かつ $\sigma(i)>\sigma(j)$ となる組 $(i,j)$ の個数 $\operatorname{inv}(\sigma)$ のことである。偶奇は置換の符号を与え、値は隣接互換の積として書くときの最小の個数に等しい。各位置の右にある小さい値の個数を並べた転倒表は $S_n$ と $\prod_i\{0,\dots,n-i\}$ の全単射を与え、これから転倒数の母関数が $q$ 階乗 $[n]_q!$ になること、分布の対称性、一様な置換での平均 $n(n-1)/4$ と分散 $n(n-1)(2n+5)/72$ が従う。降下の位置の和である主要指数も同じ分布をもつ。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 置換, 対称群, 置換の符号

転倒数(inversion number)とは、$\{1,\dots,n\}$ の置換 $\sigma$ について、$i< j$ かつ $\sigma(i)>\sigma(j)$ となる組 $(i,j)$ の個数 $\operatorname{inv}(\sigma)$ のことである。並び $\sigma(1)\sigma(2)\cdots\sigma(n)$ の中で大小の順が逆になっている 2 項の組を数えた量で、並びが昇順からどれだけ乱れているかを測る。
転倒数には 3 つの顔がある。偶奇は置換の符号 $\operatorname{sgn}\sigma=(-1)^{\operatorname{inv}(\sigma)}$ を与える(置換の符号)。値そのものは、隣接互換 $s_k=(k\ \ k+1)$ の積として $\sigma$ を書くときの最小の個数、すなわち Coxeter 系 $(S_n,\{s_1,\dots,s_{n-1}\})$ の長さに等しい(置換の符号 の命題「隣接互換の積への分解」、Weyl群の長さ関数 の例「$A_{n-1}$ 型:長さは転倒数」)。この記事は 3 つ目の顔、すなわち 数え上げの統計量 としての転倒数を扱う。転倒表による $S_n$ と整数の組の集合との全単射(thm-inv-table)から、転倒数の母関数が $q$ 階乗 $[n]_q!$ になること、分布の対称性・平均・分散を導く。さらに、降下の位置の和である主要指数が転倒数と同じ分布をもつこと(thm-inv-maj)を証明し、2 つの並びの食い違いを数える距離を述べる。

定義

転倒と転倒数

$n\ge1$、$\sigma\in S_n$ とし、$\sigma$ を値の並び $\sigma(1)\sigma(2)\cdots\sigma(n)$ で表す。$1\le i< j\le n$ で $\sigma(i)>\sigma(j)$ を満たす組 $(i,j)$ を $\sigma$ の 転倒(inversion)といい、転倒の全体を $\operatorname{Inv}(\sigma)$、その個数
$$ \operatorname{inv}(\sigma):=\lvert\operatorname{Inv}(\sigma)\rvert $$
を $\sigma$ の 転倒数 という。より一般に、整数の列 $a=a_1a_2\cdots a_n$ について $\operatorname{inv}(a):=\#\{(i,j)\mid i< j,\ a_i>a_j\}$ と定める。

転倒を位置の組 $(i,j)$ でなく値の組 $(\sigma(i),\sigma(j))$ で表す流儀もある(Sta11 §1.3, p. 36)が、個数は同じである。つねに $0\le\operatorname{inv}(\sigma)\le\binom n2$ であり、$\operatorname{inv}(\sigma)=0$ となるのは恒等置換 $e$ だけ、$\operatorname{inv}(\sigma)=\binom n2$ となるのは逆順の置換 $w_0(i)=n+1-i$ だけである。前者は転倒がなければ $\sigma(1)< \dots< \sigma(n)$ となること、後者はすべての組が転倒なら $\sigma(1)>\dots>\sigma(n)$ となることから分かる($w_0$ の転倒数は 置換の符号 の例「逆順の置換」でも計算されている)。
符号と長さの関係の証明はそれぞれの記事にあり、ここでは繰り返さない。$0$ と $1$ だけからなる列の転倒数は q二項係数 の定理「転倒数による解釈」で数えられている。

3 文字と 4 文字の置換

$S_3$ の 6 個の置換の転倒数は、$123$ が $0$、$213$ と $132$ が $1$、$231$ と $312$ が $2$、$321$ が $3$ である(転倒の列挙は 置換の符号 の例「3 文字の置換の符号」にある)。転倒数が $k$ の置換の個数を $I(n,k)$ と書くと $(I(3,k))_{k=0}^{3}=(1,2,2,1)$ である。$S_4$ の $24$ 個では
$$ (I(4,k))_{k=0}^{6}=(1,3,5,6,5,3,1) $$
であり、たとえば $\sigma=3142$ の転倒は $(1,2)$、$(1,4)$、$(3,4)$ の 3 個である。

この列が左右対称であることは、下の prop-inv-distribution で一般に示す。

転倒表

転倒表

$\sigma\in S_n$ と $1\le i\le n$ について
$$ c_i(\sigma):=\#\{j\mid i< j\le n,\ \sigma(j)< \sigma(i)\} $$
(位置 $i$ より右にあって $\sigma(i)$ より小さい値の個数)とおき、列 $c(\sigma):=(c_1(\sigma),\dots,c_n(\sigma))$ を $\sigma$ の 転倒表(Lehmer コード)という。また
$$ T_n:=\{(c_1,\dots,c_n)\in\mathbb{Z}^n\mid 0\le c_i\le n-i\ (i=1,\dots,n)\} $$
とおく。

$c_i(\sigma)$ は位置 $i$ を左の端とする転倒の個数なので
$$ \operatorname{inv}(\sigma)=c_1(\sigma)+c_2(\sigma)+\dots+c_n(\sigma) $$
であり、位置 $i$ の右には $n-i$ 個の値しかないので $c(\sigma)\in T_n$ である。Sta11 §1.3(pp. 35–36)は、値 $i$ ごとにその左にある $i$ より大きい値を数えた列を inversion table と呼び、上の $c(\sigma)$ を code と呼んで、$\sigma$ の code は $\sigma^{-1}$ の inversion table に等しいと注意している。どちらを使っても以下の議論は同じ形で進む。

転倒表は全単射

写像 $c\colon S_n\to T_n$ は全単射である。さらに、$R_i:=\{1,\dots,n\}\setminus\{\sigma(1),\dots,\sigma(i-1)\}$ とおくと、$\sigma(i)$ は $R_i$ の中で小さい方から $c_i(\sigma)+1$ 番目の元である。

残っている値の中の順位を読む

$\sigma$ は全単射なので、$R_i$ は $\sigma(i),\sigma(i+1),\dots,\sigma(n)$ からなる $n-i+1$ 元の集合であり、位置 $i$ より右にある値の全体は $R_i\setminus\{\sigma(i)\}$ である。したがって $c_i(\sigma)$ は $R_i$ の中で $\sigma(i)$ より小さい元の個数であり、$\sigma(i)$ は $R_i$ の中で小さい方から $c_i(\sigma)+1$ 番目である。これで後半を示した。
単射:$c(\sigma)=c(\tau)$ とする。$i$ についての帰納法で $\sigma(i)=\tau(i)$ を示す。$\sigma(1),\dots,\sigma(i-1)$ と $\tau(1),\dots,\tau(i-1)$ が一致していれば、$R_i$ は $\sigma$ と $\tau$ で同じ集合であり、後半により $\sigma(i)$ と $\tau(i)$ はともにその中で小さい方から $c_i+1$ 番目の元なので一致する。よって $\sigma=\tau$ である。
全射:$(c_1,\dots,c_n)\in T_n$ をとる。$R_1:=\{1,\dots,n\}$ とし、$i=1,2,\dots,n$ の順に、$R_i$ の小さい方から $c_i+1$ 番目の元を $\sigma(i)$ とし、$R_{i+1}:=R_i\setminus\{\sigma(i)\}$ とおく。$\lvert R_i\rvert=n-i+1>c_i$ なので、この元はつねに存在する。こうして得た $\sigma$ は $\{1,\dots,n\}$ の元をちょうど 1 回ずつ使うので置換であり、作り方の $R_i$ は後半の $R_i$ と一致する。後半により $c_i(\sigma)$ は $\sigma(i)$ の $R_i$ の中での順位から 1 を引いたものなので、$c(\sigma)=(c_1,\dots,c_n)$ である。$\square$

たとえば $c=(2,0,1,0)$ からは、$\{1,2,3,4\}$ の 3 番目の $3$、残り $\{1,2,4\}$ の 1 番目の $1$、残り $\{2,4\}$ の 2 番目の $4$、最後に $2$ を選んで $\sigma=3142$ を得る。$\operatorname{inv}(3142)=2+0+1+0=3$ は ex-inv-small と一致する。転倒表は、置換を「各段で残りの値から何番目を選ぶか」の記録として表したもので、$\lvert S_n\rvert=\lvert T_n\rvert=n!$ の 1 つの証明にもなっている。

母関数と分布

$m\ge1$ について $[m]_q:=1+q+\dots+q^{m-1}$、$[n]_q!:=[1]_q[2]_q\cdots[n]_q$ とおく($q$ 階乗)。$q=1$ とおくと $[n]_1!=n!$ である。

転倒数の母関数

$$ \sum_{\sigma\in S_n}q^{\operatorname{inv}(\sigma)}=[n]_q!=\prod_{m=1}^{n}(1+q+\dots+q^{m-1}). $$

転倒表の成分ごとに和をとる

thm-inv-table の全単射 $c$ で和を $T_n$ の上に移し、$\operatorname{inv}(\sigma)=\sum_ic_i(\sigma)$ を使うと
$$ \sum_{\sigma\in S_n}q^{\operatorname{inv}(\sigma)}=\sum_{(c_1,\dots,c_n)\in T_n}q^{c_1+\dots+c_n}=\prod_{i=1}^{n}\Bigl(\sum_{c_i=0}^{n-i}q^{c_i}\Bigr)=\prod_{i=1}^{n}[n-i+1]_q $$
であり、$m=n-i+1$ と置けば右辺になる。$\square$

これは Sta11 Corollary 1.3.13(p. 36)の式である。同じ式は、有限体 $\mathbb{F}_q$ 上の一般線形群の元を Bruhat 分解で 2 通りに数える方法でも得られる(Bruhat分解 の系「転倒数の母関数」)。

転倒数の分布

$n\ge1$、$N:=\binom n2$ とし、$I(n,k):=\#\{\sigma\in S_n\mid\operatorname{inv}(\sigma)=k\}$ とする($k< 0$ と $k>N$ では $0$)。

  1. (漸化式)$n\ge2$ なら $I(n,k)=\sum_{j=0}^{n-1}I(n-1,k-j)$ である。
  2. (対称性)$\operatorname{inv}(\sigma w_0)=N-\operatorname{inv}(\sigma)$ であり、$\sigma\mapsto\sigma w_0$(並びを逆順にする写像)は転倒数 $k$ の置換を転倒数 $N-k$ の置換に 1 対 1 に写す。とくに $I(n,k)=I(n,N-k)$ である。
  3. (平均と分散)$S_n$ から一様に選んだ置換の転倒数の平均は $\dfrac{n(n-1)}{4}$、分散は $\dfrac{n(n-1)(2n+5)}{72}$ である。
転倒表の成分は独立に動く

1:cor-inv-gf から $\sum_kI(n,k)q^k=[n]_q!=[n-1]_q!\,(1+q+\dots+q^{n-1})$ であり、両辺の $q^k$ の係数を比べればよい。
2:$\sigma w_0$ の並びは $\sigma(n)\sigma(n-1)\cdots\sigma(1)$ である。位置の組 $i< j$ に対し、$\sigma w_0$ の位置 $n+1-j< n+1-i$ にある値はそれぞれ $\sigma(j)$、$\sigma(i)$ なので、$(n+1-j,n+1-i)$ が $\sigma w_0$ の転倒であることは $\sigma(j)>\sigma(i)$、すなわち $(i,j)$ が $\sigma$ の転倒でないことと同値である。$\{i,j\}\mapsto\{n+1-j,n+1-i\}$ は 2 元部分集合全体の上の全単射なので、$\operatorname{inv}(\sigma w_0)=N-\operatorname{inv}(\sigma)$ である。$w_0^2=e$ なので $\sigma\mapsto\sigma w_0$ は $S_n$ の全単射であり、主張が従う。
3:$\sigma$ を $S_n$ から一様に選ぶと、thm-inv-table により $c(\sigma)$ は直積集合 $T_n=\prod_{i=1}^{n}\{0,1,\dots,n-i\}$ の上で一様に分布する。直積集合の上の一様分布では、各成分はそれぞれの因子の上で一様に分布し、互いに独立である(各点の確率 $1/\lvert T_n\rvert$ が因子ごとの確率の積になる)。$\{0,1,\dots,m-1\}$ の上の一様分布の平均は $(m-1)/2$、分散は
$$ \frac1m\sum_{c=0}^{m-1}c^2-\Bigl(\frac{m-1}{2}\Bigr)^2=\frac{(m-1)(2m-1)}{6}-\frac{(m-1)^2}{4}=\frac{m^2-1}{12} $$
である。$\operatorname{inv}=\sum_ic_i$ で、$c_i$ は $m=n-i+1$ の場合の一様分布に従い、$i=1,\dots,n$ で $m$ は $n,\dots,1$ を動く。独立な確率変数の和の平均と分散はそれぞれの和なので(分散)、
$$ \text{平均}=\sum_{m=1}^{n}\frac{m-1}{2}=\frac{n(n-1)}{4},\qquad \text{分散}=\sum_{m=1}^{n}\frac{m^2-1}{12}=\frac{1}{12}\Bigl(\frac{n(n+1)(2n+1)}{6}-n\Bigr)=\frac{n(n-1)(2n+5)}{72} $$
である。$\square$

平均が $N/2$ になることは 2 の対称性からも分かる。$n=4$ では平均 $3$、分散 $4\cdot3\cdot13/72=13/6$ であり、ex-inv-small の分布 $(1,3,5,6,5,3,1)$ から直接計算しても $\frac{1}{24}\sum_kk^2I(4,k)-3^2=\frac{268}{24}-9=\frac{13}{6}$ となる。

逆置換の転倒数

$\sigma\in S_n$ について $\operatorname{inv}(\sigma^{-1})=\operatorname{inv}(\sigma)$ である。より詳しく、$(i,j)\mapsto(\sigma(j),\sigma(i))$ は $\operatorname{Inv}(\sigma)$ から $\operatorname{Inv}(\sigma^{-1})$ への全単射である。

位置と値を入れ替える

$(i,j)\in\operatorname{Inv}(\sigma)$ なら $a:=\sigma(j)< b:=\sigma(i)$ であり、$\sigma^{-1}(a)=j>i=\sigma^{-1}(b)$ なので $(a,b)\in\operatorname{Inv}(\sigma^{-1})$ である。同じ規則で $\operatorname{Inv}(\sigma^{-1})$ から $\operatorname{Inv}(\sigma)$ への写像 $(a,b)\mapsto(\sigma^{-1}(b),\sigma^{-1}(a))$ を作ると、これは $(a,b)=(\sigma(j),\sigma(i))$ を $(i,j)$ に戻すので逆写像である。$\square$

これは Sta11 Proposition 1.3.14(p. 37)である。長さの言葉では、$\sigma=s_{k_1}\cdots s_{k_m}$ なら $\sigma^{-1}=s_{k_m}\cdots s_{k_1}$ なので最小の個数は等しい、という形でも分かる。一方、転倒数は共役では保たれない(置換の符号 の例「反例:転倒数は共役で変わる」)。

主要指数

降下と主要指数

$\sigma\in S_n$ について、$1\le i\le n-1$ で $\sigma(i)>\sigma(i+1)$ となる $i$ を $\sigma$ の 降下(descent)という。降下の全体を $D(\sigma)$ とし、
$$ \operatorname{maj}(\sigma):=\sum_{i\in D(\sigma)}i $$
を $\sigma$ の 主要指数(major index)という。整数の列についても同じ式で定める。

転倒は離れた位置の組も数えるが、降下は隣り合う位置だけを見る。降下 $i$ は転倒 $(i,i+1)$ でもあるので、降下の個数は転倒数以下である。主要指数は降下にその位置の重みを付けた量で、値は転倒数と一般に異なる(ex-inv-maj-small)。それにもかかわらず、両者は $S_n$ の上で同じ分布をもつ(thm-inv-maj)。この結果は MacMahon による(Sta11 第 1 章の Notes, p. 106)。Sta11 Proposition 1.4.6(pp. 41–43)は、主要指数を転倒数に写す $S_n$ の全単射を構成して証明している(同じ Notes によれば、この全単射は Foata による)。ここでは、最大の値 $n$ を挿入したときの増え方を 2 つの統計量で比べる。

最大の値の挿入

$n\ge2$、$\tau\in S_{n-1}$ とし、並び $\tau(1)\cdots\tau(n-1)$ の $n$ か所の隙間に左から $0,1,\dots,n-1$ と番号を付ける(隙間 $p$ は $\tau(p)$ と $\tau(p+1)$ の間で、隙間 $0$ は左端、隙間 $n-1$ は右端)。隙間 $p$ に $n$ を入れてできる $S_n$ の元を $\tau^{(p)}$ とする。

  1. $\operatorname{inv}(\tau^{(p)})=\operatorname{inv}(\tau)+(n-1-p)$ である。
  2. $p$ が $0,1,\dots,n-1$ を動くとき、$\operatorname{maj}(\tau^{(p)})-\operatorname{maj}(\tau)$ は $0,1,\dots,n-1$ をちょうど 1 回ずつとる。
降下の位置のずれを数える

1:$n$ はほかのどの値よりも大きいので、$n$ とその右にある $n-1-p$ 個の項の組がちょうど新しい転倒であり、それ以外の組の大小は変わらない。
2:$r:=\lvert D(\tau)\rvert$ とする。$\tau^{(p)}$ では、位置 $1,\dots,p$ の項は元のまま、位置 $p+1$ が $n$ で、元の位置 $t>p$ の項は位置 $t+1$ に移る。したがって元の降下 $t>p$ は降下 $t+1$ に移り、元の降下 $t< p$ はそのまま残る。場合を分ける。

  • $p=n-1$(右端):$\tau(n-1)< n$ なので新しい降下はできず、増え方は $0$ である。
  • $1\le p\le n-2$ で $p$ が $\tau$ の降下のとき:位置 $p$ の項 $\tau(p)$ の右隣は $n$ になるので $p$ は降下でなくなり、位置 $p+1$ は $n>\tau(p+1)$ で降下になる。増え方は $(p+1)-p$ と、右の降下のずれ $\#\{t\in D(\tau)\mid t>p\}$ の和である。$D(\tau)$ の元を右から順に $p$ とすると、増え方は $1,2,\dots,r$ になる。
  • $p$ が降下でないとき($p=0$、または $1\le p\le n-2$ で $\tau(p)< \tau(p+1)$):位置 $p+1$ が新しく降下になり($n>\tau(p+1)$)、$p\ge1$ なら位置 $p$ は $\tau(p)< n$ なので降下にならない。増え方は $(p+1)+\#\{t\in D(\tau)\mid t>p\}$ である。このような隙間を左から $p_0=0< p_1< \dots< p_{n-2-r}$ とすると(右端を除く $n-1$ か所のうち $r$ か所が降下)、$p=p_s$ より左にある降下でない位置は $p_1,\dots,p_{s-1}$ の $s-1$ 個なので、$\#\{t\in D(\tau)\mid t< p_s\}=(p_s-1)-(s-1)=p_s-s$ であり、増え方は
    $$ (p_s+1)+\bigl(r-(p_s-s)\bigr)=r+1+s $$
    である。$s=0,\dots,n-2-r$ で、これは $r+1,\dots,n-1$ をとる。
    3 つの場合をあわせると、増え方は $0$、$1,\dots,r$、$r+1,\dots,n-1$ をちょうど 1 回ずつとる。$\square$
主要指数の母関数

$n\ge1$ について
$$ \sum_{\sigma\in S_n}q^{\operatorname{maj}(\sigma)}=[n]_q! $$
である。したがって、各 $k$ について $\#\{\sigma\in S_n\mid\operatorname{maj}(\sigma)=k\}=\#\{\sigma\in S_n\mid\operatorname{inv}(\sigma)=k\}$ である。

挿入の位置で和を分ける

$n$ についての帰納法で示す。$n=1$ では両辺とも $1$ である。$n\ge2$ とする。$\sigma\in S_n$ の並びから $n$ を取り除くと $\tau\in S_{n-1}$ の並びが得られ、$\sigma$ は $\tau$ と $n$ の入る隙間 $p$ で決まる($\sigma=\tau^{(p)}$)。したがって $(\tau,p)\mapsto\tau^{(p)}$ は $S_{n-1}\times\{0,\dots,n-1\}$ から $S_n$ への全単射である。lem-inv-insert の 2 により
$$ \sum_{\sigma\in S_n}q^{\operatorname{maj}(\sigma)}=\sum_{\tau\in S_{n-1}}\sum_{p=0}^{n-1}q^{\operatorname{maj}(\tau^{(p)})}=\sum_{\tau\in S_{n-1}}q^{\operatorname{maj}(\tau)}(1+q+\dots+q^{n-1}) $$
であり、帰納法の仮定から右辺は $[n-1]_q!\,[n]_q=[n]_q!$ である。後半は cor-inv-gf と係数を比べればよい。$\square$

lem-inv-insert の 1 を同じように使うと、$\sum_{\sigma}q^{\operatorname{inv}(\sigma)}$ も同じ漸化式を満たすことが分かり、cor-inv-gf の別証明になる。2 つの統計量は「$n$ を挿入したときの増え方の集合」が $\{0,1,\dots,n-1\}$ になるという点で共通している。ただし増え方を与える隙間は一般に異なる(転倒数では右端が $0$、左端が $n-1$ だが、主要指数では左端は $\lvert D(\tau)\rvert+1$ である)。

転倒数と主要指数の比較

$S_3$ では次のとおりである。

$\sigma$$\operatorname{Inv}(\sigma)$$\operatorname{inv}$$D(\sigma)$$\operatorname{maj}$
$123$なし$0$なし$0$
$132$$(2,3)$$1$$\{2\}$$2$
$213$$(1,2)$$1$$\{1\}$$1$
$231$$(1,3),(2,3)$$2$$\{2\}$$2$
$312$$(1,2),(1,3)$$2$$\{1\}$$1$
$321$$(1,2),(1,3),(2,3)$$3$$\{1,2\}$$3$

$132$ では $\operatorname{inv}=1$、$\operatorname{maj}=2$ で値は違うが、どちらの統計量でも値 $0,1,2,3$ をとる置換は $1,2,2,1$ 個で、分布は $[3]_q!=1+2q+2q^2+q^3$ に一致する。thm-inv-maj により、$S_4$ でも主要指数の分布は転倒数と同じ $(1,3,5,6,5,3,1)$ である。

2 つの並びの距離

転倒数は、2 つの並びがどれだけ食い違っているかを測る量にもなる。

並びの食い違いの個数

$\sigma,\tau\in S_n$ について、$\{1,\dots,n\}$ の 2 元部分集合 $\{i,j\}$ で $(\sigma(i)-\sigma(j))(\tau(i)-\tau(j))< 0$ となるもの(2 つの並びで大小の順が逆になる組)の個数を $d(\sigma,\tau)$ とする。

  1. $d(\sigma,\tau)=\operatorname{inv}(\tau\sigma^{-1})$ であり、とくに $d(e,\tau)=\operatorname{inv}(\tau)$ である。
  2. $d$ は $S_n$ の上の距離であり、すべての $\rho\in S_n$ について $d(\sigma\rho,\tau\rho)=d(\sigma,\tau)$ を満たす。
2 元部分集合の付け替え

1:$\{i,j\}\mapsto\{\sigma(i),\sigma(j)\}$ は 2 元部分集合全体の上の全単射である。$a=\sigma(i)< b=\sigma(j)$ と書くと、$\{i,j\}$ が食い違うことは $\tau(i)>\tau(j)$、すなわち $\tau\sigma^{-1}(a)>\tau\sigma^{-1}(b)$ と同値であり、これは $(a,b)$ が $\tau\sigma^{-1}$ の転倒であることにほかならない。
2:$d(\sigma,\tau)=d(\tau,\sigma)\ge0$ は定義から明らかで、1 により $d(\sigma,\tau)=0$ は $\tau\sigma^{-1}=e$、すなわち $\sigma=\tau$ と同値である。三角不等式:$\{i,j\}$ が $\sigma$ と $\tau$ で食い違うなら、$\sigma(i)-\sigma(j)$ と $\tau(i)-\tau(j)$ の符号は異なるので、$\rho(i)-\rho(j)$ の符号はそのどちらかと異なる。よって $\{i,j\}$ は $\sigma$ と $\rho$、または $\rho$ と $\tau$ で食い違い、$d(\sigma,\tau)\le d(\sigma,\rho)+d(\rho,\tau)$ である。右からの不変性:$\{i,j\}$ が $\sigma\rho$ と $\tau\rho$ で食い違うことは、$\{\rho(i),\rho(j)\}$ が $\sigma$ と $\tau$ で食い違うことと同値であり、$\{i,j\}\mapsto\{\rho(i),\rho(j)\}$ は全単射である。$\square$

$\sigma(i)$ を「対象 $i$ の順位」と読むと、$d(\sigma,\tau)$ は 2 人の審査員がつけた順位の間で、どちらが上かの判断が分かれる対象の組の数である。機械学習の順位付けの問題では、これを $\binom n2$ で割った量が Kendall-tau 損失と呼ばれている(SSBD14 §17.4)。1 と三角不等式から、$\operatorname{inv}(\sigma\tau)=d(e,\sigma\tau)\le d(e,\tau)+d(\tau,\sigma\tau)=\operatorname{inv}(\tau)+\operatorname{inv}(\sigma)$ が従う。

反例と注意

転倒数について成り立ちそうで成り立たない主張を挙げる。

成り立ちそうな主張反例実際に成り立つこと
$\operatorname{inv}(\sigma\tau)=\operatorname{inv}(\sigma)+\operatorname{inv}(\tau)$$n=2$、$\sigma=\tau=s_1$偶奇の一致と、不等式 $\operatorname{inv}(\sigma\tau)\le\operatorname{inv}(\sigma)+\operatorname{inv}(\tau)$
転倒数は $\sigma$ を互換の積に書くときの最小の個数$(1\ 3)=321\in S_3$隣接互換に限れば最小の個数、互換を任意に使えば最小の個数は $n-\kappa(\sigma)$($\kappa(\sigma)$ は軌道の個数)
各 $\sigma$ で $\operatorname{maj}(\sigma)=\operatorname{inv}(\sigma)$$132\in S_3$分布の一致(thm-inv-maj)
降下の個数も転倒数と同じ分布をもつ$S_3$降下の位置の和(主要指数)なら同じ分布
$d$ は左からの積でも不変:$d(\rho\sigma,\rho\tau)=d(\sigma,\tau)$$n=3$、$\sigma=e$、$\tau=s_1$、$\rho=(2\ 3)$右からの積での不変性(prop-inv-kendall の 2)
表の反例の確かめ
確かめを開く

1 行目:$s_1=21$ は $\operatorname{inv}(s_1)=1$ だが、$s_1s_1=e$ で $\operatorname{inv}(e)=0\ne2$ である。偶奇は $0\equiv2\pmod 2$ で一致し(置換の符号 の定理「符号準同型」)、不等式は上の段落で示した。

2 行目:$(1\ 3)$ の並びは $321$ で、ex-inv-small により転倒数は $3$ だが、それ自身が 1 個の互換である。互換を任意に使うときの最小の個数が $n-\kappa(\sigma)$ であることは 互換 の定理「互換の個数の下限と偶奇」にあり、ここでは $3-2=1$ である。隣接互換に限ると $(1\ 3)=s_1s_2s_1$ の 3 個が最小である(置換の符号 の命題「隣接互換の積への分解」)。

3 行目:ex-inv-maj-small の表のとおり、$132$ は $\operatorname{inv}=1$、$\operatorname{maj}=2$ である。

4 行目:降下の個数を数えると、$123$ が $0$、$132$・$213$・$231$・$312$ が $1$、$321$ が $2$ で、分布は $(1,4,1)$ である。転倒数の分布 $(1,2,2,1)$ とは値の範囲から異なる。

5 行目:$d(e,s_1)=\operatorname{inv}(s_1)=1$ である。$\rho=(2\ 3)$ について $\rho s_1\rho^{-1}=(1\ 3)$ なので、prop-inv-kendall の 1 により $d(\rho,\rho s_1)=\operatorname{inv}(\rho s_1\rho^{-1})=\operatorname{inv}((1\ 3))=3\ne1$ である。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する