文献あり

major indexによるq-二項係数

192

正方格子路にmajor indexと呼ばれる統計量を定義し，それに関する母関数が $q$ -二項係数になることを示す．
本記事の元ネタの文献 [1]によると，これはもともと MacMahon の仕事らしい．

major indexによる

q

-二項係数

$\begin{array}{r} \sum_{ω \in L (n, r)} q^{m a j (ω)} = {(\binom{n + r}{r})}_{q} \end{array}$
但し $L (n, r)$ は $(0, 0)$ から $(n, r)$ まで，ステップ $(1, 0)$ と $(0, 1)$ を使って行くパス (注：そういうのを正方格子路という)．

元ネタ文献 [1]の練習問題6.4では， $area (ω) = k$ な正方格子路 $ω$ を $maj (ω^{'}) = k$ な正方格子路 $ω^{'}$ にうつす全単射を構成して示してたが，以下では趣を変えてパスカルの三角形を経由して示してみる．

ちなみに，統計量 $maj$ の面白いところは，正方格子路の特殊な場合であるDyck路を $maj$ で数えると，以下のように積で書けるところである [1, 定理6.10]．

major indexによるCatalan数の

q

-拡張

$\begin{array}{r} \sum_{ω \in D y c k (n)} q^{m a j (ω)} = \frac{1}{[n + 1]_{q}} {(\binom{2 n}{n})}_{q} \end{array}$

本稿を通じて以下の $q$ -類似を表す記号を使う．
$\begin{aligned} [n]_{q} & ≜ 1 + q + \dots + q^{n - 1}, \\ [n]_{q}! & ≜ [1]_{q} [2]_{q} \dots [n]_{q}, \\ {(\binom{n + r}{r})}_{q} & ≜ \frac{[n + r]_{q}!}{[n]_{q}! [r]_{q}!} . \end{aligned}$

$q$ -二項係数が満たす以下の性質は，もう知ってるとする．（計算すればわかる．）
この式については例えば [2]にも書いてある．

q

-二項係数の対称性

$\begin{array}{r} {(\binom{n + r}{r})}_{q} = {(\binom{n + r}{n})}_{q} \end{array}$

q

-パスカルの三角形

$\begin{array}{r} {(\binom{n + r}{r})}_{q} = q^{n} {(\binom{n + r - 1}{r - 1})}_{q} + {(\binom{n + r - 1}{r})}_{q} \end{array}$

準備

major index

全順序集合 $S$ の語 (注：語とは元の有限列のことだと思ってよい) $ω = ω_{1} ω_{2} \dots ω_{r} (ω_{i} \in S)$ に対して，その降下点集合 (set of descents) $D (ω)$ を
$\begin{array}{r} D (ω) ≜ {i ∣ ω_{i} > ω_{i + 1}} \end{array}$
と定める．そして，語 $ω$ のmajor index $m a j (ω)$ を，
$\begin{array}{r} m a j (ω) ≜ \sum_{i \in D (ω)} i \end{array}$
と定める．

major indexの例1

$S ≜ {1, 2, \dots, 8}$ で $ω = 47523816$ なら， $D (ω) = {2, 3, 6}$ であり $m a j (ω) = 2 + 3 + 6 = 11$ である．

major indexの例2

$S ≜ {A, B} (A > B)$ で $ω = B A B A A B B A B$ なら， $D (ω) = {2, 5, 8}$ であり $m a j (ω) = 15$ である．

正方格子路

次に，正方格子路を定義する．ベクトル $A, B$ を $A ≜ (1, 0)$ ， $B ≜ (0, 1)$ と定める．

点 $(0, 0)$ から $(n, r)$ への正方格子路とは，
語 $ω = ω_{1} \dots ω_{n + r} (ω_{i} \in {A, B})$
で，その総和が
$ω_{1} + \dots + ω_{n + r} = (n, r)$ を満たすものである．
$(0, 0)$ から $(n, r)$ への正方格子路の集合を $L (n, r)$ とかく．

ベクトル $A, B$ の順序関係を $A > B$ と定めることにより，集合 $L (n, r)$ の上の関数 $m a j$ を定義する．

正方格子路の反転操作

正方格子路の集合 $L (n, r)$ の部分集合で，末尾が $A, B$ であるものをそれぞれ
$\begin{array}{r} L_{A} (n, r) ≜ {ω = ω_{1} \dots ω_{n + r} \in L (n, r) ∣ ω_{n + r} = A}, \\ L_{B} (n, r) ≜ {ω = ω_{1} \dots ω_{n + r} \in L (n, r) ∣ ω_{n + r} = B} \end{array}$
と定める．

正方格子路の反転操作．

$ω \in L (n, r)$ に対する操作 $flip$ を， $ω$ に出てくる $A$ と $B$ を，をれぞれ $B$ と $A$ に入れ替える操作と定義する．
すると， $flip$ は $L_{A} (n, r)$ から $L_{B} (r, n)$ への全単射であり，
$ω \in L_{A} (n, r)$ に対して
$\begin{array}{r} maj (flip (ω)) - r = maj (ω) \end{array}$
が成り立つ．

これを示すために，正方格子路を置換として扱う方法を考える．

正方格子路の置換への埋め込み

$(0, 0)$ から $(n, r)$ への正方格子路を $n + r$ 文字の置換へ写す単射
$σ_{∙} : L (n, r) \to S_{n + r}$ をつくる．

$ω = ω_{1} \dots ω_{n + r} \in L (n, r)$ とする．
$ω_{i} = B$ となるような添字 $i$ を，小さい順に $i_{1}, \dots, i_{r}$ とする．
また， $ω_{j} = A$ となるような添字 $j$ を，小さい順に $j_{1}, \dots, j_{n}$ とする．
そして，置換 $σ_{ω} \in S_{n + r}$ を
$\begin{aligned} σ_{ω} (i_{k}) & ≜ k, (k = 1, \dots, r) \\ σ_{ω} (j_{k}) & ≜ r + k, (k = 1, \dots, n) \end{aligned}$
と定める．

例

下記上段の $ω \in L (6, 4)$ に対して，下記下段の $σ_{ω} \in S_{10}$ をえる．
$\begin{array}{r} \begin{array}{ccccccccccc} ω = & A & B & A & B & B & A & A & B & A & A, \\ σ_{ω} = & 5 & 1 & 6 & 2 & 3 & 7 & 8 & 4 & 9 & 10. \end{array} \end{array}$
左にある $B$ から順にラベル $1, 2,, \dots$ をつけて，それが終わったら左にある $A$ から順にラベル $r + 1, r + 2, \dots$ をつけると思ってもよい．絵で描くと以下のような感じになる．
埋め込みの例

この単射は，統計量 $maj$ を保存する．つまり，

$ω \in L (n, r)$ に対して $maj (ω) = maj (σ_{ω})$ .

次に，置換を，majが1大きい別の置換に写す操作を考える．

置換のmajor indexを

1

だけ増やす操作．

${1, \dots, n}$ の置換 $σ = σ_{1} \dots σ_{n} \in S_{n} (σ_{i} \in {1, \dots, n})$ が $σ_{n} \neq 1$ を満たすとし， $σ_{i} = 1 (i < n)$ だとする．
置換 $φ (σ) \in S_{n}$ を
$\begin{array}{r} φ (σ) ≜ (σ_{1} - 1) \dots (σ_{i - 1} - 1) n (σ_{i + 1} - 1) \dots (σ_{n} - 1) \end{array}$
と定める．すると，
$\begin{array}{r} m a j (σ) + 1 = m a j (φ (σ)) \end{array}$
が成立．

言葉で書くと，写像 $φ$ は，置換に出てくる $1$ を $n$ に変えて，それ以外を全部 $- 1$ する写像である．

補題5の証明

もし $i \neq 1$ ならば， $i - 1 \in D (σ), i \notin D (σ)$ であり，
$\begin{array}{r} D (φ (σ)) = (D (σ) ∖ {i - 1}) \cup {i} \end{array}$
が成り立つのでmajor indexが $1$ 増える．
もし $i = 1$ ならば， $1 \notin D (ω)$ であり，
$\begin{array}{r} D (φ (σ)) = D (σ) \cup {1} \end{array}$
なので，この場合もmajor indexが $1$ 増える．

例

$σ = 47523816$ のとき $φ (σ) = 36412785$ .
$D (σ) = {2, 3, 6}, D (φ (σ)) = {2, 3, 7}$ .
補題5の写像!FORMULA[113][1017910466][0]の説明補題5の写像 $φ$ の説明
絵で描くと、写像 $φ$ は、一番下の段を一番上に移動することに相当する。

補題3の証明

$ω \in L_{A} (n, r)$ とし，置換への埋め込み $σ_{ω}$ を考える．
$ω$ の末尾が $A なので，$ この置換 $σ_{ω}$ は，
$\begin{array}{r} φ^{k} (σ_{ω}) (n) \neq 1, (k = 0, \dots, r - 1) \end{array}$
を満たし，写像 $φ$ を $r$ 回当てることができる．
そして， $φ^{r} (σ_{ω})$ は， $flip (ω)$ の埋め込みである．補題5より
$\begin{array}{r} maj (σ_{ω}) + r = maj (φ^{r} (σ_{ω})) \end{array}$
であり，補題4から
$\begin{array}{r} maj (ω) + r = maj (flip (ω)) \end{array}$
を得る．

補題3の説明
写像 $flip, σ_{∙}, φ$ は上図のような可換図式で表される関係にある．

定理1の証明

母関数 $\sum_{ω \in L (n, r)} q^{m a j (ω)}$ が，以下の漸化式を満たすことを示す．

$\begin{array}{r} \sum_{ω \in L (n, r)} q^{m a j (ω)} = q^{n} \sum_{ω \in L (r - 1, n)} q^{m a j (ω)} + \sum_{ω \in L (n - 1, r)} q^{m a j (ω)} . \end{array}$

命題6の証明

正方格子路 $ω = (ω_{1}, \dots, ω_{n + r}) \in L (n, r)$ の最後のステップ $ω_{n + r}$ が $A, B$ のどちらなのか注目すると，以下のように書ける．

$\begin{array}{r} \sum_{ω \in L (n, r)} q^{m a j (ω)} = \sum_{\begin{array}{c} ω \in L (n, r), \\ ω_{n + r} = B \end{array}} q^{m a j (ω)} + \sum_{\begin{array}{c} ω \in L (n, r), \\ ω_{n + r} = A \end{array}} q^{m a j (ω)} . \end{array}$

最後のステップが $A$ なら，それを取り去ってもmajor indexは変化しないから，まず
$\begin{array}{r} \sum_{\begin{array}{c} ω \in L (n, r), \\ ω_{n + r} = A \end{array}} q^{m a j (ω)} = \sum_{ω \in L (n - 1, r)} q^{m a j (ω)} \end{array}$
が言える．
次に，最後のステップが $B$ なら，補題3で定義した操作flipを当てる．すると，flipしたあとの格子路は最後のステップが $A$ になるから，それを取り除く，つまり
$\begin{array}{r} \sum_{\begin{array}{c} ω \in L (n, r), \\ ω_{n + r} = B \end{array}} q^{m a j (ω)} = q^{n} \sum_{\begin{array}{c} ω \in L (r, n), \\ ω_{n + r} = A \end{array}} q^{m a j (ω)} = q^{n} \sum_{ω \in L (r - 1, n)} q^{m a j (ω)} . \end{array}$

定理1の証明

$n + r$ に関する帰納法による．命題6に帰納法の仮定を使い，二項係数の対称性 (公式1)，パスカルの三角形 (公式2)を使って式変形する．
$\begin{aligned} \sum_{ω \in L (n, r)} q^{m a j (ω)} & = {(\binom{n + r - 1}{r})}_{q} + q^{n} {(\binom{n + r - 1}{n})}_{q} \\ = {(\binom{n + r - 1}{r})}_{q} + q^{n} {(\binom{n + r - 1}{r - 1})}_{q} \\ = {(\binom{n + r}{r})}_{q} \end{aligned}$