peak多項式と変形Foata-Strehl作用

$n$ 次対称群の元 $σ$ を $[n] := {1, 2, \dots, n}$ の順列 $σ (1) σ (2) \dots σ (n)$ と同一視する. 降下集合を $Des (σ) := {1 \leq i \leq n; a_{i} > a_{i + 1}}$ として, $des (σ) := | Des (σ) |$ を降下数といい, 降下集合の元を降下という. Eulerian多項式を $1 \leq n$ に対して,
$\begin{array}{r} A_{n} (t) := \sum_{σ \in S_{n}} t^{des (σ) + 1} \end{array}$
と定義する.

peak, 二重降下, 二重上昇

$[n]$ の順列 $σ = a_{1} \dots a_{n}$ に対して, $a_{i - 1} < a_{i} > a_{i + 1}$ となる $1 < i < n$ をpeakといい, $σ$ のpeakの個数を $peak (σ)$ と表し, peak数という. $a_{i - 1} > a_{i} > a_{i + 1}$ となる $1 \leq i \leq n$ を二重降下, $a_{i - 1} < a_{i} < a_{i + 1}$ となる $1 \leq i \leq n$ を二重上昇とする. この定義において, $a_{0} = a_{n + 1} = \infty$ と見なす.

peak多項式

$1 \leq n$ に対し,
$\begin{array}{r} P_{n} (t) := \sum_{σ \in S_{n}} t^{peak (σ) + 1} \end{array}$
をpeak多項式という.

次の定理がこの記事の目標である.

$1 \leq n$ に対し,
$\begin{aligned} A_{n} (t) & = {(\frac{1 + t}{2})}^{n + 1} P_{n} (\frac{4 t}{(1 + t)^{2}}) \end{aligned}$
が成り立つ.

以下, 証明の準備を行う.

変形Foata-Strehl作用

$[n]$ の順列 $σ = a_{1} \dots a_{n}$ に対し, $x = a_{i}$ とする( $a_{0} = a_{n + 1} = \infty$ とみなす). 変形Foata-Strehl作用 $ϕ_{x} : S_{n} \to S_{n}$ は以下のように定義される.

$i$ が二重降下ならば, $x$ を取り除いたあと, $a_{j} < a_{i} < a_{j + 1}, i < j$ となる最小の $j$ に対して, $a_{j}$ と $a_{j + 1}$ の間に $x$ を挿入する.
$i$ が二重上昇ならば, $x$ を取り除いたあと, $a_{j - 1} > a_{i} > a_{j}, j < i$ となる最大の $j$ に対して, $a_{j - 1}$ と $a_{j}$ の間に $x$ を挿入する.
どちらでもない場合には何もしない.

定義から $x, y \in [n]$ に対して, $ϕ_{x}, ϕ_{y}$ は可換であることから, $[n]$ の部分集合 $S = {x_{1}, \dots, x_{n}}$ に対して,
$\begin{array}{r} ϕ_{S} := ϕ_{x_{1}} \circ ϕ_{x_{2}} \circ \dots \circ ϕ_{x_{n}} \end{array}$
と定義する. 順列 $σ$ に対して, その変形Foata-Strehl作用による軌道を
$\begin{array}{r} Orb (σ) := {ϕ_{S} (σ); S \subset [n]} \end{array}$
によって定義する.

$[n]$ の順列 $σ$ に対して,
$\begin{array}{r} \sum_{π \in Orb (σ)} t^{des (π)} = t^{peak (σ)} (1 + t)^{n - 1 - 2 peak (σ)} \end{array}$
が成りたつ.

定義より, $peak (σ)$ の値は変形Foata-Strehl作用により不変である. 二重降下であるような $x$ を選んで変形Foata-Strehl作用を繰り返すことによって, $Orb (σ)$ の中で二重降下が $1$ つもないようなただ一つの順列に帰着する. それを $\hat{π}$ とする. $\hat{π}$ は二重降下を $1$ つも持たないので, $\hat{π}$ の降下は全てpeakである. つまり, $des (\hat{π}) = peak (\hat{π}) = peak (σ)$ が成り立つ. また $\hat{π}$ の中で, 変形Foata-Strehl作用で動くのは先頭と降下とその直後を除いた $m := n - 1 - 2 des (\hat{π}) = n - 1 - 2 peak (σ)$ 個であり, 動く数全体を $[m]^{'} \subset [n]$ とすると, $S \subset [m]^{'}$ に対して, $des (ϕ_{S} (\hat{π})) = des (\hat{π}) + | S | = peak (σ) + | S |$ となる. よって,
$\begin{aligned} \sum_{π \in Orb (σ)} t^{des (π)} & = \sum_{S \subset [m]^{'}} t^{peak (σ) + | S |} = t^{peak (σ)} (1 + t)^{n - 1 - 2 peak (σ)} \end{aligned}$
となって示される.

定理1の証明

定理2の証明より, $σ$ の軌道の要素の数は $2^{n - 1 - 2 peak (σ)}$ であるから
$\begin{aligned} 2^{n + 1} \sum_{σ \in S_{n}} t^{des (σ) + 1} & = 2^{n + 1} \sum_{σ \in S_{n}} 2^{- (n - 1 - 2 peak (σ))} \sum_{π \in Orb (σ)} t^{des (π) + 1} \end{aligned}$
と表される. 右辺に定理2を適用して, 定理1を得る.

投稿日：2月12日

この記事を高評価した人

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

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

バッジはありません。

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

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

投稿者

Wataru

739

49483

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

他の人のコメント

コメントはありません。

読み込み中

Wataru

peak多項式と変形Foata-Strehl作用