Eulerian多項式

124

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

降下集合を $Des (σ) := {1 \leq i < n; a_{i} > a_{i + 1}}$ として, $des (σ) := | Des (σ) |$ を降下数といい, 降下集合の元を降下という.

Eulerian多項式を $A_{0} (t) := 1$
$\begin{array}{r} A_{n} (t) := \sum_{σ \in S_{n}} t^{des (σ) + 1} \end{array}$
で定義する. $A_{n}$ の $k$ 次の係数を $⟨ \binom{n}{k} ⟩$ と表し, Eulerian数という.

上の定義においては, $A_{n}$ は $n$ 次多項式であるが,
$\begin{array}{r} \sum_{σ \in S_{n}} t^{des (σ)} \end{array}$
をEulerian多項式という流儀もあり, その場合はEulerian多項式は $n - 1$ 次になることに注意する必要がある.
Eulerian数は次のような対称性を持つ.

$0 < k \leq n$ に対して,
$\begin{aligned} ⟨ \binom{n}{k} ⟩ & = ⟨ \binom{n}{n + 1 - k} ⟩ \end{aligned}$
が成り立つ.

$⟨ \binom{n}{k} ⟩$ は降下数が $k - 1$ であるような $[n]$ の順列の個数である. 降下数が $k - 1$ であるような順列 $σ = a_{1} \dots a_{n}$ に対して, $b_{i} = n + 1 - a_{i}$ とすると, $b_{1} \dots b_{n}$ の降下数は $(n - 1) - (k - 1) = n - k$ となる. これは降下数が $k - 1$ の順列と降下数が $n - k$ の順列の間の全単射を与える. よって,
$\begin{aligned} ⟨ \binom{n}{k} ⟩ & = ⟨ \binom{n}{n + 1 - k} ⟩ \end{aligned}$
である.

Eulerian数は次のような漸化式を持つ.

$0 < k \leq n$ に対し,
$\begin{aligned} ⟨ \binom{n}{k} ⟩ & = (n - k + 1) ⟨ \binom{n - 1}{k - 1} ⟩ + k ⟨ \binom{n - 1}{k} ⟩ \end{aligned}$
が成り立つ.

まず, $[n - 1]$ の順列 $σ$ の降下数が $k - 2$ の場合と, $k - 1$ の場合のみ, それに $n$ を挿入した順列の降下数が $k - 1$ になる場合があることが分かる. $σ$ の降下数が $k - 2$ の場合, 降下の直後と末尾以外の $n$ の挿入によって降下数が $1$ 増える. よってその方法は $n - k + 1$ 通りある. $σ$ の降下数が $k - 1$ の場合, 降下の直後と末尾への挿入によって降下数が変わらない. よってその方法は $k$ 通りある. これらより,
$\begin{aligned} ⟨ \binom{n}{k} ⟩ & = (n - k + 1) ⟨ \binom{n - 1}{k - 1} ⟩ + k ⟨ \binom{n - 1}{k} ⟩ \end{aligned}$
が従う.

順列 $σ = a_{1} \dots a_{n}$ に対して, $i < a_{i}$ となる $1 \leq i \leq n$ を超過といい, その全体の集合を $Exc (σ)$ と表し, 超過集合という. $exc (σ) := | Exc (σ) |$ を超過数という.

$1 \leq n$ に対して,
$\begin{aligned} \sum_{σ \in S_{n}} t^{exc (σ) + 1} & = A_{n} (t) \end{aligned}$
が成り立つ.

$\begin{array}{r} \sum_{k = 0}^{n} A_{n, k} t^{k} := \sum_{σ \in S_{n}} t^{exc (σ) + 1} \end{array}$
とする. $[n - 1]$ の順列 $σ = a_{1} \dots a_{n - 1}$ に対して, $a_{i}$ を $n$ に置き換えて末尾に $a_{i}$ を追加することによって, $[n]$ の順列が得られる. この操作は $i$ が超過のときは超過数を変えず, $i$ が超過数でないときは超過数を $1$ 増やす. よって,
$\begin{aligned} A_{n, k} & = (n - k + 1) A_{n - 1, k - 1} + k A_{n - 1, k} \end{aligned}$
が得られる. これはEulerian数と全く同じ漸化式であり, $A_{1, k} = ⟨ \binom{1}{k} ⟩, A_{k, 0} = ⟨ \binom{k}{0} ⟩$ は明らかだから, 帰納的に $A_{n, k} = ⟨ \binom{n}{k} ⟩$ が示される.

これはつまり, 降下数と超過数が等分布であることを意味している.
次に, Eulerian多項式に関してより明示的な級数表示を与える.

Carlitz, Worpitzky

$0 \leq n$ のとき,
$\begin{aligned} \frac{A_{n} (t)}{(1 - t)^{n + 1}} & = \sum_{0 \leq k} k^{n} t^{k} \end{aligned}$
が成り立つ.

$n = 0$ のときは明らか. $1 \leq n$ とする. 両辺の $k$ 次の係数を考えて,
$\begin{aligned} \sum_{σ \in S_{n}} (\binom{n + k - des (σ) - 1}{n}) & = k^{n} \end{aligned}$
を示せばよい. 右辺は $[n]$ の要素を $k$ 個の空集合を許した集合への順序付きの分割 $(A_{1}, \dots, A_{k})$ の個数に等しい. $A_{i}$ の要素を昇順に並び替えた順列を $B_{i}$ とすると, $B_{1} | B_{2} | \dots | B_{k}$ のように仕切りを用いて分割 $(A_{1}, \dots, A_{k})$ を表すことができ, その仕切りを外すと順列が得られる. 逆に順列 $σ$ が与えられたとき, $k$ 個の分割を表す仕切りを入れる方法の個数は, まず降下の直後に $des (σ)$ 個の仕切りを最初から入れておくことにより, 残りの $k - 1 - des (σ)$ の仕切りを追加する方法の個数となる. 仕切りを入れる場所の総数は $n + 1$ 個であるから, それは重複順列の個数
$\begin{array}{r} (\binom{n + k - des (σ) - 1}{n}) \end{array}$
で与えられる. よって, 全ての順列に対して足し合わせることによって,
$\begin{aligned} \sum_{σ \in S_{n}} (\binom{n + k - des (σ) - 1}{n}) & = k^{n} \end{aligned}$
を得る.