半標準ヤング盤とコストカ数

形 $λ$ ・内容 $μ$ の半標準ヤング盤を、数 $1, 2, \dots$ を順に水平帯として置いていく方法で数え上げ、コストカ数 $K_{λ μ}$ を求められる

前提

分割数と分割の母関数（大学数学離散数学・組合せ論）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

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

説明

ヤング図形の箱に正の整数を、行は左から右へ広義増加、列は上から下へ狭義増加となるように書き込んだものを半標準ヤング盤といいます。形 $λ$ の図形に、 $1$ を $μ_{1}$ 個、 $2$ を $μ_{2}$ 個、… 書き込む半標準ヤング盤の個数がコストカ数 $K_{λ μ}$ です。この技能では、 $1, 2, 3, \dots$ を順に「同じ列に 2 個入らない帯（水平帯）」として図形に付け足していく見方で、 $K_{λ μ}$ を樹形図で漏れなく数えられるようになります。コストカ数は対称関数や表現論で、ある基本的な量を別の量で書き表すときの係数として現れます。

なぜそうしてよいのか

まず定義を整理します。 $n$ の分割 $λ = (λ_{1} \geq λ_{2} \geq \dots)$ のヤング図形は、第 $i$ 行に $λ_{i}$ 個の箱を左詰めに並べたものです。形 $λ$ の半標準ヤング盤とは、各箱に正の整数を入れ、(i) 各行で左から右へ広義増加（等しくてもよい）、(ii) 各列で上から下へ狭義増加（等しいのは不可）となるものです。数 $i$ がちょうど $μ_{i}$ 個使われているとき、その内容を $μ = (μ_{1}, μ_{2}, \dots)$ といいます（ $μ_{1} + μ_{2} + \dots = n$ ）。

半標準ヤング盤で $k$ 以下の数が入っている箱だけを取り出してみます。行は左から増加するので、各行で $k$ 以下の箱は左に詰まっています。列は上から増加するので、ある箱が $k$ 以下ならその上の箱も $k$ 以下です。したがって取り出した箱の集まり $λ^{(k)}$ はそれ自体ヤング図形で、 $\emptyset = λ^{(0)} \subseteq λ^{(1)} \subseteq \dots \subseteq λ$ と大きくなっていきます。 $λ^{(k)}$ から $λ^{(k - 1)}$ を除いた部分はちょうど数 $k$ の箱で、その個数は $μ_{k}$ です。しかも列の狭義増加より、同じ列に $k$ が 2 個入ることはありません。このように「同じ列に 2 個以上の箱をもたない差」を水平帯と呼びます。

逆に、ヤング図形の列 $\emptyset = ν^{(0)} \subseteq ν^{(1)} \subseteq \dots \subseteq ν^{(ℓ)} = λ$ で、各差 $ν^{(k)} / ν^{(k - 1)}$ が $μ_{k}$ 個の箱からなる水平帯であるものが与えられたら、差の箱に $k$ を書き込むと半標準ヤング盤になります（行の条件は各段階が左詰めであることから、列の条件は水平帯であることから従います）。こうして半標準ヤング盤と「水平帯の付け足し方の列」は 1 対 1 に対応するので、 $K_{λ μ}$ は後者を樹形図で数えれば求まります。実用上は、 $κ \subseteq ν$ について $ν / κ$ が水平帯であることは、不等式 $ν_{1} \geq κ_{1} \geq ν_{2} \geq κ_{2} \geq ν_{3} \geq \dots$ が成り立つことと同じです（第 $i + 1$ 行に足した箱が、第 $i$ 行の新しい箱の真下に来ないための条件）。

手順

形 $λ$ と内容 $μ = (μ_{1}, \dots, μ_{ℓ})$ を確認し、 $∣ λ ∣ = μ_{1} + \dots + μ_{ℓ}$ であることを確かめる
$1$ を置く: $1$ はすべて第 1 行に入るので $ν^{(1)} = (μ_{1})$ （ $μ_{1} > λ_{1}$ なら $K_{λ μ} = 0$ ）
$k = 2, 3, \dots$ の順に、いまの図形 $κ = ν^{(k - 1)}$ に $μ_{k}$ 個の箱を付け足した図形 $ν$ で、(a) ヤング図形である、(b) $ν \subseteq λ$ 、(c) $ν_{1} \geq κ_{1} \geq ν_{2} \geq κ_{2} \geq \dots$ （水平帯）を満たすものをすべて挙げ、樹形図で枝分かれさせる
最後の数 $ℓ$ を置いた時点で $λ$ に到達した枝の本数を数える。それが $K_{λ μ}$

例題

形 $λ = (3, 2, 1)$ 、内容 $μ = (2, 2, 1, 1)$ （ $1$ を 2 個、 $2$ を 2 個、 $3$ を 1 個、 $4$ を 1 個使う）の半標準ヤング盤の個数、すなわちコストカ数 $K_{(3, 2, 1), (2, 2, 1, 1)}$ を求めよ。

