文献あり

Foata全単射

155

$n$ 次対称群の元 $σ$ を $[n] := {1, 2, \dots, n}$ の順列 $σ (1) σ (2) \dots σ (n)$ と同一視する. 前回の記事で, 転倒数とmajor indexが等分布であるという以下の等式を示した.
$\begin{array}{r} \sum_{σ \in S_{n}} q^{inv (σ)} = \sum_{σ \in S_{n}} q^{maj (σ)} \end{array}$
この等式により, 順列の中の $inv (σ) = k$ のものと $maj (σ) = k$ のものの個数は等しいので, それらの間に直接全単射を構成するような証明ができることが期待される. それを与えるのがFoata全単射である.

Foata全単射

順列の間の写像 $ϕ$ を順列の長さに関して再帰的に定義する. まず, 長さ $2$ 以下の順列に対しては, $ϕ (σ) := σ$ と定める. 長さ $n - 1$ の順列全体に $ϕ$ が定まっているとする. 順列 $σ = a_{1} \dots a_{n}$ に対して, $a_{n - 1} < a_{n}$ ならば, 全ての $a_{n}$ より小さい $ϕ (a_{1} \dots a_{n - 1})$ の要素の後ろに $|$ を挿入し, $a_{n - 1}$ ならば, 全ての $a_{n}$ より大きい $ϕ (a_{1} \dots a_{n - 1})$ の要素の後ろに $|$ を挿入する. それを行った後, 末尾に $a_{n}$ を挿入する. そのようにして順列が $|$ によっていくつかのブロックに分けられたものが得られる. 各ブロックにおいて, $b_{1} \dots b_{m} \mapsto b_{m} b_{1} \dots b_{m - 1}$ と変換して $|$ を取り除いたものを $ϕ (a_{1} \dots a_{n})$ と定める.

定義が複雑なので, 具体例で計算してみる. $[8]$ の順列を $σ = 71283645$ とする. まず,
$\begin{aligned} ϕ (71) & = 71 \end{aligned}$
である. $1 < 2$ であるから, $2$ より小さい $1$ の後ろに $|$ を入れる.
$\begin{array}{r} 71 | 2 \end{array}$
各ブロックは $71, 2$ であり, それぞれに対して, $71 \mapsto 17, 2 \mapsto 2$ となって,
$\begin{array}{r} ϕ (712) = 172 \end{array}$
となる. 次に, $2 < 8$ であるから, $8$ より小さい $1, 7, 2$ の後ろに $|$ を入れる.
$\begin{array}{r} 1 | 7 | 2 | 8 \end{array}$
これより,
$\begin{array}{r} ϕ (7128) = 1728 \end{array}$
となる. 次に $8 > 3$ なので, $3$ より大きい全ての要素の後ろに $|$ を入れる.
$\begin{array}{r} 17 | 28 | 3 \end{array}$
これより,
$\begin{aligned} ϕ (71283) & = 71823 \end{aligned}$
以下, 同様の計算を続けると,
$\begin{aligned} ϕ (712836) & = 172836 \\ ϕ (7128364) & = 7182634 \\ ϕ (71283645) & = 17283645 \end{aligned}$
となる.

Foata(1968)

$ϕ$ は順列の間の全単射であり, 任意の順列 $σ$ に対して,
$\begin{aligned} maj (σ) & = inv (ϕ (σ)) \end{aligned}$
が成り立つ.

