desとexcの等分布性の全単射による証明

降下集合を $Des (σ) := {1 \leq i \leq n; a_{i} > a_{i + 1}}$ として, $des (σ) := | Des (σ) |$ を降下数といい, 降下集合の元を降下という. 超過集合を $Exc (σ) := {1 \leq i \leq n; i < σ (i)}$ として, $exc (σ) := | Exc (σ) |$ を超過数といい, 超過集合の元を超過という. 前回の記事で以下の定理を示した.

des

と

exc

の等分布性

$\begin{aligned} \sum_{σ \in S_{n}} t^{des (σ) + 1} & = \sum_{σ \in S_{n}} t^{exc (σ) + 1} \end{aligned}$

これは, 降下数が $k$ である順列の個数と超過数が $k$ である順列の個数が等しいことを意味している. よって, 直接全単射を構成するような証明が望まれる. そのような証明はD. Foataによって最初に発見された.
$[n] := {1, 2 \dots, n}$ とする.

$[n]$ の順列 $σ$ をいくつかのサイクルの積に分解することを考える.
$\begin{array}{r} σ = (c_{11} c_{12} \dots c_{1 l_{1}}) (c_{21} c_{22} \dots c_{2 l_{2}}) \dots (c_{m 1} c_{m 2} \dots c_{m l_{m}}) \end{array}$
上のようなサイクルによる分解において, 各 $i$ に対して, $c_{i 1}, \dots, c_{i l_{i}}$ の中で $c_{i 1}$ が最も大きく $i < j$ ならば $c_{i 1} < c_{j 1}$ となるように並び替えられているとする. このとき, 各 $i$ に対して $c_{i 2}$ から $c_{i l_{i}}$ までを逆向きにして並べたもの
$\begin{array}{r} ψ (σ) := c_{11} c_{1 l_{1}} \dots c_{12} c_{21} c_{2 l_{2}} \dots c_{22} \dots c_{m 1} c_{m l_{m}} \dots c_{m 2} \end{array}$
によって写像 $ψ$ を定義する.

$ψ (σ)$ が与えられたとき, $c_{i 1}$ より後ろ側にあって, $c_{i 1}$ より真に大きいものとして $c_{(i + 1) 1}$ が決まり, そこから $σ$ が復元できる. よって $ψ$ は全単射である.

以下が示されれば, 定理1が従う.

Foata

任意の順列 $σ$ に対して, $exc (σ) = des (ψ (σ))$ が成り立つ.

$σ$ のサイクルの一つを $c_{1} \dots c_{m}$ とすると, $c_{m + 1}$ としてそのサイクルに含まれる超過数は $c_{i} < c_{i + 1}$ であるような $i$ の個数である. よって, それは $c_{1}$ を最大値として, $c_{1} c_{m} \dots c_{2}$ の降下数によって与えられることが分かり, $ψ (σ)$ の定義において常に $c_{i l_{i}} < c_{(i + 1) 1}$ であるから, これらをつなげたものである $ψ (σ)$ の降下数は $σ$ の超過数に等しい.

上の議論について, 一つ例を挙げる. $σ = 526314$ とする. $σ$ をサイクル分解すると,
$\begin{array}{r} σ = (15) (2) (364) \end{array}$
となる. $(15)$ の部分の超過数は $1 < 5$ だけが成り立つから $1$ である. $(2)$ の部分の超過数は $0$ . $(364)$ の部分の超過数は $3 < 6$ だけが成り立つから $1$ である. よって合わせて $2$ である. $ψ$ の定義におけるサイクル分解の並び替えを行うと,
$\begin{array}{r} σ = (2) (51) (643) \end{array}$
となる.
$\begin{array}{r} ψ (σ) = 251634 \end{array}$
である. これの降下数を求めてみると, $5 > 1, 6 > 3$ より $2$ である. ここで両方の計算を行ったが, 比較して数え上げられている部分に着目すると, ともに $1 < 5, 3 < 6$ である. このように, $σ$ の超過がちょうど $ψ (σ)$ の降下に対応するように上手く $ψ$ が定義されているのである.

投稿日：2月10日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

Wataru

656

45549

超幾何関数, 直交関数, 多重ゼータ値などに興味があります

他の人のコメント

コメントはありません。

読み込み中

Wataru

desとexcの等分布性の全単射による証明