1

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

95
0
$$\newcommand{bk}[0]{\boldsymbol{k}} \newcommand{bl}[0]{\boldsymbol{l}} \newcommand{BQ}[5]{{}_{#1}\psi_{#2}\left[\begin{matrix}#3\\#4\end{matrix};#5\right]} \newcommand{calA}[0]{\mathcal{A}} \newcommand{calS}[0]{\mathcal{S}} \newcommand{CC}[0]{\mathbb{C}} \newcommand{F}[5]{{}_{#1}F_{#2}\left[\begin{matrix}#3\\#4\end{matrix};#5\right]} \newcommand{inv}[0]{\mathrm{inv}} \newcommand{maj}[0]{\mathrm{maj}} \newcommand{ol}[0]{\overline} \newcommand{Q}[5]{{}_{#1}\phi_{#2}\left[\begin{matrix}#3\\#4\end{matrix};#5\right]} \newcommand{QQ}[0]{\mathbb{Q}} \newcommand{ZZ}[0]{\mathbb{Z}} $$

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

peak, 二重降下, 二重上昇

$[n]$の順列$\sigma=a_1\cdots a_n$に対して, $a_{i-1}< a_i>a_{i+1}$となる$1< i< n$をpeakといい, $\sigma$のpeakの個数を$\mathrm{peak}(\sigma)$と表し, 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{align} P_n(t):=\sum_{\sigma\in\mathfrak{S}_n}t^{\mathrm{peak}(\sigma)+1} \end{align}
をpeak多項式という.

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

$1\leq n$に対し,
\begin{align} A_n(t)&=\left(\frac{1+t}2\right)^{n+1}P_n\left(\frac{4t}{(1+t)^2}\right) \end{align}
が成り立つ.

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

変形Foata-Strehl作用

$[n]$の順列$\sigma=a_1\cdots a_n$に対し, $x=a_i$とする($a_0=a_{n+1}=\infty$とみなす). 変形Foata-Strehl作用$\phi_x:\mathfrak{S}_n\to\mathfrak{S}_n$は以下のように定義される.

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

定義から$x,y\in [n]$に対して, $\phi_x,\phi_y$は可換であることから, $[n]$の部分集合$S=\{x_1,\dots,x_n\}$に対して,
\begin{align} \phi_S:=\phi_{x_1}\circ\phi_{x_2}\circ\cdots \circ\phi_{x_n} \end{align}
と定義する. 順列$\sigma$に対して, その変形Foata-Strehl作用による軌道を
\begin{align} \mathrm{Orb}(\sigma):=\{\phi_S(\sigma);S\subset [n]\} \end{align}
によって定義する.

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

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

定理1の証明

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

投稿日:212
OptHub AI Competition

この記事を高評価した人

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

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

バッジはありません。

投稿者

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

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中