カタラン数とその拡張 その4 〜ロビンソン対応と321-avoiding permutation〜

$w^{\prime }$が$w$に一回のクヌース変換を行ったものとして一般性を失わない。$u=u_1{u}_2\cdots u_p,v=v_1{v}_2\cdots v_q$を適当な数字列として、対称性から2通りの場合に帰着できる。
(i)

$P(w)\leftarrow x$のワードと$wx$がクヌース同値であることを示せば帰納法により十分である。そのために、バンプアルゴリズムの過程をクヌース変換のみで記述できることを示せば良い。バンプアルゴリズムの1ステップにあたる

が、対応する数字列のクヌース変換だけで実現できる様子を示す。それぞれに対応する数字列は、
$$(89|1235674),(895|123467)$$
である。(行の区切りを$|$で示している。)まず、
$$(89|1235\underset{―}{674})\to (89|123\underset{―}{564}7)\to (89|1235467)$$
のように、バンプする数字$a_1=4$を$a_2=5$のすぐ後ろまで移動させることができる。これらの変換はすべて、
$$xyz\to xzy(y>x>z)$$
の形をしたクヌース変換である。次に、
$$(89|12\underset{―}{354}67)\to (89|1\underset{―}{253}467)\to (89|\underset{―}{152}3467)\to (89|5123467)=(895|123467)$$
のように、$a_2=5$を$2$行目の右端まで移動させることができる。これらの変換はすべて、
$$xyz\to yxz(y>z>x)$$
の形をしたクヌース変換である。このように、バンプアルゴリズムは、対応する数字列のクヌース変換だけで実現できることがわかった。

$L(w)$は$w^{\prime }:=w(P(w))$とクヌース同値なので、$L(w^{\prime })$を求めればよい。$P(w)$の行数を$l$とする。

としよう。$w^{\prime }$は
$$w^{\prime }=(a_{l1}{a}_{l2}\cdots a_{l{\lambda }_l}|\cdots |a_{21}{a}_{22}\cdots a_{2{\lambda }_2}|a_{11}{a}_{12}\cdots a_{1{\lambda }_2})$$
と書ける。まず、$P(w)$の各行の左側の数字を並べた$a_{l1}\cdots a_{31}{a}_{21}{a}_{11}$は、$P(w)$の減少部分列を与えるので、$L(w^{\prime })\ge l$である。また、$w^{\prime }$の部分列を作る際、$P(w)$の同じ行から$2$つ以上の数字を選ぶと減少部分列とならないので、$L(w^{\prime })\le l$である。以上より、$L(w)=L(w^{\prime })=l$である。

$1,2,\cdots ,n$の並び替え$w$に対して、バンプアルゴリズムによって得られる標準盤を$P=P(w)$とする。$Q=Q(w)$は$P$と同じ形をした標準盤で、$P$を作る際のバンプアルゴリズムで$k$番目に追加した箱に数字$k$を書き込んだものとする。これにより$w$から標準盤の組$(P,Q)$を得ることができる。$(P,Q)$から$w$を復元するには、単に$Q$から最大の数字の入った箱を取り除き、$P$で対応する箱に対して逆バンプを行うことを繰り返せば良い。

$2\times n$の長方形の形をした標準盤の個数は、カタラン数$c_n$に等しいので、これと行数が$2$以下の、同じ形をした標準盤の組$(P,Q)$が一対一に対応することを示せば十分である。この対応は簡単に作ることができる。

標準盤の組$(P,Q)$に対し、$Q$の各数字$k$を$k^{\ast }:=n+1-k$に置き換え、それを$180$度回転させた図形を$Q^{\ast }$とする。$P$の右に$Q^{\ast }$をはめ込むと、$2\times n$の長方形の形をした標準盤$T$を得ることができる。

逆に$2\times n$の長方形の形をした標準盤$T$が与えられた時、$T$のうち$n$以下の数字からなる部分$P$とそれ以外の部分$Q^{\ast }$とに分ける。$Q^{\ast }$の各数字$k$を$k^{\ast }$に置き換え、それを$180$度回転させた図形を$Q$とすれば、標準盤の組$(P,Q)$を得ることができる。これらが互いに逆写像を与える。

これらが$1$以上$k+l-1$以下の整数であることは簡単に分かる。$l-{\lambda }_i+i-1$は$i$について狭義単調増加で、$l-j+{\mu }_j$は$j$について狭義単調減少なので、
$$l-{\lambda }_i+i-1=l-j+{\mu }_j$$
なる$i,j$が存在しないことを示せばよい。このような$i,j$が存在したとする。この式を変形すれば、
$$i+j-1={\lambda }_i+{\mu }_j$$
である。ここで、もし$(i,j)$ ($i$行$j$列)が$\lambda$の箱であれば、$i\le {\mu }_j,j\le {\lambda }_i$であり、
$$i+j-1<i+j\le {\lambda }_i+{\mu }_j$$
となる。また、もし$(i,j)$が$\lambda$の箱でなければ、$i>{\mu }_j,j>{\lambda }_i$であり、
$$i+j-1>(i-1)+(j-1)\ge {\lambda }_i+{\mu }_j$$
となる。これは矛盾である。したがって、題意は示された。

フック長公式より、
$$\prod _{\lambda \in c}{h}_{\lambda }(c)=\frac{a_1!a_2!a_3!\cdots a_k!}{\prod _{i<j}(a_i-a_j)}$$
を示せば良い。$k$についての帰納法で示す。そのためには、$a_1$に関わる因子の積が第一行のフック長の積であること：
$$\prod _{j=1}^k{h}_{\lambda }(1,j)=\frac{a_1!}{\prod _{j=2}^k(a_1-a_j)}$$
を示せば十分である。$h_{\lambda }(1,j)=l-j+{\mu }_j$であるから、補題より、
$$\prod _{j=1}^k{h}_{\lambda }(1,j)=\prod _{j=1}^k(l-j+{\mu }_j)=\frac{(k+l-1)!}{\prod _{i=2}^k(l-{\lambda }_i+i-1)}=\frac{a_1!}{\prod _{i=2}^k(a_1-a_i)}$$

定理11より、
$$D(n,k)=\sum _{\lambda }({\mathrm{SYT}}_{\lambda }{)}^2=\sum _{\begin{array}{c}{l}_1+l_2+\cdots +l_k=n+\frac{k(k-1)}{2}\\ l_1>l_2>\cdots >l_k\end{array}}{\left(\frac{n!\prod _{i<j}(l_i-l_j)}{l_1!l_2!\cdots l_k!}\right)}^2$$
ここでシグマの中身の${\left(\frac{n!\prod _{i<j}(l_i-l_j)}{l_1!l_2!\cdots l_k!}\right)}^2$は、$l_1,l_2,\cdots ,l_k$の対称式で、$l_i=l_j,i\ne j$なる$i,j$があるとき$0$なので、

$$D(n,k)=\frac{1}{k!}\sum _{l_1+l_2+\cdots +l_k=n+\frac{k(k-1)}{2}}{\left(\frac{n!\prod _{i<j}(l_i-l_j)}{l_1!l_2!\cdots l_k!}\right)}^2$$