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

$w'$が$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|123567\ 4),\quad (89\ 5|123467) $$
である。(行の区切りを$|$で示している。)まず、
$$ (89|123\textcolor{red}{5}\underline{67\ \textcolor{blue}{4}}) \to (89|123\underline{\textcolor{red}{5}6\textcolor{blue}{4}}7) \to (89|123\textcolor{red}{5}\textcolor{blue}{4}67) $$
のように、バンプする数字$a_1=4$を$a_{2}=5$のすぐ後ろまで移動させることができる。これらの変換はすべて、
$$ xyz \to xzy\quad (y>x>z) $$
の形をしたクヌース変換である。次に、
$$ (89|12\underline{3\textcolor{red}{5}\textcolor{blue}{4}}67) \to (89|1\underline{2\textcolor{red}{5}3}\textcolor{blue}{4}67) \to (89|\underline{1\textcolor{red}{5}2}3\textcolor{blue}{4}67) \to (89|\textcolor{red}{5}123\textcolor{blue}{4}67) = (89\ \textcolor{red}{5}|123\textcolor{blue}{4}67) $$
のように、$a_{2} = 5$を$2$行目の右端まで移動させることができる。これらの変換はすべて、
$$ xyz \to yxz\quad (y>z>x) $$
の形をしたクヌース変換である。このように、バンプアルゴリズムは、対応する数字列のクヌース変換だけで実現できることがわかった。

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

としよう。$w'$は
$$ w' = (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') \geq l$である。また、$w'$の部分列を作る際、$P(w)$の同じ行から$2$つ以上の数字を選ぶと減少部分列とならないので、$L(w') \leq l$である。以上より、$L(w) = L(w') = 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^* :=n+1-k$に置き換え、それを$180$度回転させた図形を$Q^*$とする。$P$の右に$Q^*$をはめ込むと、$2\times n$の長方形の形をした標準盤$T$を得ることができる。

逆に$2\times n$の長方形の形をした標準盤$T$が与えられた時、$T$のうち$n$以下の数字からなる部分$P$とそれ以外の部分$Q^*$とに分ける。$Q^*$の各数字$k$を$k^*$に置き換え、それを$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 \leq \mu_j, j \leq \lambda_i$であり、
$$ i+j -1 < i+j \leq \lambda_i + \mu_j $$
となる。また、もし$(i,j)$が$\lambda$の箱でなければ、$i > \mu_j, j > \lambda_i$であり、
$$ i+j -1 > (i - 1) + (j - 1) \geq \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_{\substack{l_1+l_2+\cdots+l_k=n+\frac{k(k-1)}{2} \\ l_1 >l_2>\cdots > l_k}} \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 \neq 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 $$