この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

代数的組合せ論の問題

難易度 4大学院入試の難問レベル大学院数学代数的組合せ論

$S_{10}$ を ${1, 2, \dots, 10}$ の置換全体とする。置換 $w \in S_{10}$ を語 $w (1) w (2) \dots w (10)$ とみなし、 $1 \leq i_{1} < i_{2} < \dots < i_{k} \leq 10$ かつ $w (i_{1}) < w (i_{2}) < \dots < w (i_{k})$ となる $k$ の最大値を $w$ の最長増加部分列の長さ、 $w (i_{1}) > w (i_{2}) > \dots > w (i_{k})$ となる $k$ の最大値を最長減少部分列の長さとよぶ。

$w^{2} = id$ をみたす $w \in S_{10}$ （恒等置換も含む）のうち、最長増加部分列の長さと最長減少部分列の長さがともにちょうど $4$ であるものの個数を求めよ。

この問題で使うもの

RSK 対応と増加・減少部分列（説明と入口の問題）
対称群の既約表現の次元（フック長公式）（説明と入口の問題）

この問題を解けるようになるまで（95 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

ロビンソン・シェンステッド対応で、対合と標準ヤング盤の対応、および最長増加・減少部分列の長さがヤング図形のどこに現れるかを考える。

ヒント 2

対合 $w$ は $P (w) = Q (w)$ をみたし、最長増加部分列の長さは $λ_{1}$ 、最長減少部分列の長さは $λ$ の行数に等しい。したがって答えは $λ_{1} = 4, ℓ (λ) = 4$ をみたす $λ ⊢ 10$ についての $f^{λ}$ の和。

ヒント 3

該当する分割は $(4, 4, 1, 1), (4, 3, 2, 1), (4, 2, 2, 2)$ 。それぞれフック長公式で $f^{λ}$ を求める（ $(4, 4, 1, 1)$ と $(4, 2, 2, 2)$ は互いに共役）。

答えと解説

答えを見る

1368

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

RSK 対応とシェンステッドの定理

ロビンソン・シェンステッド対応 $w \mapsto (P (w), Q (w))$ は、 $S_{n}$ と「同じ形 $λ ⊢ n$ の標準ヤング盤の組 $(P, Q)$ 」全体との全単射である。さらに
- $Q (w^{- 1}) = P (w)$ , $P (w^{- 1}) = Q (w)$ （シュッツェンベルジェの対称性）であるから、 $w$ が対合（ $w = w^{- 1}$ ）であることと $P (w) = Q (w)$ は同値。したがって対合 $w \in S_{n}$ と形 $λ ⊢ n$ の標準ヤング盤 $P$ は一対一に対応する。
- シェンステッドの定理により、 $w$ の最長増加部分列の長さは $λ_{1}$ （第 1 行の長さ）、最長減少部分列の長さは $ℓ (λ) = λ_{1}^{'}$ （第 1 列の長さ）である。

よって求める個数は
$λ ⊢ 10 λ_{1} = 4, ℓ (λ) = 4 \sum f^{λ}$
（ $f^{λ}$ は形 $λ$ の標準ヤング盤の個数）である。

該当する分割　 $λ_{1} = 4$ で行数がちょうど $4$ の $10$ の分割は、残り $3$ 行に $6$ 個の箱を各行 $1$ 以上 $4$ 以下で単調非増加に配るものなので
$(4, 4, 1, 1), (4, 3, 2, 1), (4, 2, 2, 2)$
の $3$ つである。

フック長公式 $f^{λ} = \frac{n !}{\prod h ( c )}$ で計算する（ $10! = 3628800$ ）。
- $λ = (4, 3, 2, 1)$ ：フック長は第 1 行 $7, 5, 3, 1$ 、第 2 行 $5, 3, 1$ 、第 3 行 $3, 1$ 、第 4 行 $1$ 。積は $7 \cdot 5 \cdot 3 \cdot 5 \cdot 3 \cdot 3 = 4725$ で $f^{λ} = 3628800/4725 = 768$ 。
- $λ = (4, 4, 1, 1)$ （共役は $(4, 2, 2, 2)$ ）：フック長は第 1 行 $7, 4, 3, 2$ 、第 2 行 $6, 3, 2, 1$ 、第 3 行 $2$ 、第 4 行 $1$ 。積は $168 \cdot 36 \cdot 2 = 12096$ で $f^{λ} = 3628800/12096 = 300$ 。
- $λ = (4, 2, 2, 2)$ は $(4, 4, 1, 1)$ の共役なので、フック長の多重集合が同じで $f^{λ} = 300$ 。

以上より
$768 + 300 + 300 = 1368.$

別解

RSK 対応により $S_{n}$ の置換は同じ形 $λ ⊢ n$ の標準タブロー対 $(P, Q)$ と一対一に対応し、最長増加部分列の長さは $λ_{1}$ 、最長減少部分列の長さは $λ$ の行数 $ℓ (λ)$ に等しい。また $w^{- 1}$ には $(Q, P)$ が対応するので、 $w^{2} = id$ （ $w = w^{- 1}$ ）は $P = Q$ と同値であり、形 $λ$ の対合の個数は標準タブローの個数 $f^{λ}$ に等しい。

よって求める個数は $\sum f^{λ}$ （ $λ ⊢ 10$ , $λ_{1} = 4$ , $ℓ (λ) = 4$ ）。

$λ = (4, a, b, c)$ , $4 \geq a \geq b \geq c \geq 1$ , $a + b + c = 6$ を満たすのは $(a, b, c) = (4, 1, 1), (3, 2, 1), (2, 2, 2)$ 、すなわち $λ = (4, 4, 1, 1), (4, 3, 2, 1), (4, 2, 2, 2)$ の 3 つ。

フック長公式 $f^{λ} = 10! / \prod h$ で計算する。
- $(4, 3, 2, 1)$ : フック長の積は $7 \cdot 5 \cdot 3 \cdot 1 \cdot 5 \cdot 3 \cdot 1 \cdot 3 \cdot 1 \cdot 1 = 4725$ なので $f = 3628800/4725 = 768$ 。
- $(4, 2, 2, 2)$ : フック長は第1行 $7, 6, 2, 1$ 、第2行 $4, 3$ 、第3行 $3, 2$ 、第4行 $2, 1$ 。積は $84 \cdot 12 \cdot 6 \cdot 2 = 12096$ なので $f = 3628800/12096 = 300$ 。
- $(4, 4, 1, 1)$ は $(4, 2, 2, 2)$ の共役なので $f = 300$ 。

合計 $768 + 300 + 300 = 1368$ 。

検算: 共役の対称性（ $λ \leftrightarrow λ^{'}$ で $f$ が不変、 $(4, 3, 2, 1)$ は自己共役）と整合している。また $(4, 3, 2, 1)$ の $f^{λ} = 768$ は階段形の既知の値と一致する。

代数的組合せ論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題