RSK 対応と増加・減少部分列

ロビンソン・シェンステッド対応で置換を同じ形の標準ヤング盤の組に移し、最長増加部分列の長さが $λ_{1}$ 、最長減少部分列の長さが $ℓ (λ)$ になること（シェンステッドの定理）を使って、増加・減少部分列の長さに条件のある置換の個数を $\sum_{λ} (f^{λ})^{2}$ として求められる

前提

対称群の既約表現の次元（フック長公式）（大学院数学表現論）

この技能までの道筋（94 技能）

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

三角形の角の大きさ（算数平面図形）
対頂角と平行線の同位角・錯角（中学数学平面図形）
三角形の外角と角の組み合わせ（中学数学平面図形）
小数の四則計算（算数計算と数のきまり）
分数のたし算・ひき算（算数計算と数のきまり）
分数のかけ算・わり算（算数計算と数のきまり）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
1 次方程式の解き方（中学数学方程式）
二等辺三角形の角（中学数学平面図形）
平行四辺形と特別な四角形の性質（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
三平方の定理（中学数学相似と三平方の定理）
乗法公式による展開（中学数学数と式）
折り返した図形の角と長さ（中学数学平面図形）
三平方の定理と平面図形（中学数学相似と三平方の定理）
ベクトルの演算と成分（数学C ベクトル）
行列の和・積と 2 次の逆行列（大学数学線形代数）
掃き出し法と連立 1 次方程式（大学数学線形代数）
行列の階数と解の存在（大学数学線形代数）
ベクトル空間・一次独立・基底・次元（大学数学線形代数）
円の周の長さと面積（算数平面図形）
おうぎ形の弧の長さと面積（算数平面図形）
弧の長さからおうぎ形の中心角と面積を求める（中学数学平面図形）
特別な直角三角形の辺の比（中学数学相似と三平方の定理）
弧度法と単位円による三角関数（数学II 三角関数）
加法定理と 2 倍角・半角・積和の公式（数学II 三角関数）
線形変換と行列（大学数学線形代数）
核と像と次元定理（大学数学線形代数）
掃き出し法による逆行列（大学数学線形代数）
基底の変換と表現行列（大学数学線形代数）
最大公約数と最小公倍数（算数整数の性質）
最大公約数と最小公倍数（数学A 整数の性質）
因数分解（中学数学数と式）
文字式で表した整数の性質（中学数学数と式）
余りによる整数の分類（数学A 整数の性質）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
合同式（数学A 整数の性質）
群の位数と元の位数（大学数学代数学）
群の表現と指標（大学院数学表現論）
比例・反比例の式とグラフ（中学数学関数）
関数 $y = a x^{2}$ の式と変域（中学数学関数）
平方完成と 2 次関数のグラフ（数学I 2次関数）
複素数と 2 次方程式の虚数解（数学II 複素数と方程式）
極形式と積・商（数学C 複素数平面）
ド・モアブルの定理（数学C 複素数平面）
方程式 $z^{n} = a$ の解（数学C 複素数平面）
1 次元表現とアーベル化（大学院数学表現論）
置換の巡回置換分解と位数（大学数学代数学）
順列・円順列・重複順列（数学A 場合の数と確率）
対称群の共役類（大学数学代数学）
二面体群の共役類（大学数学代数学）
既約表現の個数と次元（大学院数学表現論）
組合せ（数学A 場合の数と確率）
同じものを含む順列・重複組合せ（数学A 場合の数と確率）
3 次式までの展開と因数分解（数学I 数と式）
微分係数と導関数の定義（数学II 微分法と積分法）
多項式の微分（数学II 微分法と積分法）
2 次不等式（数学I 2次関数）
剰余の定理・因数定理と高次方程式（数学II 複素数と方程式）
増減表と極値（数学II 微分法と積分法）
等間隔にならんだ数の和（算数計算と数のきまり）
等差・等比数列の和と Σ （数学B 数列）
数列の極限（数学III 極限）
関数の極限（数学III 極限）
関数の連続性と中間値の定理（数学III 極限）
平均値の定理（数学III 微分法）
積と商の微分（数学III 微分法）
第 2 次導関数とグラフの凹凸（数学III 微分法）
合成関数の微分（数学III 微分法）
$sin x / x$ の極限（数学III 極限）
三角関数の導関数（数学III 微分法）
根号の乗除と加減（中学数学数と式）
指数の拡張と指数関数（数学II 指数関数と対数関数）
対数の定義と性質（数学II 指数関数と対数関数）
自然対数の底 $e$ （数学III 極限）
指数関数・対数関数の導関数（数学III 微分法）
増減・凹凸・漸近線とグラフ（数学III 微分法）
テイラー展開（大学数学微分積分）
無限等比級数と無限級数（数学III 極限）
べき級数と収束半径（大学数学微分積分）
母関数と係数の取り出し（大学数学離散数学・組合せ論）
分割数と分割の母関数（大学数学離散数学・組合せ論）
対称群の既約表現の次元（フック長公式）（大学院数学表現論）

