2

Eulerian多項式

138
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{eul}[2]{\left\langle{#1}\atop {#2}\right\rangle} \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< n;a_i>a_{i+1}\}$として, $\mathrm{des}(\sigma):=|\mathrm{Des}(\sigma)|$を降下数といい, 降下集合の元を降下という.

Eulerian多項式を$A_0(t):=1$
\begin{align} A_n(t):=\sum_{\sigma\in\mathfrak{S}_n}t^{\mathrm{des}(\sigma)+1} \end{align}
で定義する. $A_n$$k$次の係数を$\eul nk$と表し, Eulerian数という.

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

$0< k\leq n$に対して,
\begin{align} \eul nk&=\eul n{n+1-k} \end{align}
が成り立つ.

$\eul nk$は降下数が$k-1$であるような$[n]$の順列の個数である. 降下数が$k-1$であるような順列$\sigma=a_1\cdots a_n$に対して, $b_i=n+1-a_i$とすると, $b_1\cdots b_n$の降下数は$(n-1)-(k-1)=n-k$となる. これは降下数が$k-1$の順列と降下数が$n-k$の順列の間の全単射を与える. よって,
\begin{align} \eul nk&=\eul n{n+1-k} \end{align}
である.

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

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

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

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

$1\leq n$に対して,
\begin{align} \sum_{\sigma\in\mathfrak{S}_n}t^{\mathrm{exc}(\sigma)+1}&=A_n(t) \end{align}
が成り立つ.

\begin{align} \sum_{k=0}^nA_{n,k}t^k:=\sum_{\sigma\in\mathfrak{S}_n}t^{\mathrm{exc}(\sigma)+1} \end{align}
とする. $[n-1]$の順列$\sigma=a_1\cdots a_{n-1}$に対して, $a_i$$n$に置き換えて末尾に$a_i$を追加することによって, $[n]$の順列が得られる. この操作は$i$が超過のときは超過数を変えず, $i$が超過数でないときは超過数を$1$増やす. よって,
\begin{align} A_{n,k}&=(n-k+1)A_{n-1,k-1}+kA_{n-1,k} \end{align}
が得られる. これはEulerian数と全く同じ漸化式であり, $A_{1,k}=\eul 1k, A_{k,0}=\eul k0$は明らかだから, 帰納的に$A_{n,k}=\eul nk$が示される.

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

Carlitz, Worpitzky

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

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

等式
\begin{align} A_n(t)&=(1-t)^{n+1}\sum_{0\leq k}k^nt^k \end{align}
の係数を比較することによって次の明示式が得られる.

\begin{align} \eul nk&=\sum_{j=0}^k(-1)^j(k-j)^n\binom{n+1}j \end{align}

投稿日:29
OptHub AI Competition

この記事を高評価した人

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

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

バッジはありません。

投稿者

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

コメント

他の人のコメント

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