置換のMajor indexと転倒数の等分布性 - 数学の命題示しました

major indexとは置換の統計量つまり，対称群から非負整数への写像の一種 ${\rm maj}\colon \mathfrak{S}_n\to \mathbb{N}_0$ である．
major indexは，以前このブログでも紹介した「置換の転倒数」と等分布であることが知られている．
つまり，以下の母関数の式が成立する．（式 (1)とする．）
$\displaystyle\sum_{\sigma\in\mathfrak{S}_n}q^{{\rm maj}(\sigma)}=\prod_{k=1}^n\frac{1-q^k}{1-q}$ .

（参考：R. P. Stanley, Enumerative combinatorics, vol. 1, second edition, p. 41, 2011）

本記事では式 (1)を証明する．
証明はD. Foataによる，重みを保つ全単射 ${\rm maj}(\sigma)={\rm inv}(\varphi(\sigma))$ を構成する方法が有名だが，今回は転倒数との関連は考えず直接証明してみる．
（参考：D. Foata, On the Netto Inversion Number of a Sequence, Proceedings of the American
Mathematical Society 19, pp. 236-240, 1968.）

定義 (減少集合，major index)
置換 $\sigma\in\mathfrak{S}_n$ に対して，その減少集合 $D(\sigma)$ を
$D(\sigma)\triangleq \{i\mid \sigma(i)>\sigma(i+1)\}\subseteq\{0,\ldots,n-1\}$
と定める．

置換 $\sigma$ のmajor indexを，
$\displaystyle{\rm maj}(\sigma)\triangleq\sum_{i\in D(\sigma)}i$
と定める．

例
置換 $\sigma\in\mathfrak{S}_n$ を $\sigma(1)\cdots\sigma(n)$ とかく．
$\sigma=47523816\in\mathfrak{S}_8$ に対して，
$D(\sigma)=\{2,3,6\}であり, {\rm maj}(\sigma)=2+3+6=11$ である．

major indexと転倒数の等分布性

式 (1)を証明する．
まず，major indexに関する情報を保ちつつ置換を置換に写す全単射を構成する．この全単射は式 (1)の証明の核心となる．

命題
$0\leq k\leq n-1$ のとき，全単射
$\displaystyle\varphi\colon\{\sigma\in\mathfrak{S}_n\mid \sigma(n)=k\}\to\{\sigma\in\mathfrak{S}_n\mid \sigma(n)=k+1\}$
が存在して，
$\displaystyle{\rm maj}\left(\varphi(\sigma)\right)={\rm maj}\left(\sigma\right)+1$
を満たす．

証明
置換の行列表記を用いる．
ここでいう置換の行列表記とは， $\sigma(i)=j$ のとき $a_{n-j+1,i}=1$ ，そうでないとき $a_{n-j+1,i}=0$ によって $n\times n$ 行列 $A$ を定義し，そのような行列で置換を表すことである．
行列の一番下の行をとり，一番上の行の上に乗せる写像を $\varphi$ と定義する．
つまり，下図のように定義する．
f:id:iwalion:20200913050726p:plain

この写像は明らかに可逆である．
また，この写像を当てたあとは，当てる前よりmajor indexが1増える．
なぜなら， $\sigma(r)=1$ なる $r\in\{1,\ldots,n\}$ が唯一つ存在し， $(\varphi(\sigma))(r)=n$ となるが，

$r\neq 1$ ならば， $r-1\in D(\sigma)$ であり， $D(\varphi(\sigma))=(D(\sigma)\setminus\{r-1\})\cup\{r\}$ が成立する．
$r=1$ ならば， $1\notin D(\sigma)$ であり， $D(\varphi(\sigma))=D(\sigma)\sqcup\{1\}$ が成立する．

よって，いずれの場合でもmajor indexが1増えるのである．
（証明終わり．）

命題
母関数の式 (1)が成立する．
式 (1)の再掲：
$\displaystyle\sum_{\sigma\in\mathfrak{S}_n}q^{{\rm maj}(\sigma)}=\prod_{k=1}^n\frac{1-q^k}{1-q}$ .

証明
置換 $\sigma\in\mathfrak{S}_n$ に対して，置換 $\sigma'\in \mathfrak{S}_{n+1}$ を，行列表記を用いて
f:id:iwalion:20200913051927p:plain
と定める．このとき ${\rm maj}(\sigma)={\rm maj}(\sigma')$ である．
集合 $U_{\sigma}\subseteq\mathfrak{S}_{n+1}$ を
$\displaystyle U_{\sigma}\triangleq\left\{\sigma',\varphi(\sigma'),\varphi^2(\sigma'),\ldots,\varphi^{n}(\sigma')\right\}$
と定める．
すると集合の等式
$\displaystyle \mathfrak{S}_{n+1}=\bigsqcup_{\sigma\in\mathfrak{S}_n}U_{\sigma}$
が成立する．（写像 $\varphi$ は全単射なので，右辺の和は非交差である．）

以下，式 (1)を $n$ に関する帰納法で示す．上で示した集合の式から，
$\displaystyle\sum_{\sigma\in\mathfrak{S}_{n+1}}q^{{\rm maj}(\sigma)}=\sum_{\sigma\in\mathfrak{S}_{n}}\left(q^{{\rm maj}(\sigma)}+q^{{\rm maj}(\varphi(\sigma))}+q^{{\rm maj}(\varphi^2(\sigma))}+\cdots+q^{{\rm maj}(\varphi^n(\sigma))}\right)$

しかし ${\rm maj}(\varphi(\sigma))={\rm maj}(\sigma)+1$ であったから，
$\displaystyle =\sum_{\sigma\in\mathfrak{S}_{n}}q^{{\rm maj}(\sigma)}q^{0+1+2+\ldots+n}$
$\displaystyle =\frac{1-q^{n+1}}{1-q}\sum_{\sigma\in\mathfrak{S}_{n}}q^{{\rm maj}(\sigma)}$
帰納法の仮定から
$\displaystyle =\prod_{k=1}^{n+1}\frac{1-q^{k}}{1-q}.$
（証明終わり．）