説明

ロビンソン・シェンステッド（RS）対応は、 $S_{n}$ の置換 $w$ を、同じ形 $λ ⊢ n$ をもつ標準ヤング盤の組 $(P (w), Q (w))$ に 1 対 1 に移す対応です（RSK 対応を置換に制限したもの）。シェンステッドの定理により、 $w$ の最長増加部分列の長さは $λ_{1}$ （第 1 行の長さ）、最長減少部分列の長さは $ℓ (λ)$ （行の個数）に等しくなります。これを使うと「最長増加部分列の長さが $a$ 以下」「最長減少部分列の長さがちょうど $b$ 」のような条件を形 $λ$ の条件に言い換え、その条件を満たす置換の個数を $\sum_{λ} (f^{λ})^{2}$ として、フック長公式で計算できます。

なぜそうしてよいのか

置換 $w = w_{1} w_{2} \dots w_{n}$ （1 行表記）に対し、空の盤から始めて $w_{1}, w_{2}, \dots, w_{n}$ を順に「挿入」します。数 $x$ を第 1 行に挿入するときは、 $x$ より大きい最小の数があればそれを $x$ で置き換え、追い出された数を第 2 行に同じ規則で挿入し、以下同様に続けます（追い出す数がなければ行の右端に置いて終わり）。こうしてできる盤 $P (w)$ は各行・各列が増加し、 $k$ 回目の挿入で新しく増えた箱に $k$ を書き込んだ盤 $Q (w)$ は同じ形の標準ヤング盤になります。 $Q$ を見れば最後に増えた箱がわかるので、そこから逆向きに追い出しをたどって $w_{n}$ を取り出せ、これを繰り返せば $w$ が復元できます。逆に同じ形の標準ヤング盤の任意の組からも同じ操作で置換が得られるので、RS 対応は $S_{n}$ と ${(P, Q) : P, Q は形 λ の標準ヤング盤, λ ⊢ n}$ の全単射です。特に $n! = \sum_{λ ⊢ n} (f^{λ})^{2}$ が成り立ち、形 $λ$ に移る置換はちょうど $(f^{λ})^{2}$ 個あります。

第 1 行の長さが最長増加部分列の長さになる理由は次のとおりです。 $w_{1}, \dots, w_{k}$ まで挿入した時点で、第 1 行の左から $j$ 番目の数は「 $w_{1} \dots w_{k}$ の中の長さ $j$ の増加部分列の末尾として取れる値の最小値」になっています。実際、新しい数 $x$ を挿入するとき、 $x$ より小さい数が第 1 行に $j - 1$ 個あれば、それらのうち $j - 1$ 番目を末尾とする長さ $j - 1$ の増加部分列に $x$ をつなげて長さ $j$ の増加部分列が作れ、末尾の最小値は $x$ に更新されます。これが「 $x$ より大きい最小の数を $x$ で置き換える（なければ右端に置く）」操作そのものです。したがって第 1 行の長さ $λ_{1}$ は最長増加部分列の長さに等しくなります（ただし第 1 行に並ぶ数の列そのものが $w$ の部分列とは限りません）。

また、シェンステッドは $w$ を逆順に読んだ置換 $w^{rev} = w_{n} \dots w_{1}$ の挿入盤が $P (w)$ の転置になることを示しました。 $w$ の減少部分列は $w^{rev}$ の増加部分列なので、最長減少部分列の長さは転置した形の第 1 行の長さ、すなわち $λ$ の行の個数 $ℓ (λ)$ になります。例えば $w = 31425$ を挿入すると $P = 13245$ （形 $(3, 2)$ ）で、実際に最長増加部分列 $345$ の長さは $3 = λ_{1}$ 、最長減少部分列 $31$ の長さは $2 = ℓ (λ)$ です。

手順

