peak多項式と変形Foata-Strehl作用
$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}
と定義する.
$[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$と見なす.
$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}
が成り立つ.
以下, 証明の準備を行う.
$[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$は以下のように定義される.
- $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]$に対して, $\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}
となって示される.
定理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を得る.
この記事を高評価した人
この記事に送られたバッジ
投稿者
