代数的組合せ論の問題

ステップ 1（RSK 対応とシェンステッドの定理） ロビンソン–シェンステッド（RSK）対応は、$\{1,\dots ,n\}$ の置換 $\sigma$ と、同じ形 $\lambda ⊢n$ の標準ヤング盤の組 $(P,Q)$ との全単射を与える。さらにシェンステッドの定理により、
- $\sigma$ の最長増加部分列の長さ $={\lambda }_1$（第 1 行の長さ）
- $\sigma$ の最長減少部分列の長さ $={\lambda }_1^{\prime }$（行の数 $\ell (\lambda )$）

が成り立つ。形 $\lambda$ の標準ヤング盤の個数を $f^{\lambda }$ とすると、求める個数は
$$N=\sum _{\begin{array}{c}\lambda ⊢7\\ {\lambda }_1\le 3,\ell (\lambda )\le 3\end{array}}(f^{\lambda }{)}^2$$
である。

ステップ 2（該当する分割） $3\times 3$ の正方形に収まる $7$ の分割は、正方形 $(3,3,3)$ から $2$ 個の箱を取り除いて分割になるものである。取り除き方は $(3,3,1)$ と $(3,2,2)$ の $2$ 通りしかない（$(3,3,3)$ から角を順に $2$ つ取る）。

ステップ 3（フック長公式） $\lambda =(3,3,1)$ の各箱のフック長は
$$\begin{array}{ccc}5& 3& 2\\ 4& 2& 1\\ 1& & \end{array}$$
であるから、フック長公式より
$$f^{(3,3,1)}=\frac{7!}{5\cdot 3\cdot 2\cdot 4\cdot 2\cdot 1\cdot 1}=\frac{5040}{240}=21.$$
$(3,2,2)$ は $(3,3,1)$ の共役分割であり、フック長の多重集合は共役で変わらないので $f^{(3,2,2)}=21$。

（検算：標準ヤング盤で $7$ が入る箱は角なので $f^{(3,3,1)}=f^{(3,2,1)}+f^{(3,3)}=16+5=21$、$f^{(3,2,2)}=f^{(3,2,1)}+f^{(2,2,2)}=16+5=21$ となり一致する。）

ステップ 4（合計）
$$N=21^2+21^2=441+441=882.$$

Robinson–Schensted 対応により、$S_7$ の置換は同じ形 $\lambda ⊢7$ の標準ヤング盤の組 $(P,Q)$ と 1 対 1 に対応し、最長増加部分列の長さは ${\lambda }_1$、最長減少部分列の長さは $\lambda$ の行数 $\ell (\lambda )$ に等しい（Schensted の定理）。したがって長さ 4 の増加部分列も減少部分列ももたないことは ${\lambda }_1\le 3$ かつ $\ell (\lambda )\le 3$ と同値で、求める個数は
$$\sum _{\lambda ⊢7,{\lambda }_1\le 3,\ell (\lambda )\le 3}(f^{\lambda }{)}^2.$$

$3\times 3$ の枠に入る 7 の分割は、各部分が 3 以下で高々 3 個の部分をもつものなので $(3,3,1)$ と $(3,2,2)$ のみ（$(3,3,1)$ を転置すると $(3,2,2)$）。

$(3,3,1)$ のフック長は、1 行目 $5,3,2$、2 行目 $4,2,1$、3 行目 $1$。積は $5\cdot 3\cdot 2\cdot 4\cdot 2\cdot 1\cdot 1=240$ なので $f^{(3,3,1)}=7!/240=5040/240=21$。転置でも $f$ は変わらないので $f^{(3,2,2)}=21$。

個数は $21^2+21^2=441+441=882$。

検算：$(3,2,2)$ のフック長は 1 行目 $5,4,1$、2 行目 $3,2$、3 行目 $2,1$ で、積は $5\cdot 4\cdot 1\cdot 3\cdot 2\cdot 2\cdot 1=240$、$5040/240=21$ で一致する。