desとexcの等分布性の全単射による証明
降下集合を$\mathrm{Des}(\sigma):=\{1\leq i\leq n;a_i>a_{i+1}\}$として, $\mathrm{des}(\sigma):=|\mathrm{Des}(\sigma)|$を降下数といい, 降下集合の元を降下という. 超過集合を$\mathrm{Exc}(\sigma):=\{1\leq i\leq n;i<\sigma(i)\}$として, $\mathrm{exc}(\sigma):=|\mathrm{Exc}(\sigma)|$を超過数といい, 超過集合の元を超過という. 前回の記事 で以下の定理を示した.
\begin{align} \sum_{\sigma\in\mathfrak{S}_n}t^{\mathrm{des}(\sigma)+1}&=\sum_{\sigma\in\mathfrak{S}_n}t^{\mathrm{exc}(\sigma)+1} \end{align}
これは, 降下数が$k$である順列の個数と超過数が$k$である順列の個数が等しいことを意味している. よって, 直接全単射を構成するような証明が望まれる. そのような証明はD. Foataによって最初に発見された.
$[n]:=\{1,2\dots,n\}$とする.
$[n]$の順列$\sigma$をいくつかのサイクルの積に分解することを考える.
\begin{align}
\sigma=(c_{11}c_{12}\cdots c_{1l_1})(c_{21}c_{22}\cdots c_{2l_2})\cdots(c_{m1}c_{m2}\cdots c_{ml_m})
\end{align}
上のようなサイクルによる分解において, 各$i$に対して, $c_{i1},\dots,c_{il_i}$の中で$c_{i1}$が最も大きく$i< j$ならば$c_{i1}< c_{j1}$となるように並び替えられているとする. このとき, 各$i$に対して$c_{i2}$から$c_{il_i}$までを逆向きにして並べたもの
\begin{align}
\psi(\sigma):=c_{11}c_{1l_1}\cdots c_{12}c_{21}c_{2l_2}\cdots c_{22}\cdots c_{m1}c_{ml_m}\cdots c_{m2}
\end{align}
によって写像$\psi$を定義する.
$\psi(\sigma)$が与えられたとき, $c_{i1}$より後ろ側にあって, $c_{i1}$より真に大きいものとして$c_{(i+1)1}$が決まり, そこから$\sigma$が復元できる. よって$\psi$は全単射である.
以下が示されれば, 定理1が従う.
任意の順列$\sigma$に対して, $\mathrm{exc}(\sigma)=\mathrm{des}(\psi(\sigma))$が成り立つ.
$\sigma$のサイクルの一つを$c_1\cdots c_m$とすると, $c_{m+1}$としてそのサイクルに含まれる超過数は$c_i< c_{i+1}$であるような$i$の個数である. よって, それは$c_1$を最大値として, $c_1c_m\cdots c_2$の降下数によって与えられることが分かり, $\psi(\sigma)$の定義において常に$c_{il_i}< c_{(i+1)1}$であるから, これらをつなげたものである$\psi(\sigma)$の降下数は$\sigma$の超過数に等しい.
上の議論について, 一つ例を挙げる. $\sigma=526314$とする. $\sigma$をサイクル分解すると,
\begin{align}
\sigma=(15)(2)(364)
\end{align}
となる. $(15)$の部分の超過数は$1<5$だけが成り立つから$1$である. $(2)$の部分の超過数は$0$. $(364)$の部分の超過数は$3<6$だけが成り立つから$1$である. よって合わせて$2$である. $\psi$の定義におけるサイクル分解の並び替えを行うと,
\begin{align}
\sigma=(2)(51)(643)
\end{align}
となる.
\begin{align}
\psi(\sigma)=251634
\end{align}
である. これの降下数を求めてみると, $5>1, 6>3$より$2$である. ここで両方の計算を行ったが, 比較して数え上げられている部分に着目すると, ともに$1<5, 3<6$である. このように, $\sigma$の超過がちょうど$\psi(\sigma)$の降下に対応するように上手く$\psi$が定義されているのである.
この記事を高評価した人
この記事に送られたバッジ
投稿者
