置換の転倒数の母関数 - 数学の命題示しました

本稿では置換の転倒数の母関数が綺麗という側面から転倒数に触れていくが，転倒数という概念自体は行列式の性質を証明するために有用であったりとか (岩瀬順一，岩瀬順一の「授業をする際のヒント --- 数学編」，転倒数を利用し、互換の積への分解を飛ばして行列式を導入する)，置換の集合に距離を入れるために使ったりするらしい (萩原学，ポストモダン符号理論としてのネットワーク，置換，形式化３：置換符号，応用数理 26(2), 27-32, 2016)．
置換の転倒数の母関数に関する参考文献は，(Stanley，Enumerative Combinatorics volume 1 second edition，p. 36，2011)を参照．

転倒数に関する分かりやすい動画は，龍孫江の「群論：置換の転倒数」https://www.youtube.com/watch?v=LXlXGWGmItg&feature=youtu.beを参照せよ．

転倒数の母関数

定義 (転倒数)
$n$ 文字の置換 $\sigma\in\mathfrak{S}_n$ に対して，非負整数 ${\rm inv}(\sigma)$ を
$\displaystyle{\rm inv}(\sigma)\triangleq\#\left\{(i,j)\mid i\lt j,　 \sigma(i)\gt\sigma(j)\right\}$
と定め， $\sigma$ の転倒数という．

以下のように，転倒数の母関数は積表示を持つことが知られている．
$\displaystyle \sum_{\sigma\in\mathfrak{S}_n}q^{{\rm inv}(\sigma)}=\prod_{k=1}^n\frac{1-q^k}{1-q}$
(式1とする．)
本稿ではこの式 (1)の全単射的証明をしたあと，母関数の精密化を試みる．
式 (1)で表される多項式は「 $n$ の $q$ -階乗」と呼ばれ， $[n]$ $_q!$ と書かれることがある．

式 (1)の証明

転倒数に関する情報を保ちつつ $n$ 文字の置換を $n+1$ 文字の置換にうつす以下の全単射が構成できる．

定理
全単射 $\varphi\colon\mathfrak{S}_n\times\{0,\ldots,n\}\to\mathfrak{S}_{n+1}$ で，任意の $(\sigma,i)\in\mathfrak{S}_n\times\{0,\ldots,n\}$ に対して
${\rm inv}(\varphi(\sigma,i))={\rm inv}(\sigma)+i$ なるものが存在する．

証明
$(\sigma,i)\in\mathfrak{S}_n\times\{0,\ldots,n\}$ とする．
置換 $\sigma$ を長さ $n$ の列 $(\sigma(1),\ldots,\sigma(n))$ で表す．
文字 $n+1$ を，列 $(\sigma(1),\ldots,\sigma(n))$ の右から $i$ 番目に入れて長さ $n+1$ の列
$\displaystyle\left(\sigma(1),\ldots,\sigma(n-i),n+1,\sigma(n-i+1),\ldots,\sigma(n)\right)$
を作る．
こうしてできる列は $n+1$ 文字の置換を表すから，それを $\varphi(\sigma,i)$ とする．
この対応は可逆である．なぜならば置換 $\varphi(\sigma,i)$ において
文字 $n+1$ がどこに有るかを見てそれを抜けば数 $i$ と置換 $\sigma$ が分かるからである．
置換 $\varphi(\sigma,i)$ の転倒数は， $\sigma$ の転倒数に比べて，文字 $n+1$ の右にある $i$ 個の数の分増えるので，
${\rm inv}(\varphi(\sigma,i))={\rm inv}(\sigma)+i$ が成立する．
(証明終わり．)

定理
転倒数の母関数の式(1)が成立する．

証明
$n$ に関する帰納法による．上で構成した全単射
$\varphi\colon\mathfrak{S}_{n}\times\{0,\dots,n\}\to\mathfrak{S}_{n+1}$ により
$\displaystyle\sum_{\sigma\in\mathfrak{S}_{n+1}}q^{{\rm inv}(\sigma)}=\sum_{\sigma\in\mathfrak{S}_{n}}\sum_{i=0}^{n}q^{{\rm inv}(\varphi(\sigma,i))}=\sum_{\sigma\in\mathfrak{S}_{n}}q^{{\rm inv}(\sigma)}\sum_{i=0}^{n}q^{i}$

帰納法の仮定から
$\displaystyle=\left(\prod_{k=1}^n\frac{1-q^k}{1-q}\right)\sum_{i=0}^{n}q^{i}=\prod_{k=1}^{n+1}\frac{1-q^k}{1-q}.$
(証明終わり．)

母関数を精密化してみる

自然数 $k$ に対して $k$ -転倒数 ${\rm inv}_k$ を以下で定義する．
$\displaystyle{\rm inv}_k(\sigma) \triangleq \#\left\{(i,j)\mid i\lt j,\ \sigma(i)\gt\sigma(j),\ \sigma(i)=k\right\}．$
置換 $\sigma\in\mathfrak{S}_n$ の $k$ -転倒数 ${\rm inv}_k$ の和は通常の転倒数に一致する．すなわち，
$\displaystyle{\rm inv}_1(\sigma)+\cdots+{\rm inv}_n(\sigma)={\rm inv}(\sigma),\quad \sigma\in\mathfrak{S}_n.$

式 (1)を精密化する以下の式が成立する．

定理
$k$ -転倒数の母関数の式
$\displaystyle\sum_{\sigma\in\mathfrak{S}_n}q_1^{{\rm inv}_1(\sigma)}q_2^{{\rm inv}_2(\sigma)}\cdots q_n^{{\rm inv}_n(\sigma)}=\prod_{k=1}^n\frac{1-q_k^k}{1-q_k}$
が成立する．

証明
全単射 $\varphi\colon\mathfrak{S}_{n}\times\{0,\dots,n\}\to\mathfrak{S}_{n+1}$ がもつ以下の性質を用いる．

すなわち任意の $(\sigma,i)\in \mathfrak{S}_{n}\times\{0,\dots,n\}$ に対して
$\displaystyle{\rm inv}_{n+1}(\varphi(\sigma,i))=i,$
$\displaystyle{\rm inv}_{k}(\varphi(\sigma,i))={\rm inv}_k(\sigma),\quad (k\leq n)$
である．証明は式 (1)の証明とほとんど同じである．
（証明終わり．)