代数的組合せ論の問題

階段型シューア多項式の積表示

$\delta =(4,3,2,1,0)$ とし、5 変数 $x_1,\dots ,x_5$ で考える（$\mu =(2,2,2,2,2)$ は長さ $5$ なので、5 変数に制限しても係数 $K_{\lambda \mu }$ は変わらない）。交代式 $a_{\alpha }=\det {\left(x_i^{{\alpha }_j}\right)}_{1\le i,j\le 5}$ を用いると、ヤコビの双交代式（bialternant）公式による表示
$$s_{\lambda }(x_1,\dots ,x_5)=\frac{a_{\lambda +\delta }}{a_{\delta }}$$
が成り立つ。$\lambda =(4,3,2,1,0)=\delta$ なので $\lambda +\delta =2\delta$ で、
$$a_{2\delta }=\det \left((x_i^2{)}^{5-j}\right)=\prod _{i<j}(x_i^2-x_j^2),a_{\delta }=\det \left(x_i^{5-j}\right)=\prod _{i<j}(x_i-x_j).$$
よって
$$s_{(4,3,2,1)}(x_1,\dots ,x_5)=\prod _{1\le i<j\le 5}(x_i+x_j).$$

係数の組合せ的解釈

右辺の $10$ 個の因子 $(x_i+x_j)$ のそれぞれから $x_i$ か $x_j$ を 1 つ選ぶことは、5 人 $\{1,\dots ,5\}$ の総当たり戦で各試合 $\{i,j\}$ の勝者を決めること（ラベル付きトーナメント）に対応し、選んだ単項式 $x_1^{w_1}\cdots x_5^{w_5}$ の指数 $w_i$ は $i$ の勝ち数である。$K_{\lambda \mu }$ は単項式 $x_1^2{x}_2^2{x}_3^2{x}_4^2{x}_5^2$ の係数に等しいので、
$$K_{(4,3,2,1),(2,2,2,2,2)}=\#\{\text{全員が }2\text{ 勝 }2\text{ 敗のトーナメント}\}.$$

数え上げ

選手 $1$ が勝つ 2 人の選び方は $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ 通りで、どの選び方でも残りの数え方は同じである。$1$ が $a,b$ に勝ち、$c,d$ に負けたとする。残り $\{a,b,c,d\}$ の間の $6$ 試合で必要な勝ち数は $a:2,b:2,c:1,d:1$ である。

$a$ と $b$ の試合で $a$ が勝つ場合: $b$ は残り $c,d$ に 2 勝しなければならないので $b$ が $c,d$ に勝つ。$a$ は $c,d$ のちょうど一方に勝つ。
- $a$ が $c$ に勝つとき: $c$ は $a,b$ に負けたので $d$ に勝つ。すると $d$ は $b,c$ に負けたので $a$ に勝つ。各勝ち数は条件をみたす。
- $a$ が $d$ に勝つとき: 同様に $d$ が $c$ に勝ち、$c$ が $a$ に勝つ。条件をみたす。

よって 2 通り。$b$ が $a$ に勝つ場合も対称に 2 通りで、合計 $4$ 通り。

したがって
$$K_{(4,3,2,1),(2,2,2,2,2)}=6\times 4=24.$$

（参考: 5 頂点の正則トーナメントは同型を除いて巡回型 $i\to i+1,i+2(\mathrm{mod}5)$ のただ 1 つで、自己同型群の位数は $5$ なので、ラベル付きの個数は $5!/5=24$ とも確かめられる。）

内容 $(2,2,2,2,2)$ の半標準ヤング盤は、空の形から大きさ 2 の水平帯を 5 回付け足す列に対応する。$N(\nu ,k)$ を形 $\nu$、内容 $(2^k)$ の SSYT の個数とすると、$N(\lambda ,k)={\sum }_{\nu }N(\nu ,k-1)$（$\lambda /\nu$ は大きさ 2 の水平帯）。\n\n(1) $k=2$: $N((4),2)=N((3,1),2)=N((2,2),2)=1$、他は 0。\n(2) $k=3$（大きさ 6）: 上の漸化式より $N((6))=1,N((5,1))=2,N((4,2))=3,N((4,1,1))=1,N((3,3))=1,N((3,2,1))=2,N((2,2,2))=1$。\n(3) $k=4$（大きさ 8）: $(4,3,2,1)$ から大きさ 2 の水平帯を除くと、各行から高々 1 マスずつ 2 マス除く 6 通り:\n- $(3,2,2,1)$: 隣接する $\rho$ は $(3,2,1),(2,2,2)$ で $2+1=3$\n- $(3,3,1,1)$: $\rho =(3,2,1)$ のみで $2$\n- $(3,3,2)$: $\rho =(3,3),(3,2,1)$ で $1+2=3$\n- $(4,2,1,1)$: $\rho =(4,1,1),(3,2,1)$ で $1+2=3$\n- $(4,2,2)$: $\rho =(4,2),(3,2,1),(2,2,2)$ で $3+2+1=6$\n- $(4,3,1)$: $\rho =(4,2),(4,1,1),(3,3),(3,2,1)$ で $3+1+1+2=7$\n(4) $k=5$: 合計 $3+2+3+3+6+7=24$。\n\n検算: (2) の値は $K_{\rho ,(2,2,2)}$ の既知の値（例えば $K_{(4,2),(2,2,2)}=3$）と一致する。