例題の解答

手順 1: $∣ λ ∣ = 6 = 2 + 2 + 1 + 1$ 。

手順 2: $1$ を 2 個置くと $ν^{(1)} = (2)$ 。

手順 3（ $k = 2$ , 2 個）: $(2)$ に 2 箱足して $λ = (3, 2, 1)$ に収まるヤング図形は $(3, 1)$ , $(2, 2)$ , $(2, 1, 1)$ 。水平帯の条件を調べると、 $(3, 1)$ : $3 \geq 2 \geq 1 \geq 0$ で可。 $(2, 2)$ : $2 \geq 2 \geq 2 \geq 0$ で可。 $(2, 1, 1)$ : $2 \geq 2 \geq 1 \geq 0 \geq 1$ が不成立（第 2 行と第 3 行の第 1 列に $2$ が縦に並ぶ）で不可。よって $ν^{(2)} = (3, 1)$ または $(2, 2)$ 。

手順 3（ $k = 3$ , 1 個）: 1 箱だけ足すときは、同じ列に 2 個入ることはないので、 $λ$ に収まるヤング図形になればよい。 $(3, 1)$ からは $(3, 2)$ , $(3, 1, 1)$ 。 $(2, 2)$ からは $(3, 2)$ , $(2, 2, 1)$ 。

手順 3（ $k = 4$ , 1 個）: $λ = (3, 2, 1)$ に到達させる。 $(3, 2) \to (3, 2, 1)$ 、 $(3, 1, 1) \to (3, 2, 1)$ 、 $(2, 2, 1) \to (3, 2, 1)$ はいずれも 1 箱を足すだけで可能。

手順 4: 枝は
$(2) \to (3, 1) \to (3, 2) \to λ$ 、 $(2) \to (3, 1) \to (3, 1, 1) \to λ$ 、 $(2) \to (2, 2) \to (3, 2) \to λ$ 、 $(2) \to (2, 2) \to (2, 2, 1) \to λ$ の 4 本。
対応する盤は（行を / で区切って） $112/23/4$ 、 $112/24/3$ 、 $113/22/4$ 、 $114/22/3$ 。

よって $K_{(3, 2, 1), (2, 2, 1, 1)} = 4$ 。

答え: $4$

よくある誤り

同じ数を同じ列に縦に並べてしまう誤り。例題で $(2)$ から $(2, 1, 1)$ へ進めると第 1 列に $2$ が 2 個縦に並び、列の狭義増加に反する。正しくは $ν_{1} \geq κ_{1} \geq ν_{2} \geq κ_{2} \geq \dots$ を確かめて水平帯だけを残す
途中の図形がヤング図形でなくてもよいとしてしまう誤り。たとえば $(2)$ の第 2 行の第 2 列だけに箱を足すような左詰めでない形は作れない。 $k$ 以下の数の箱は必ずヤング図形 $λ^{(k)}$ をなし、 $λ^{(k)} \subseteq λ$ でなければならない
$1$ を第 2 行以下にも置けるとしてしまう誤り。第 2 行の箱の上には必ず箱があり、それは $1$ より大きくなれないので、 $1$ はすべて第 1 行の左端に入る。正しくは $ν^{(1)} = (μ_{1})$ と 1 通りに決まる
半標準ヤング盤の個数を、各数を 1 個ずつ使う標準ヤング盤の個数と混同する誤り。 $λ = (3, 2, 1)$ の標準ヤング盤は $16$ 個だが、それは内容 $(1, 1, 1, 1, 1, 1)$ のときの値で、内容 $(2, 2, 1, 1)$ では正しくは $K_{λ μ} = 4$

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

入口の問題

難易度 1（大学院の講義の例題レベル）
分割 $λ$ のヤング図形（第 $i$ 行に $λ_{i}$ 個の箱を左詰めで並べ、第 1 行を一番上にかく）の各箱に正の整数を 1 つずつ書き入れたもので、各行では左から右へ広義単調増加、各列では上から下へ狭義単調増加となっているものを、形 $λ$ の半標準ヤング盤という。数 $i$ がちょうど $μ_{i}$ 回現れるとき、その内容は $μ = (μ_{1}, μ_{2}, \dots)$ であるという。形 $λ$ ・内容 $μ$ の半標準ヤング盤の個数をコストカ数 $K_{λ μ}$ という。
$λ = (4, 2)$ , $μ = (2, 2, 2)$ のとき、コストカ数 $K_{λ μ}$ を求めよ。

この技能を使う問題

この技能の次に学べること

フック内容公式（大学院数学代数的組合せ論）
シューア関数とコストカ数による展開（大学院数学代数的組合せ論）