フィボナッチ・フリーク

数学の小ネタ集。

Fibonacci Freak

置換の下降数と減少数

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

\{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 35\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}なら、12に、24に、45に、51に移るため、ここに(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数と呼ばれており、様々な性質が知られています。それについてはまた改めて記事を書こうと思います。