まず, 上の定義を逆にたどることによって $ϕ$ の逆写像が与えられることを示す. 長さ $n - 1$ までの順列に逆写像が与えられているとする. 長さ $n$ の順列 $a_{1} \dots a_{n}$ に対して, $a_{1} < a_{n}$ ならば, $a_{1} \dots a_{n - 1}$ の中で, $a_{n}$ より小さい $a_{i}$ の前に $|$ を挿入し, $a_{1} > a_{n}$ ならば, $a_{n}$ より大きい $a_{i}$ の前に $|$ を挿入することによって $a_{1} \dots a_{n - 1}$ がいくつかのブロックに分けられる. 各ブロックにおいて, $b_{1} \dots b_{m} \mapsto b_{2} \dots b_{m} b_{1}$ と変換したものを $c_{1} \dots c_{n - 1}$ とするとき, $ϕ^{- 1} (a_{1} \dots a_{n}) = ϕ^{- 1} (c_{1} \dots c_{n - 1}) a_{n}$ によって定まる. 後半を示す. $n = 1$ のときは明らか. $n$ に関する帰納法で示す. 長さ $n - 1$ の順列に対して成り立っているとして, $σ = a_{1} \dots a_{n}$ とする. 仮定より, $c_{1} \dots c_{n - 1} = ϕ (a_{1} \dots a_{n - 1})$ と書くと,
$\begin{array}{r} maj (a_{1} \dots a_{n - 1}) = inv (c_{1} \dots c_{n - 1}) \end{array}$
である. $c_{n - 1} > a_{n}$ のとき, $c_{i}$ の中で $a_{n}$ より大きいものの後ろに $|$ を挿入してできる各ブロックは $b_{1} \dots b_{m} \mapsto b_{m} b_{1} \dots b_{m - 1}$ となり, この部分で $ϕ (a_{1} \dots a_{n})$ の転倒数は元の順列と比べて $m - 1$ だけ増加する. また末尾に $a_{n}$ が加わることによって, 転倒数はブロックの数だけ増加することになる. よって転倒数は全体で $n - 1$ だけ増加する. 一方, $c_{n - 1} = a_{n - 1} > a_{n}$ より, major indexも $n - 1$ だけ増加する. よって,
$\begin{aligned} maj (a_{1} \dots a_{n}) & = inv (ϕ (a_{1} \dots a_{n})) \end{aligned}$
である. 次に, $c_{n - 1} < a_{n}$ のとき, $c_{i}$ の中で $a_{n}$ より小さいものの後ろに $|$ を挿入してできるブロックは $b_{1} \dots b_{m} \mapsto b_{m} b_{1} \dots b_{m - 1}$ となり, この部分で転倒数は $m - 1$ だけ減少する. また, 末尾に $a_{n}$ が加わることによって転倒数は $n - 1$ からブロックの数を引いた数だけ増加する. よってこれらを合わせると転倒数は変わらないことが分かる. 一方, $c_{n - 1} = a_{n - 1} < a_{n}$ より, major indexも変わらない. よってこの場合も
$\begin{aligned} maj (a_{1} \dots a_{n}) & = inv (ϕ (a_{1} \dots a_{n})) \end{aligned}$
が成り立つことが分かる.

降下集合を $Des (σ) := {1 \leq i \leq n - 1; σ (i) > σ (i + 1)}$ とする.

Foata-Schützenberger(1978)

$ϕ$ をFoata全単射とするとき, 任意の順列 $σ \in S_{n}$ に対して,
$\begin{aligned} Des (σ^{- 1}) & = Des (ϕ (σ)^{- 1}) \end{aligned}$
が成り立つ.

$Des (σ^{- 1})$ は $σ$ の中で $i$ より前に $i + 1$ が並んでいるような $1 \leq i \leq n - 1$ の個数である. よって, $σ$ の中で $i$ より前に $i + 1$ が並んでいるとき, $ϕ (σ)$ においても $i$ より前に $i + 1$ が並んでいることを示せばよい. $ϕ$ の計算において, $|$ を入れるときに, $i$ の後ろに $|$ が入ることと, $i + 1$ の後ろに $|$ が入ることが同値になる. $i, i + 1$ の順番が入れ替わるのは, $i$ の後ろに $|$ が入り $i + 1$ の後ろには $|$ が入らない必要があるが, その場合が起こりえないことを意味している.

これより, 以下のようなMacMahonの等式の精密化が得られる.

任意の $S \subset [n - 1]$ に対して,
$\begin{aligned} \sum_{\begin{array}{c} σ \in S_{n} \\ Des (σ^{- 1}) = S \end{array}} q^{inv (σ)} & = \sum_{\begin{array}{c} σ \in S_{n} \\ Des (σ^{- 1}) = S \end{array}} q^{maj (σ)} \end{aligned}$
が成り立つ.