代数的組合せ論の問題

難易度 2大学院の講義の演習問題レベル証明問題大学院数学代数的組合せ論

$a, b$ を $a \geq b \geq 0$ をみたす整数とし、 $n = a + b \geq 1$ とする。ヤング図形 $λ = (a, b)$ とは、第 $1$ 行の第 $1$ 列から第 $a$ 列までの $a$ 個の箱と、第 $2$ 行の第 $1$ 列から第 $b$ 列までの $b$ 個の箱からなる図形とする（ $b = 0$ のときは第 $1$ 行だけ。 $a \geq b$ なので、第 $2$ 行の各箱の真上には第 $1$ 行の箱がある）。 $λ$ の標準ヤング盤とは、 $λ$ の $n$ 個の箱に $1, 2, \dots, n$ を $1$ つずつ書き入れたもので、次の 2 条件をみたすものをいう。ここで第 $i$ 行第 $j$ 列の箱に書かれた数を $T (i, j)$ と書く。

行の条件: $T (1, 1) < T (1, 2) < \dots < T (1, a)$ かつ $T (2, 1) < T (2, 2) < \dots < T (2, b)$ 。
列の条件: $1 \leq j \leq b$ をみたすすべての $j$ について $T (1, j) < T (2, j)$ 。

$λ = (a, b)$ の標準ヤング盤の個数を $f^{(a, b)}$ とするとき、
$f^{(a, b)} = (b n) - (b - 1 n)$
が成り立つことを証明せよ。ただし $(- 1 n) = 0$ とし、フック長公式は用いないものとする。

この問題で使うもの

組合せ（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

標準ヤング盤を、各数 $k$ が第 $1$ 行・第 $2$ 行のどちらにあるかを記録した $U$ / $D$ の文字列に置き換え、条件をみたす文字列を数えましょう。

ヒント 2

列の条件 $T (1, j) < T (2, j)$ は「どの先頭部分でも $U$ の個数が $D$ の個数以上」と同値になります。全体 $(b n)$ から、この条件をみたさない文字列の個数を引けばよいです。

ヒント 3

条件をみたさない文字列では、初めて $D$ が $U$ より $1$ 個多くなる位置があります。そこまでの $U$ と $D$ を入れ替えると、 $U$ が $a + 1$ 個・ $D$ が $b - 1$ 個の文字列になります。この操作が逆にたどれることを確かめましょう。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

標準ヤング盤と、 $U$ が $a$ 個・ $D$ が $b$ 個の文字列との対応を作り、行の条件から書き入れが文字列で一意に決まることを示している（2 点）
列の条件が「すべての先頭部分で $U$ の個数 $\geq$ $D$ の個数」と同値であることを、両方向とも示している（3 点）
条件をみたさない文字列について、初めて $D$ が $1$ 個多くなる位置までの $U$ ・ $D$ の入れ替え（鏡映）により、 $U$ が $a + 1$ 個・ $D$ が $b - 1$ 個の文字列に写している（2 点）
逆写像を構成し（入れ替える位置が存在することや、入れ替えの位置が保たれることを含めて）全単射であることを確かめている（2 点）
全体 $(b n)$ から $(b - 1 n)$ を引いて結論し、 $b = 0$ の場合にも成り立つことを確認している（1 点）

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

模範解答を読む

ステップ 1（標準ヤング盤と文字列の対応）. 行の条件をみたす書き入れ $T$ に対し、長さ $n$ の文字列 $w = w_{1} w_{2} \dots w_{n}$ を「 $k$ が第 $1$ 行にあれば $w_{k} = U$ 、第 $2$ 行にあれば $w_{k} = D$ 」で定める。 $w$ は $U$ を $a$ 個、 $D$ を $b$ 個含む。逆に、そのような文字列 $w$ が与えられると、行の条件により、第 $1$ 行には $w_{k} = U$ である $k$ を小さい順に左から、第 $2$ 行には $w_{k} = D$ である $k$ を小さい順に左から並べるしかなく、そうすれば行の条件がみたされる。よって、行の条件をみたす書き入れ全体と、 $U$ が $a$ 個・ $D$ が $b$ 個の文字列全体とは $T \mapsto w$ で全単射に対応する。この対応で、 $T (1, j)$ は $w$ の $j$ 番目の $U$ の位置、 $T (2, j)$ は $j$ 番目の $D$ の位置である。

ステップ 2（列の条件の言い換え）. $0 \leq t \leq n$ に対し、先頭部分 $w_{1} \dots w_{t}$ に含まれる $U$ , $D$ の個数を $u (t)$ , $d (t)$ とする（ $u (0) = d (0) = 0$ ）。列の条件が
$すべての t (0 \leq t \leq n) について u (t) \geq d (t) (1)$
と同値であることを示す。

$1 \leq j \leq b$ について $p_{j} = T (2, j)$ とおくと $d (p_{j}) = j$ であり、 $w_{p_{j}} = D$ なので $u (p_{j}) = u (p_{j} - 1)$ である。 $j \leq b \leq a$ なので $j$ 番目の $U$ は存在し、その位置 $T (1, j)$ が $p_{j}$ より小さいことは、位置 $p_{j} - 1$ までに $U$ が $j$ 個以上あることと同値である。よって
$T (1, j) < T (2, j) ⟺ u (p_{j} - 1) \geq j ⟺ u (p_{j}) \geq d (p_{j}) .$

