置換の下降数と減少数 - フィボナッチ・フリーク

置換には興味深い性質がたくさんあります。ここではその一つを紹介します。

$\{1,2,\cdots,n\}$ 上の置換の全体を $S_n$ と書きます。 $\sigma\in S_n$ に対し、その下降数を $\sigma(i)\gt\sigma(i+1)$ なる $i$ の総数 $(1\leq i\leq n-1)$ と定めます。例えば $\sigma=\begin{pmatrix} 1~2~3~4~5\\2~4~3~5~1\end{pmatrix}$ という置換には $4\gt 3$ と $5\gt 1$ の2箇所に「下降」があるため、下降数は $2$ です。

また、置換 $\sigma$ の減少数を $\sigma(i)\lt i$ なる $i$ の総数 $(1\leq i \leq n)$ と定めます。上の例では減少数は1です。実はこれらには次の関係があります。

定理. $1\leq k \leq n-1$ とする。 $S_n$ の元のうち下降数が $k$ のものと減少数が $k$ のものの個数は等しい。

この定理は、下降数が $k$ の置換と減少数が $k$ の置換の間に1対1の対応を与えることで証明できます。証明の鍵となるのは次の性質です。

命題. 任意の置換はいくつかの交わらない巡回置換の積にただ一通りに表せる。

このことは置換でそれぞれの数がどこに移るかを追跡することでわかります。例えば上に挙げた例 $\sigma=\begin{pmatrix} 1~2~3~4~5\\2~4~3~5~1\end{pmatrix}$ なら、 $1$ は $2$ に、 $2$ は $4$ に、 $4$ は $5$ に、 $5$ は $1$ に移るため、ここに $(1245)$ という巡回置換があります。 $3$ は動かないので $1$ 元の巡回置換と見なせば

$\sigma=(1245)(3)$

と表せます。
それでは定理を証明してみましょう。

定理の証明. 以下のように写像 $f:S_n\to S_n$ を定める。 $\sigma\in S_n$ を

$\sigma=(a_1^{(1)}a_2^{(1)}\cdots a_{l_1}^{(1)})(a_1^{(2)}a_2^{(2)}\cdots a_{l_2}^{(2)})\cdots(a_1^{(m)}a_2^{(m)}\cdots a_{l_m}^{(m)})$

と交わらない巡回置換の積に書く。この書き方には任意性があるが、 $a_{l_j}^{(j)}=\underset{i}{\mathop{\rm min}}\{a_i^{(j)}\}$ かつ $a_{l_1}^{(1)}\lt a_{l_2}^{(2)}\lt\cdots\lt a_{l_m}^{(m)}$ (各巡回置換に含まれる最小元が最も右側にあり、それらは小さい順に並んでいる)という条件を付けると唯一通りに定まる。このとき $f(\sigma)$ を

\begin{pmatrix}1&2&\cdots&l_1&l_1+1&\cdots&n\\a_1^{(1)}&a_2^{(1)}&\cdots&a_{l_1}^{(1)}&a_1^{(2)}&\cdots&a_{l_m}^{(m)}\end{pmatrix}

と定める。これは全単射である。実際、置換の表示を左から見て $1$ が現れる所までを括弧で括り、次にそれより右側の最小元が現れる所までを括弧で括り…と繰り返すことで逆写像が構成できる。
あとは $f$ が減少数 $k$ の置換を下降数 $k$ の置換に移すことを見ればよい。 $\sigma$ の減少数は定義から $a_i^{(j)}\gt a_{i+1}^{(j)}$ なる組 $(i,j)$ の総数に等しい。ここで作り方から常に $a_{l_j}^{(j)}\lt a_1^{(j)}$ なので巡回置換の端どうしは考えなくてよいことに注意する。さらに常に $a_{l_j}^{(j)}\lt a_1^{(j+1)}$ なので、この総数は $f(\sigma)$ の下降数に等しい。 $\Box$

$S_n$ の元のうち下降数が $k$ であるものの個数はEuler数と呼ばれており、様々な性質が知られています。それについてはまた改めて記事を書こうと思います。