置換についての条件（最長増加部分列の長さ $= a$ や $\leq a$ 、最長減少部分列の長さ $= b$ や $\leq b$ ）を、シェンステッドの定理で形の条件（ $λ_{1} = a$ や $λ_{1} \leq a$ 、 $ℓ (λ) = b$ や $ℓ (λ) \leq b$ ）に言い換える
$n$ の分割のうち、その条件を満たす $λ$ をもれなく列挙する
各 $λ$ についてフック長公式 $f^{λ} = \frac{n !}{\prod _{(i, j) \in λ} h ( i , j )}$ で標準ヤング盤の個数を求める
RS 対応が全単射で、形 $λ$ に移る置換が $(f^{λ})^{2}$ 個あることから、求める個数を $λ \sum (f^{λ})^{2}$ として計算する

例題

$S_{5}$ の置換 $w$ （1 行表記 $w_{1} w_{2} w_{3} w_{4} w_{5}$ ）のうち、最長増加部分列の長さが $3$ であり、かつ最長減少部分列の長さも $3$ であるものの個数を求めよ。

例題の解答

【手順 1】RS 対応で $w$ が形 $λ ⊢ 5$ の組 $(P, Q)$ に移るとき、シェンステッドの定理より最長増加部分列の長さは $λ_{1}$ 、最長減少部分列の長さは $ℓ (λ)$ である。よって条件は $λ_{1} = 3$ かつ $ℓ (λ) = 3$ と言い換えられる。

【手順 2】 $5$ の分割は $(5), (4, 1), (3, 2), (3, 1, 1), (2, 2, 1), (2, 1, 1, 1), (1, 1, 1, 1, 1)$ の 7 個である。このうち $λ_{1} = 3$ なのは $(3, 2), (3, 1, 1)$ で、さらに行の個数が $3$ なのは $(3, 1, 1)$ だけである。

【手順 3】 $λ = (3, 1, 1)$ のフック長は、第 1 行が左から $5, 2, 1$ 、第 1 列の 2 段目・3 段目が $2, 1$ である。よって
$f^{(3, 1, 1)} = \frac{5 !}{5 \cdot 2 \cdot 1 \cdot 2 \cdot 1} = \frac{120}{20} = 6.$

【手順 4】RS 対応は全単射で、形 $(3, 1, 1)$ に移る置換は $P, Q$ をそれぞれ $6$ 通り選べるので $(f^{(3, 1, 1)})^{2} = 6^{2} = 36$ 個ある。

したがって求める個数は $36$ である。

答え: $36$

よくある誤り

形 $λ$ に移る置換の個数を $f^{λ}$ としてしまう誤り。置換は盤の組 $(P, Q)$ に対応するので、正しくは $(f^{λ})^{2}$ 個（例えば $λ = (3, 1, 1)$ なら $6$ ではなく $36$ ）。
最長減少部分列の長さを $λ_{1}$ 、最長増加部分列の長さを $ℓ (λ)$ と取り違える誤り。正しくは増加が第 1 行の長さ $λ_{1}$ 、減少が行の個数 $ℓ (λ)$ （例: $w = 12345$ は $λ = (5)$ で増加部分列の長さ $5$ ）。
「長さが $a$ 以下」と「ちょうど $a$ 」を混同する誤り。例えば $S_{5}$ で最長増加部分列の長さが $2$ 以下なら $λ = (2, 2, 1), (2, 1, 1, 1), (1^{5})$ をすべて足して $5^{2} + 4^{2} + 1^{2} = 42$ だが、ちょうど $2$ なら $(1^{5})$ を除いて $41$ 。
挿入後の $P (w)$ の第 1 行に並ぶ数がそのまま最長増加部分列だとしてしまう誤り。一致するのは長さだけで、例えば $w = 231$ では $P = 123$ の第 1 行 $1, 3$ は $w$ の部分列ではない（最長増加部分列は $23$ ）。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（大学院の講義の例題レベル）
${1, 2, \dots, 6}$ の置換 $w$ を語 $w (1) w (2) \dots w (6)$ とみなす。添字 $1 \leq i_{1} < i_{2} < \dots < i_{k} \leq 6$ に対して $w (i_{1}) < w (i_{2}) < \dots < w (i_{k})$ となるとき $w (i_{1}) w (i_{2}) \dots w (i_{k})$ を長さ $k$ の増加部分列といい、 $w (i_{1}) > w (i_{2}) > \dots > w (i_{k})$ となるとき長さ $k$ の減少部分列という。
最長増加部分列の長さがちょうど $3$ であり、かつ最長減少部分列の長さもちょうど $3$ であるような置換 $w \in S_{6}$ の個数を求めよ。

RSK 対応と増加・減少部分列

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題