Eulerian多項式
$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多項式に関してより明示的な級数表示を与える.
$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}
この記事を高評価した人
この記事に送られたバッジ
投稿者
