サイクル数とそのq-拡張 - 数学の命題示しました

置換をサイクル分解したとき現れるサイクルの数をサイクル数という．置換 $\sigma\in\mathfrak{S}_n$ のサイクル数を ${\rm cyc}(\sigma)$ とかく．この統計量 ${\rm cyc}$ について，次の式が知られいてる．
(式 1)　 $\displaystyle\label{eq:sum_cycle}\sum_{\sigma\in\mathfrak{S}_n}(a+1)^{{\rm cyc}(\sigma)}=(a+1)_n$
但し， $a$ は形式的な変数であり， $(a+1)_n\triangleq (a+1)(a+2)\cdots(a+n)$ とする．

(式 1)についてより詳しくは，Stanley (R. P. Stanley, Enumerative combinatorics, vol. 1, second edition, p. 33, 2011)などを見よ．
$a$ が非負整数のとき，式 (1)の左辺は，置換をサイクル分解してサイクルごとに色 $\{0,\ldots,a\}$ を決めたもの全体の和だと思うことができる．つまり，「色付き置換」の集合 $\mathcal{S}_n^{(a)}$ を
$\displaystyle\mathcal{S}_n^{(a)}\triangleq\left\{(\tau,f)\mid \tau\in\mathfrak{S}_n,\ f\colon (\tau {\rm のサイクルの集合}) \to \{0,\ldots,a\}\right\}$
と定めれば，式 (1)は
(式 2)　 $\displaystyle\label{eq:sum_cycle_modified}\sum_{\sigma\in\mathcal{S}_n^{(a)}}1=(a+1)_n$
とかける．

本稿では，式 (2)を $q$ -拡張する以下の式を導く．

(式 3)　 $\displaystyle\label{eq:q_sum_cycle}\sum_{\sigma\in\mathcal{S}_n^{(a)}}w_q(\sigma)=\frac{(q^{a+1};q)_n}{(1-q)^n},\qquad w_q(\sigma)\to 1\ (q\to 1)$
但し $(q^{a+1};q)_n\triangleq (1-q^{a+1})(1-q^{a+2})\cdots(1-q^{a+n})$ である．式 (3)中の $w_q\colon \mathcal{S}_n^{(a)}\to\mathbb{Z}[q]$ は「色付き置換」の重みである．この重み $w_q$ を適切に定める必要がある．
式 (3)は， $q\to 1$ の極限で式 (2)と一致する．

式 (3)において $a=0$ とすると，左辺は通常の置換についての和になり，右辺は $q$ -階乗 $[n]_q!$ となる．この意味でサイクル数は，Mahonianの拡張だと思うことができる．(転倒数とかMajor indexとかと同分布な統計量を総称してMahonianというらしい．)

まず，そもそも $q$ -拡張する前の式 (2)をどうやって全単射的に示すのかを確かめる． $q$ -拡張のための重み $w_q$ は，その全単射から自ずと導かれる．

式 (2)を示す全単射

命題
次の全単射 $\varphi$ を構成する．
$\varphi\colon\mathcal{S}_{n}^{(a)}\times\{0,\ldots, a+n\}\to\mathcal{S}_{n+1}^{(a)}$

構成
$\sigma\in\mathcal{S}_n^{(a)}$ と， $i\in\{0,\ldots,a+n\}$ をとったとき， $\sigma'\in\mathcal{S}_{n+1}^{(a)}$ を次のように定める．

$0\leq i\leq a$ のとき．色 $i$ の新しいサイクル $(n+1)$ を $\sigma$ に追加し，それを $\sigma'$ とする．
$a+1\leq i$ のとき． $j=i-a$ とすると $j\in\{1,\ldots,n\}$ である． $\sigma$ には，数 $j$ を含むサイクルが存在する．そのサイクルの数 $j$ の前に数 $n+1$ を追加して $\sigma'$ とする．

これにより， $\varphi(\sigma,i)\triangleq\sigma'$ と定めれば， $\varphi$ は全単射となる．
（構成終わり．）

この全単射 $\varphi$ が存在するので，式 (2)つまり $|S_n^{(a)}|=(a+1)_n$ が $n$ に関する帰納法で示される．

$q$ -拡張

$\sigma\in\mathcal{S}_n^{(a)},i\in\{0,\ldots,a+n\},\sigma'\in\mathcal{S}_{n+1}^{(a)}$ として
$\varphi(\sigma,i)=\sigma'$ とする．このとき，
(式 4)　 $w_q(\sigma')=w_q(\sigma)q^i$
が成り立つような重み $w_q\colon \mathcal{S}_n^{(a)}\to\mathbb{Z}[q]$ を決めれば，
$\displaystyle\sum_{\sigma\in \mathcal{S}_{n+1}^{(a)}}w_q(\sigma)=(1+q+\cdots+q^{a+n})\sum_{\sigma\in \mathcal{S}_{n}^{(a)}}w_q(\sigma)$
となるから，式 (3)が成り立つ．

重み $w_q$ は次のように定めればよい． $\sigma=(\tau,f)\in\mathcal{S}_n^{(a)}$ に含まれるサイクルごとに重みを定め， $\sigma$ の重みはサイクルの重みの積とする．
$\sigma$ のあるサイクルを $c=(c_1\ c_2\ \cdots\ c_r)$ とする．サイクルの要素 $c_1,\ldots,c_r$ にそれぞれ重みを割り当て，サイクルの重みはそれらの重みの積とする．
まず，最小要素 $\min\{c_1,\ldots,c_r\}$ の重みは，サイクルの色 $f(c)$ を用いて $q^{f(c)}$ とする．
それ以外の要素 $c_i$ の重みは，サイクルにおいて $c_i$ の次に初めて現れる $c_i$ 未満の要素を $c_k$ としたとき， $q^{c_k+a}$ と定める．

以下は重みの決め方を説明する図である．赤い色で書いたのが，各サイクル $c$ の色 $f(c)$ ，数字の脇に青い色で書いてある数字が，その要素の重み (qの青い数字乗という意味)．
f:id:iwalion:20200923070849p:plain

こうして決めた重み $w_q$ は，式 (4)を満たすことが，全単射 $\varphi$ の作り方から分かる．

別の方法による $q$ -拡張

Q. PanとJ. Zeng (Q. Pan, J. Zeng, Combinatorics of (q,y)-Laguerre polynomials and their moments. Seminaire Lotharingien de Combinatoire, B81e, 20pp. 2020)は，以下のような全単射
$\displaystyle\label{eq:bij2}\theta\colon\mathfrak{S}_n\times \binom{\{1,\ldots,n+a\}}{n}\to\mathcal{S}_{n}^{(a)}$
をもとに重み $w_q$ を定めることで，式 (3)を導いている．Q. PanとJ. Zengの重みと，本記事で紹介した重みとの関連性は，よく知らない．

式 (2)を示す全単射

-拡張

別の方法による-拡張

$q$ -拡張

別の方法による $q$ -拡張