Foata全単射
$n$次対称群の元$\sigma$を$[n]:=\{1,2,\dots,n\}$の順列$\sigma(1)\sigma(2)\cdots\sigma(n)$と同一視する.
前回の記事
で, 転倒数とmajor indexが等分布であるという以下の等式を示した.
\begin{align}
\sum_{\sigma\in\mathfrak{S}_n}q^{\inv(\sigma)}=\sum_{\sigma\in\mathfrak{S}_n}q^{\maj(\sigma)}
\end{align}
この等式により, 順列の中の$\inv(\sigma)=k$のものと$\maj(\sigma)=k$のものの個数は等しいので, それらの間に直接全単射を構成するような証明ができることが期待される. それを与えるのがFoata全単射である.
順列の間の写像$\phi$を順列の長さに関して再帰的に定義する. まず, 長さ$2$以下の順列に対しては, $\phi(\sigma):=\sigma$と定める. 長さ$n-1$の順列全体に$\phi$が定まっているとする. 順列$\sigma=a_1\cdots a_n$に対して, $a_{n-1}< a_n$ならば, 全ての$a_n$より小さい$\phi(a_1\cdots a_{n-1})$の要素の後ろに$|$を挿入し, $a_{n-1}$ならば, 全ての$a_n$より大きい$\phi(a_1\cdots a_{n-1})$の要素の後ろに$|$を挿入する. それを行った後, 末尾に$a_n$を挿入する. そのようにして順列が$|$によっていくつかのブロックに分けられたものが得られる. 各ブロックにおいて, $b_1\cdots b_m\mapsto b_mb_1\cdots b_{m-1}$と変換して$|$を取り除いたものを$\phi(a_1\cdots a_n)$と定める.
定義が複雑なので, 具体例で計算してみる. $[8]$の順列を$\sigma=71283645$とする. まず,
\begin{align}
\phi(71)&=71
\end{align}
である. $1<2$であるから, $2$より小さい$1$の後ろに$|$を入れる.
\begin{align}
71|2
\end{align}
各ブロックは$71, 2$であり, それぞれに対して, $71\mapsto 17, 2\mapsto 2$となって,
\begin{align}
\phi(712)=172
\end{align}
となる. 次に, $2<8$であるから, $8$より小さい$1,7,2$の後ろに$|$を入れる.
\begin{align}
1|7|2|8
\end{align}
これより,
\begin{align}
\phi(7128)=1728
\end{align}
となる. 次に$8>3$なので, $3$より大きい全ての要素の後ろに$|$を入れる.
\begin{align}
17|28|3
\end{align}
これより,
\begin{align}
\phi(71283)&=71823
\end{align}
以下, 同様の計算を続けると,
\begin{align}
\phi(712836)&=172836\\
\phi(7128364)&=7182634\\
\phi(71283645)&=17283645
\end{align}
となる.
$\phi$は順列の間の全単射であり, 任意の順列$\sigma$に対して,
\begin{align}
\maj(\sigma)&=\inv(\phi(\sigma))
\end{align}
が成り立つ.
まず, 上の定義を逆にたどることによって$\phi$の逆写像が与えられることを示す. 長さ$n-1$までの順列に逆写像が与えられているとする. 長さ$n$の順列$a_1\cdots a_n$に対して, $a_1< a_n$ならば, $a_1\cdots a_{n-1}$の中で, $a_n$より小さい$a_i$の前に$|$を挿入し, $ a_1>a_n$ならば, $a_n$より大きい$a_i$の前に$|$を挿入することによって$a_1\cdots a_{n-1}$がいくつかのブロックに分けられる. 各ブロックにおいて, $b_1\cdots b_{m}\mapsto b_2\cdots b_mb_1$と変換したものを$c_1\cdots c_{n-1}$とするとき, $\phi^{-1}(a_1\cdots a_n)=\phi^{-1}(c_1\cdots c_{n-1})a_n$によって定まる. 後半を示す. $n=1$のときは明らか. $n$に関する帰納法で示す. 長さ$n-1$の順列に対して成り立っているとして, $\sigma=a_1\cdots a_n$とする. 仮定より, $c_1\cdots c_{n-1}=\phi(a_1\cdots a_{n-1})$と書くと,
\begin{align}
\maj(a_1\cdots a_{n-1})=\inv(c_1\cdots c_{n-1})
\end{align}
である. $c_{n-1}>a_n$のとき, $c_i$の中で$a_n$より大きいものの後ろに$|$を挿入してできる各ブロックは$b_1\cdots b_m\mapsto b_mb_1\cdots b_{m-1}$となり, この部分で$\phi(a_1\cdots a_n)$の転倒数は元の順列と比べて$m-1$だけ増加する. また末尾に$a_n$が加わることによって, 転倒数はブロックの数だけ増加することになる. よって転倒数は全体で$n-1$だけ増加する. 一方, $c_{n-1}=a_{n-1}>a_n$より, major indexも$n-1$だけ増加する. よって,
\begin{align}
\maj(a_1\cdots a_n)&=\inv(\phi(a_1\cdots a_n))
\end{align}
である. 次に, $c_{n-1}< a_n$のとき, $c_i$の中で$a_n$より小さいものの後ろに$|$を挿入してできるブロックは$b_1\cdots b_m\mapsto b_mb_1\cdots b_{m-1}$となり, この部分で転倒数は$m-1$だけ減少する. また, 末尾に$a_n$が加わることによって転倒数は$n-1$からブロックの数を引いた数だけ増加する. よってこれらを合わせると転倒数は変わらないことが分かる. 一方, $c_{n-1}=a_{n-1}< a_n$より, major indexも変わらない. よってこの場合も
\begin{align}
\maj(a_1\cdots a_n)&=\inv(\phi(a_1\cdots a_n))
\end{align}
が成り立つことが分かる.
降下集合を$\mathrm{Des}(\sigma):=\{1\leq i\leq n-1;\sigma(i)>\sigma(i+1)\}$とする.
$\phi$をFoata全単射とするとき, 任意の順列$\sigma\in \mathfrak{S}_n$に対して,
\begin{align}
\mathrm{Des}(\sigma^{-1})&=\mathrm{Des}(\phi(\sigma)^{-1})
\end{align}
が成り立つ.
$\mathrm{Des}(\sigma^{-1})$は$\sigma$の中で$i$より前に$i+1$が並んでいるような$1\leq i\leq n-1$の個数である. よって, $\sigma$ の中で$i$より前に$i+1$が並んでいるとき, $\phi(\sigma)$においても$i$より前に$i+1$が並んでいることを示せばよい. $\phi$の計算において, $|$を入れるときに, $i$の後ろに$|$が入ることと, $i+1$の後ろに$|$が入ることが同値になる. $i,i+1$の順番が入れ替わるのは, $i$の後ろに$|$が入り$i+1$の後ろには$|$が入らない必要があるが, その場合が起こりえないことを意味している.
これより, 以下のようなMacMahonの等式の精密化が得られる.
任意の$S\subset [n-1]$に対して,
\begin{align}
\sum_{\substack{\sigma \in \mathfrak{S}_n\\\mathrm{Des}(\sigma^{-1})=S}}q^{\inv(\sigma)}&=\sum_{\substack{\sigma \in \mathfrak{S}_n\\\mathrm{Des}(\sigma^{-1})=S}}q^{\maj(\sigma)}
\end{align}
が成り立つ.
参考文献
この記事を高評価した人
この記事に送られたバッジ
投稿者