$(1)$ を仮定すると、 $t = p_{j}$ として $u (p_{j}) \geq d (p_{j})$ なので、すべての $j$ で $T (1, j) < T (2, j)$ である。
逆に、すべての $j$ （ $1 \leq j \leq b$ ）で $u (p_{j}) \geq j$ と仮定する。任意の $t$ について $j = d (t)$ とおく。 $j = 0$ なら $u (t) \geq 0 = d (t)$ 。 $j \geq 1$ なら、 $j$ 番目の $D$ は位置 $t$ 以下にあるので $p_{j} \leq t$ であり、 $u$ は非減少なので $u (t) \geq u (p_{j}) \geq j = d (t)$ 。

したがって、ステップ 1 の対応により、 $f^{(a, b)}$ は $U$ が $a$ 個・ $D$ が $b$ 個で $(1)$ をみたす文字列（「良い文字列」とよぶ）の個数に等しい。

ステップ 3（悪い文字列の数え上げ: 鏡映）. $U$ が $a$ 個・ $D$ が $b$ 個の文字列は全部で $(b n)$ 個ある。そのうち $(1)$ をみたさないもの（「悪い文字列」）全体を $X$ とする。

$b = 0$ のときは $d (t) = 0$ なので $(1)$ は常に成り立ち、 $X = \emptyset$ で $# X = 0 = (- 1 n)$ である。以下 $b \geq 1$ とし、 $U$ が $a + 1$ 個・ $D$ が $b - 1$ 個の文字列全体を $Y$ とする。 $# Y = (b - 1 n)$ である。 $X$ と $Y$ の間の全単射を作る。

$Φ : X \to Y$ の定義. $w \in X$ に対し、 $d (t) > u (t)$ となる最小の $t$ をとる。 $d (0) - u (0) = 0$ で、 $d - u$ は $1$ 文字ごとにちょうど $\pm 1$ 変わるので、 $d (t) - u (t) = 1$ であり、 $t^{'} < t$ では $d (t^{'}) - u (t^{'}) \leq 0$ である。 $w$ の先頭 $t$ 文字の $U$ と $D$ をすべて入れ替えた文字列を $Φ (w)$ とする。先頭 $t$ 文字には $U$ が $u (t)$ 個、 $D$ が $u (t) + 1$ 個あったので、入れ替え後の $U$ の総数は $a - u (t) + (u (t) + 1) = a + 1$ 、 $D$ の総数は $b - 1$ となり、 $Φ (w) \in Y$ である。さらに $Φ (w)$ の先頭部分の個数を $u^{'}, d^{'}$ とすると、 $t^{'} \leq t$ では $u^{'} (t^{'}) - d^{'} (t^{'}) = d (t^{'}) - u (t^{'})$ なので、 $t^{'} < t$ で $u^{'} - d^{'} \leq 0$ 、 $t^{'} = t$ で $u^{'} - d^{'} = 1$ となる。すなわち $Φ (w)$ で $u^{'} - d^{'} = 1$ となる最小の位置は $t$ である。

$Ψ : Y \to X$ の定義. $v \in Y$ に対し、先頭部分の $U, D$ の個数を $u^{'}, d^{'}$ とする。 $u^{'} - d^{'}$ は $0$ から始まって $1$ 文字ごとに $\pm 1$ 変わり、最後に $(a + 1) - (b - 1) = a - b + 2 \geq 2$ となるので、 $u^{'} (s) - d^{'} (s) = 1$ となる $s$ が存在する。その最小の $s$ をとると、 $s^{'} < s$ では $u^{'} (s^{'}) - d^{'} (s^{'}) \leq 0$ である（ $0$ から $\pm 1$ ずつ変わるので、正になるなら先に $1$ を通るから）。 $v$ の先頭 $s$ 文字の $U$ と $D$ を入れ替えた文字列を $Ψ (v)$ とする。先頭 $s$ 文字には $U$ が $d^{'} (s) + 1$ 個、 $D$ が $d^{'} (s)$ 個あったので、入れ替え後の $U$ は $a + 1 - 1 = a$ 個、 $D$ は $b - 1 + 1 = b$ 個である。 $Ψ (v)$ の先頭部分の個数 $u, d$ について、位置 $s$ で $d - u = 1 > 0$ なので $Ψ (v)$ は $(1)$ をみたさず、 $Ψ (v) \in X$ である。また $s^{'} < s$ では $d - u = u^{'} - d^{'} \leq 0$ なので、 $Ψ (v)$ で $d > u$ となる最小の位置はちょうど $s$ である。

互いに逆写像であること. $w \in X$ について、 $Ψ$ を $Φ (w)$ に適用するときに使う位置は、上で示したとおり $t$ である。よって $Ψ (Φ (w))$ は先頭 $t$ 文字を 2 回入れ替えたもので、 $w$ に戻る。同様に $v \in Y$ について、 $Φ$ を $Ψ (v)$ に適用するときに使う位置は $s$ なので、 $Φ (Ψ (v)) = v$ である。よって $Φ : X \to Y$ は全単射であり、 $# X = # Y = (b - 1 n)$ である。

結論. 良い文字列の個数は、全体から悪い文字列を除いて $(b n) - (b - 1 n)$ である（ $b = 0$ のときも $# X = 0 = (- 1 n)$ なので同じ式が成り立つ）。ステップ 1, 2 より
$f^{(a, b)} = (b n) - (b - 1 n) .$
$■$

（確認: $(a, b) = (2, 2)$ のとき $(2 4) - (1 4) = 6 - 4 = 2$ で、実際に標準ヤング盤は、第 $1$ 行が $1, 2$ ・第 $2$ 行が $3, 4$ のものと、第 $1$ 行が $1, 3$ ・第 $2$ 行が $2, 4$ のものの $2$ 個である。）

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が模範解答を見ずに 3 回証明を試み、3 回証明できました
2 つの AI が独立に、模範解答の証明を 1 ステップずつ確かめました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる