転倒数とmajor indexの等分布性
$n$次対称群の元$\sigma$を$[n]:=\{1,2,\dots,n\}$の順列$\sigma(1)\sigma(2)\cdots\sigma(n)$と同一視する.
$[n]$の順列$\sigma=a_1\cdots a_n$に対し, $1\leq i< j\leq n$かつ$a_i>a_j$となるような組$(i,j)$を$\sigma$の転倒という. その個数を$\sigma$の転倒数といい, $\inv(\sigma)$で表す.
$[n]$の順列$\sigma=a_1\cdots a_n$に対して, その降下集合を$\mathrm{Des}(\sigma):=\{1\leq i< n;a_i>a_{i+1}\}$と定義する.
\begin{align}
\maj(\sigma)=\sum_{i\in\mathrm{Des}(\sigma)} i
\end{align}
によって定義される$\maj(\sigma)$を$\sigma$のmajor indexという. $\mathrm{des}(\sigma):=|\mathrm{Des}(\sigma)|$を降下数という.
次は転倒数とmajor indexの等分布性を表すMacMahonの定理である.
$1\leq n$に対し,
\begin{align}
\sum_{\sigma\in\mathfrak{S}_n}q^{\inv(\sigma)}=\sum_{\sigma\in\mathfrak{S}_n}q^{\maj(\sigma)}=\prod_{k=1}^{n}\frac{1-q^k}{1-q}
\end{align}
が成り立つ.
二つに分けて証明する.
$1\leq n$に対し,
\begin{align}
\sum_{\sigma\in\mathfrak{S}_n}q^{\inv(\sigma)}&=\prod_{k=1}^{n}\frac{1-q^k}{1-q}
\end{align}
が成り立つ.
$n$に関する記法により示す. $n=1$のときは明らかに成り立つ. $n-1$まで題意が成立しているとする. $[n-1]$の順列$\sigma=a_1\cdots a_{n-1}$に$n$を挿入して$[n]$の順列を得る方法は$n$通りある. $n$を末尾に挿入した順列の転倒数は$\inv(\sigma)$であり, $1\leq i\leq n-1$に対し, $n$を$a_i$の$1$つ前に挿入した順列の転倒数は$\inv(\sigma)+n-i$である. よって$[n-1]$の各順列と各$0\leq i\leq n-1$に対して, $\sigma$に$n$を挿入した順列で$\inv(\sigma)+i$を転倒数に持つものが$1$つずつ得られるから,
\begin{align}
\sum_{\sigma\in\mathfrak{S}_n}q^{\inv(\sigma)}&=(1+q+\cdots+q^{n-1})\sum_{\sigma\in\mathfrak{S}_{n-1}}q^{\inv(\sigma)}\\
&=\frac{1-q^n}{1-q}\prod_{k=1}^{n-1}\frac{1-q^k}{1-q}\\
&=\prod_{k=1}^n\frac{1-q^k}{1-q}
\end{align}
となって示される.
$1\leq n$に対し,
\begin{align}
\sum_{\sigma\in\mathfrak{S}_n}q^{\maj(\sigma)}&=\prod_{k=1}^{n}\frac{1-q^k}{1-q}
\end{align}
が成り立つ.
$n$に関する帰納法で示す. $n=1$のときは明らかに成り立つ. $n-1$まで題意が成立しているとする. $[n-1]$の順列$\sigma=a_1\cdots a_{n-1}$に$n$を挿入して$[n]$の順列を得る方法は$n$通りある. $m=\mathrm{des}(\sigma)$とする. $n$を先頭に挿入した順列のmajor indexは$\maj(\sigma)+m+1$に等しく, $n$を末尾に挿入した順列のmajor indexは$\maj(\sigma)$に等しい. 降下集合の元を$i_1<\cdots< i_m$と書く. $1\leq j\leq m$に対し, $a_{i_j}$の$1$つ後ろに$n$を挿入した順列の降下集合は
\begin{align}
i_1<\cdots< i_{j-1}< i_j+1<\cdots< i_m+1
\end{align}
と表せるから, そのmajor indexは$\maj(\sigma)+m-j+1$である. 次に,
\begin{align}
[n-1]-\mathrm{Des}(\sigma)=\{b_1,\dots,b_{n-1-m}\},\qquad b_1<\cdots< b_{n-1-m}
\end{align}
とする.$1\leq j\leq n-m-2$に対し, $a_{b_j}$の1つ後ろに$n$を挿入した順列の降下集合は, ある$1\leq k\leq m+1$を用いて
\begin{align}
i_1<\cdots< i_{k-1}< b_j+1< i_k+1<\cdots< i_m+1
\end{align}
と表すことができる. $b_j$の前には$k-1$個の降下集合の元があるから, $b_j=j+k-1$である. よってそのmajor indexは$\maj(\sigma)+(b_j+1)+(m-k+1)=\maj(\sigma)+m+j+1$で与えられる. よって, $\sigma$に$n$を挿入した順列で$\maj(\sigma)+i$をmajor indexに持つものが1つずつ得られるから,
\begin{align}
\sum_{\sigma\in\mathfrak{S}_n}q^{\maj(\sigma)}&=(1+q+\cdots+q^{n-1})\sum_{\sigma\in\mathfrak{S}_{n-1}}q^{\maj(\sigma)}\\
&=\frac{1-q^n}{1-q}\prod_{k=1}^{n-1}\frac{1-q^k}{1-q}\\
&=\prod_{k=1}^n\frac{1-q^k}{1-q}
\end{align}
となって示される.
これらから定理1が従う.
この記事を高評価した人
この記事に送られたバッジ
投稿者
