転倒数とmajor indexの等分布性

196

$n$ 次対称群の元 $σ$ を $[n] := {1, 2, \dots, n}$ の順列 $σ (1) σ (2) \dots σ (n)$ と同一視する.

転倒数

$[n]$ の順列 $σ = a_{1} \dots a_{n}$ に対し, $1 \leq i < j \leq n$ かつ $a_{i} > a_{j}$ となるような組 $(i, j)$ を $σ$ の転倒という. その個数を $σ$ の転倒数といい, $inv (σ)$ で表す.

major index

$[n]$ の順列 $σ = a_{1} \dots a_{n}$ に対して, その降下集合を $Des (σ) := {1 \leq i < n; a_{i} > a_{i + 1}}$ と定義する.
$\begin{array}{r} maj (σ) = \sum_{i \in Des (σ)} i \end{array}$
によって定義される $maj (σ)$ を $σ$ のmajor indexという. $des (σ) := | Des (σ) |$ を降下数という.

次は転倒数とmajor indexの等分布性を表すMacMahonの定理である.

MacMahonの定理

$1 \leq n$ に対し,
$\begin{array}{r} \sum_{σ \in S_{n}} q^{inv (σ)} = \sum_{σ \in S_{n}} q^{maj (σ)} = \prod_{k = 1}^{n} \frac{1 - q^{k}}{1 - q} \end{array}$
が成り立つ.

二つに分けて証明する.

$1 \leq n$ に対し,
$\begin{aligned} \sum_{σ \in S_{n}} q^{inv (σ)} & = \prod_{k = 1}^{n} \frac{1 - q^{k}}{1 - q} \end{aligned}$
が成り立つ.

$n$ に関する記法により示す. $n = 1$ のときは明らかに成り立つ. $n - 1$ まで題意が成立しているとする. $[n - 1]$ の順列 $σ = a_{1} \dots a_{n - 1}$ に $n$ を挿入して $[n]$ の順列を得る方法は $n$ 通りある. $n$ を末尾に挿入した順列の転倒数は $inv (σ)$ であり, $1 \leq i \leq n - 1$ に対し, $n$ を $a_{i}$ の $1$ つ前に挿入した順列の転倒数は $inv (σ) + n - i$ である. よって $[n - 1]$ の各順列と各 $0 \leq i \leq n - 1$ に対して, $σ$ に $n$ を挿入した順列で $inv (σ) + i$ を転倒数に持つものが $1$ つずつ得られるから,
$\begin{aligned} \sum_{σ \in S_{n}} q^{inv (σ)} & = (1 + q + \dots + q^{n - 1}) \sum_{σ \in S_{n - 1}} q^{inv (σ)} \\ = \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{aligned}$
となって示される.

$1 \leq n$ に対し,
$\begin{aligned} \sum_{σ \in S_{n}} q^{maj (σ)} & = \prod_{k = 1}^{n} \frac{1 - q^{k}}{1 - q} \end{aligned}$
が成り立つ.

$n$ に関する帰納法で示す. $n = 1$ のときは明らかに成り立つ. $n - 1$ まで題意が成立しているとする. $[n - 1]$ の順列 $σ = a_{1} \dots a_{n - 1}$ に $n$ を挿入して $[n]$ の順列を得る方法は $n$ 通りある. $m = des (σ)$ とする. $n$ を先頭に挿入した順列のmajor indexは $maj (σ) + m + 1$ に等しく, $n$ を末尾に挿入した順列のmajor indexは $maj (σ)$ に等しい. 降下集合の元を $i_{1} < \dots < i_{m}$ と書く. $1 \leq j \leq m$ に対し, $a_{i_{j}}$ の $1$ つ後ろに $n$ を挿入した順列の降下集合は

$\begin{array}{r} i_{1} < \dots < i_{j - 1} < i_{j} + 1 < \dots < i_{m} + 1 \end{array}$
と表せるから, そのmajor indexは $maj (σ) + m - j + 1$ である. 次に,
$\begin{array}{r} [n - 1] - Des (σ) = {b_{1}, \dots, b_{n - 1 - m}}, b_{1} < \dots < b_{n - 1 - m} \end{array}$
とする. $1 \leq j \leq n - m - 2$ に対し, $a_{b_{j}}$ の1つ後ろに $n$ を挿入した順列の降下集合は, ある $1 \leq k \leq m + 1$ を用いて
$\begin{array}{r} i_{1} < \dots < i_{k - 1} < b_{j} + 1 < i_{k} + 1 < \dots < i_{m} + 1 \end{array}$
と表すことができる. $b_{j}$ の前には $k - 1$ 個の降下集合の元があるから, $b_{j} = j + k - 1$ である. よってそのmajor indexは $maj (σ) + (b_{j} + 1) + (m - k + 1) = maj (σ) + m + j + 1$ で与えられる. よって, $σ$ に $n$ を挿入した順列で $maj (σ) + i$ をmajor indexに持つものが1つずつ得られるから,
$\begin{aligned} \sum_{σ \in S_{n}} q^{maj (σ)} & = (1 + q + \dots + q^{n - 1}) \sum_{σ \in S_{n - 1}} q^{maj (σ)} \\ = \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{aligned}$
となって示される.