📦

ヤング図形と競技プログラミング

2022/08/24に公開

math

tech

数学の様々な分野に登場するヤング図形について解説します。競技プログラミングと関係のありそうなトピックを多めに選びましたが、競技プログラミングのことを知らなくても楽しめると思います。

ヤング図形とは

ヤング図形とは、自然数の分割を箱を用いて可視化したものです。例えば 5 の分割 $5=2+2+1$ の場合、次のように 1 行目に 2 個の箱、2 行目に 2 個の箱、3 行目に 1 個の箱を書きます。

このヤング図形を $\lambda=(2,2,1)$ のように表します。

厳密にはヤング図形は上から下に向かって箱の個数が広義単調減少となるものです。 $\lambda$ が $n$ の分割であることを、 $\lambda\vdash n$ のように表すこともあります。

ヤング図形をテーマにした競技プログラミングの問題を 1 つ紹介します。

Codeforces Round #609 (Div. 2) D. Domino for Young
ヤング図形が与えられます。最大で何枚のドミノを敷くことができますか。

ヤング図形の定義はとてもシンプルですが、奥深い理論が展開されます。その一部を見ていきましょう。

分割数

$n$ の分割の個数を分割数といい、 $p(n)$ と表します。 $p(1)=1, p(2)=2, p(3)=3, p(4)=5, p(5)=7, p(6)=11,\cdots$ となっています。

$p(n)$ を $n$ の式で表したいところですが、実はかなり複雑な式になります。(『数学ガール』の p. 318 にあります。)

競技プログラミングにおいては $p(n)$ の値は動的計画法で求めることができます。

分割数
$N$ 個の互いに区別できない荷物があります。これらを互いに区別できない $M$ 個の容器に入れる方法は何通りありますか。

これはプログラミングコンテストチャレンジブック (蟻本) の p. 66 の問題で、写像 12 相の 1 つです。解説は蟻本を見てください。この問題は動的計画法を用いて時間計算量 $O(NM)$ で答えを求めることができます。 $N=M$ の場合が分割数 $p(N)$ なので、分割数を $O(N^2)$ で求めることができました。

実は分割数は $O(N\sqrt{N})$ あるいは $O(N\log N)$ で求めることができます。以下の記事を参照してください。

https://trap.jp/post/1657/

共役図形

ヤング図形 $\lambda$ に対して、行と列を入れ替える (すなわち対角線に沿って反転させる) ことで新たなヤング図形 $\lambda'$ を得ることができます。 $\lambda'$ を $\lambda$ の共役と呼びます。

例えば $\lambda=(2,2,1)$ のとき、 $\lambda'=(3,2)$ です。

共役の共役が元の図形であることは明らかです。

共役を使うことで次の定理が簡単にわかります。

このように、条件 A をみたす分割の個数と条件 B をみたす分割の個数が等しいという定理は多くあります。もう 1 つ紹介するので、証明は考えてみてください。

yukicoder No.2092 Conjugation
ヤング図形の共役を求めてください。

この問題は累積和と呼ばれるテクニックを用いると解くことができます。

カタラン数

競技プログラミングでは組合せの問題も出題されますが、その中でもカタラン数は重要です。カタラン数は

括弧列の個数
二分木の個数
対角線を跨がない経路の個数

など、様々な場面で現れます。カタラン数の詳しい解説はここではしないので、他の記事をご覧ください。

ここでは簡単な解説にとどめます。 $n$ 番目のカタラン数は $C_n=\binom{2n}{n}-\binom{2n}{n-1}=\frac{1}{n+1}\binom{2n}{n}$ です。

ヤング図形との関連を述べましょう。 $\lambda=(n-1,n-2,\ldots,2,1)$ というヤング図形を考えます。この $\lambda$ の内部に含まれるようなヤング図形の個数はカタラン数 $C_n$ となります。これは対角線を跨がない経路を考えたとき、その経路を境界とする図形が $\lambda$ の内部に含まれるヤング図形となるからです。

また、次のような関連もあります。 $\mu=(n,n)$ というヤング図形を考えます。長さ $2n$ の正しい括弧列が与えられたとき、 $\mu$ の箱の中に次のように数字を書き込んでいきます。

$i$ 文字目が ( であるとき、1 行目の最も左にある空箱に $i$ を書く。
$i$ 文字目が ) であるとき、2 行目の最も左にある空箱に $i$ を書く。

括弧列が (()()) のときは次のようになります。

$1$	$2$	$4$
$3$	$5$	$6$

構成から明らかなように、ヤング図形に数字を書き込んだものは次の性質を満たします。

$1$ から $2n$ までの正の整数が 1 回ずつ書かれている。
1 行目について単調増加
2 行目について単調増加
各列について 1 行目にある数よりも 2 行目にある数の方が大きい

次の節ではこれを一般化します。

標準タブローとフック長公式

$n$ の分割を表すヤング図形 $\lambda$ の各箱に $1$ から $n$ までの整数を 1 回ずつ書き込んだものをタブローといいます。タブローが次の条件を満たすとき、標準タブローといいます。

各行について書かれている数字は単調増加
各列について書かれている数字は単調増加

$\lambda=(n,n)$ のとき、標準タブローと正しい括弧列は一対一に対応します。

与えられたヤング図形 $\lambda$ に対し、標準タブローがいくつあるかを求めたいです。そのためにフックについて説明します。ヤング図形のあるマスについて、そのマスを角とするフックとは、そのマスより右または下にあるマスからなる図形 (そのマス自身を含む) です。フックに含まれるマスの個数をフック長といいます。

すなわち、すべてのフック長をかけあわせて $n!$ を割った商が標準タブローの個数となります。

$\lambda=(n,n)$ の場合で考えてみると、フック長は

$n+1$	$n$	$n-1$	$\ldots$	$3$	$2$
$n$	$n-1$	$n-2$	$\ldots$	$2$	$1$

であることから、標準タブローの個数は $\frac{(2n)!}{(n+1)!n!}=\frac{1}{n+1}\binom{2n}{n}$ となります。よって、カタラン数の表示がフック長公式の特別な場合であることがわかりました。

フック長公式の証明は表現論を用いるもの、全単射を構成するもの、確率論的なものなど、さまざまな手法があります。

Judge System Update Test Contest 202004 C - Numbering Blocks
(問題文省略)

まさに標準タブローの個数を求める問題なので、フック長公式で解くことができます。なお制約が小さいので全探索でも解けます。

正しい括弧列の一般化
$A$ 個の文字 a と $B$ 個の文字 b からなる文字列であって、どの接頭辞においても a の個数が b の個数以上となるものは何通りありますか。

解法

$A=B$ の場合が正しい括弧列です。正しい括弧列の場合と同様に、この条件を満たす文字列はヤング図形 $(A,B)$ 上の標準タブローと一対一に対応します。よってフック長公式で個数を求めることができます。 $A<B$ のときは存在しないことに注意してください。

マヤゲーム

マヤゲーム (あるいは佐藤・ウェルターのゲーム) と呼ばれる、次のようなゲームがあります。

直線状に並ぶマスの上に $N$ 個の石が置かれています。石 $i$ の位置は左から $A_i$ 番目のマスです。Georgia と Bob は交互にこれらの石のうち 1 つを選び、左に動かします。1 マス以上であれば何マスでも左に動かすことができます。1 つのマスに 2 つ以上の石を置くことはできません。動かすことができなくなった人の負けです。Georgia の番から始まるとし、お互いが最善を尽くすとしたとき、どちらが勝つでしょうか。

ゲームは次のように進行します。

このゲームは、実はヤング図形と関連します。空きマスを→、石のあるマスを↑と置き換えてみましょう。

経路が得られました。これをヤング図形の境界と見なすことで、ゲームの盤面からヤング図形を得ることができます。では、石を動かすというルールはヤング図形ではどのようになるでしょうか。

実は、マヤゲームにおける操作は、フックを 1 つ選んで抜くことと対応します。

Xmas Contest 2021 G - Game of Distinction
(問題文省略)

この問題はマヤゲームと同じです。この問題を解くにはマヤゲームの解析をする必要がありますが、ここでは省略します。

また、蟻本から以下の類題を紹介します。

Georgia and Bob
直線状に並ぶマスの上に $N$ 個の石が置かれています。石 $i$ の位置は左から $A_i$ 番目のマスです。Georgia と Bob は交互にこれらの石のうち 1 つを選び、左に動かします。1 マス以上であれば何マスでも左に動かすことができますが、他の石を追い越してはいけません。また 1 つのマスに 2 つ以上の石を置くこともできません。動かすことができなくなった人の負けです。Georgia の番から始まるとし、お互いが最善を尽くすとしたとき、どちらが勝つでしょうか。

解説は蟻本に委ねます。

対称群の表現論

ヤング図形は対称群の表現論において中心的な役割を果たします。対称群については以下の記事も参考にしてください。

有限群の表現論については以下の記事も参考にしてください。

https://hackmd.io/@koboshi/rJpHiXa-O

対称群 $S_n$ の表現論について考えます。まず有限群の表現論の一般論から次が成り立ちます。

対称群の共役類は、サイクル型と一対一に対応します。サイクル型とは、 $S_n$ の元である置換をサイクル (巡回置換) の積として表したときのサイクルの長さのリストです。例えば

\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 5 & 4 & 1 & 2 & 6 \end{pmatrix}=(1,3,4)(2,5)(6)

のサイクル型は $(3,2,1)$ です。サイクル型は $n$ の分割となります。よって、対称群の場合に次が成り立つことが分かりました。

この定理は単に個数が等しいことしか言っていませんが、実際に $n$ の分割 $\lambda$ が与えられたとき既約表現 $V_{\lambda}$ を構成することができます。

$V_{\lambda}$ の指標を $\chi_{\lambda}$ とします。さらに有限群の表現論から従う結果を述べます。

以降の節でこの式が意味するものを考えていきます。

ムルナガン・中山の規則

まずは $\chi_{\lambda}(\text{id})=\dim V_{\lambda}$ がどのような数なのかを考えます。結論を先に述べると、これは $\lambda$ 上の標準タブローの個数です。

一般化して $\chi_{\lambda}(C_{\mu})$ の値を考えます。ここで $C_{\mu}$ はサイクル型 $\mu$ をもつ置換からなる共役類です (指標は類関数なのでこれは well-defined です)。

$\lambda$ のヤング図形上のマス $(i,j)$ に関するリムフックとは、 $k\ge i, l\ge j$ をみたすマス $(k,l)$ であって、 $(k+1,l+1)$ にマスがないようなマスからなる集合です。リムフックは連結で $2\times 2$ の図形を含まず、リムフックの要素数はフック長 $h(i,j)$ と等しくなります。

このリムフックを $\text{rim}(i,j)$ と表します。 $\lambda$ から $\text{rim}(i,j)$ を除いて得られるヤング図形を $\lambda\setminus\text{rim}(i,j)$ とします。またリムフック $\text{rim}(i,j)$ の行数を高さと呼び、 $\text{ht}(i,j)$ で表します。上の図のリムフック (緑色) の高さは 3 です。

$\mu=(\mu_1,\ldots,\mu_m)$ とします。 $\mu_1$ を削除して得られる分割を $\mu-\mu_1=(\mu_2,\ldots,\mu_m)$ と表すことにします。このとき、 $\chi_{\lambda}(C_{\mu})$ は次のように再帰的に求めることができます。

例として、 $\lambda=(8,3,3),\mu=(5,4,3,2)$ のときに指標値を求めてみます。まず $\lambda$ の長さ 5 のリムフックを探します。これはマス $(1,4)$ の 1 つのみです。よって

$\chi_{(8,3,3)}(C_{(5,4,3,2)})=\chi_{(3,3,3)}(C_{(4,3,2)})$

となります。次に $(3,3,3)$ において長さ 4 のリムフックを探します。これはマス $(1,2),(2,1)$ の 2 つがあります。 $(1,2)$ のリムフックの高さは 3、 $(2,1)$ のリムフックの高さは 2 なので

$\chi_{(3,3,3)}(C_{(4,3,2)})=(-1)^{3-1}\chi_{(2,2,1)}(C_{(3,2)})+(-1)^{2-1}\chi_{(3,2)}(C_{(3,2)})=\chi_{(2,2,1)}(C_{(3,2)})-\chi_{(3,2)}(C_{(3,2)})$

となります。あとは同様に計算することで

$\chi_{(2,2,1)}(C_{(3,2)})=-\chi_{(2)}(C_{(2)})=-1$
$\chi_{(3,2)}(C_{(3,2)})=-\chi_{(1,1)}(C_{(2)})=1$

よって

$\chi_{(8,3,3)}(C_{(5,4,3,2)})=-1-1=-2$

となります。

ここで冒頭の $\chi_{\lambda}(\text{id})=\dim V_{\lambda}$ について考えます。すなわち $\mu=(1,1,\ldots,1)$ の場合です。これは $\lambda$ のヤング図形から、ヤング図形という性質を保ったまま箱を 1 個ずつ取り除いていく方法の数です。逆から見れば箱を 1 個ずつ加えて $\lambda$ を作る方法の数となります。箱の追加順に 1,2,... と番号を振っていけば標準タブローとなることが分かります。したがって、 $\chi_{\lambda}(\text{id})$ は $\lambda$ 上の標準タブローの個数に等しいことが分かりました。前述の通り、この値はフック長公式で求められます。

自作問題
$\lambda$ が $a$ 個の 2 と $n-2a$ 個の 1、 $\mu$ が $b$ 個の 2 と $n-2b$ 個の 1 からなる場合に $\chi_{\lambda}(C_{\mu})$ の値を求めてください。

解法

まずは長さ 2 のリムフックを除いていきます。これは次の 3 通りです。

1 列目から 2 個除く
2 列目から 2 個除く
1,2 列目から 1 個ずつ除く

長さ 2 のリムフックを除けるだけ除いたら残りはすべて長さ 1 のリムフックになります。この場合の指標値はフック長公式から求められます。よってメモ化再帰または逆から見て DP で求められます。DP で求める場合

if (i >= j) {
    dp[i + 2][j] -= dp[i][j]
    if (i >= j + 2) {
        dp[i][j + 2] -= dp[i][j]
    }
    if (i == j) {
        dp[i + 1][j + 1] += dp[i][j]
    }
}

のような遷移で求められます。計算量は $O(n^2)$ です。

自作問題
$\lambda$ が与えられるので、 $\chi_{\lambda}(C_{\mu})=0$ となるような $\mu$ が存在すれば 1 つ求めてください。

解法

$\mu_1$ をフック長として現れない数にすればよいです。なぜなら $h(i,j)=\mu_1$ をみたす $i,j$ が存在しないのでムルナガン・中山の規則の右辺が 0 になるからです。 $\lambda$ が $(N)$ または $(1,1,\ldots,1)$ のときはすべての数がフック長として現れるので解はありません。

ロビンソン・シェンステッド対応と最長増加部分列

続いて $n!=\sum_{\lambda\vdash n}(\dim V_{\lambda})^2$ という式の持つ意味を考えていきます。左辺は長さ $n$ の順列の個数、すなわち対称群 $S_n$ の位数です。右辺に現れる $\dim V_{\lambda}$ は先ほど述べた通り $\lambda$ 上の標準タブローの個数です。どのような関係があるのでしょうか。

ロビンソン・シェンステッド対応はこの問いに答えを与えます。

ロビンソン・シェンステッド対応は、順列 $A=(A_1,A_2,\ldots,A_n)$ に同じ形の標準タブローの組 $(P,Q)$ を対応させる規則のことです。 $A_1,A_2,\ldots,A_n$ の順に「挿入」を行っていくことで $(P_1,Q_1),(P_2,Q_2),\ldots,(P_n,Q_n)$ と順番に構成していきます。 $(P,Q)=(P_n,Q_n)$ を作ることが目的です。

まず $A_1$ を挿入すると $P_1$ は $A_1$ のみからなるタブロー、 $Q_1$ は $1$ のみからなるタブローになります。いま $(P_{k-1},Q_{k-1})$ まで構成できたとして、 $A_k$ を挿入して $(P_k,Q_k)$ を作ります。次のように $P_k$ を作ります。 $x_0=A_k$ とおきます。

$P_{k-1}$ の 1 行目の数字がすべて $x_0$ 以下ならば、1 行目の末尾に $x_0$ を追加して終了。
そうでなければ 1 行目にある $x_0$ より大きい数字の中で最も左にある数を $x_1$ とおく。1 行目の $x_1$ を $x_0$ で置き換える。
$P_{k-1}$ の 2 行目にある数字がすべて $x_1$ 以下ならば、2 行目の末尾に $x_1$ を追加して終了。
そうでなければ 2 行目にある $x_1$ より大きい数字の中で最も左にある数を $x_2$ とおく。2 行目の $x_2$ を $x_1$ で置き換える。
$P_{k-1}$ の 3 行目にある数字がすべて $x_2$ 以下ならば、3 行目の末尾に $x_2$ を追加して終了。
そうでなければ 3 行目にある $x_2$ より大きい数字の中で最も左にある数を $x_3$ とおく。3 行目の $x_3$ を $x_2$ で置き換える。
以下これを繰り返す。

このようにして得られるタブローを $P_k$ とおきます。

$(P_{k-1},Q_{k-1})$ は同じ形をしているので、 $P_k$ は $Q_{k-1}$ と 1 箇所だけ異なっています。そこで $Q_{k-1}$ に $k$ と書かれた箱を追加して $P_k$ と形を合わせます。こうして得られるタブローを $Q_k$ とします。

このようにして $(P_1,Q_1),(P_2,Q_2),\ldots$ が作られ、 $(P,Q)=(P_n,Q_n)$ が得られます。この操作をロビンソン・シェンステッド対応と呼びます。例として順列が $3,5,1,2,4$ の場合は次のようになります。

ロビンソン・シェンステッド対応はこのサイトで遊べるので遊んでみましょう。

全単射が存在するので集合の要素数は等しくなります。長さ $n$ の順列の個数は $n!$ 、形 $\lambda$ をもつ標準タブローの個数は $\dim V_{\lambda}$ なので、 $n!=\sum_{\lambda\vdash n}(\dim V_{\lambda})^2$ となります。よって冒頭の等式に組合せ論的な解釈を与えたことになります。このように組合せ論では等式 $a=b$ を示すために

要素数 $a$ の集合 $A$ を作る。
要素数 $b$ の集合 $B$ を作る。
$A,B$ の間に全単射を作る。

という手法が用いられることがあります。

ロビンソン・シェンステッド対応は順列から同じ形の標準タブローの組 $(P,Q)$ への対応でしたが、順列を一般の整数列に置き換えても同様のアルゴリズムになります。この場合 $P$ は半標準タブロー (行について広義単調増加、列について狭義単調増加) になります。さらに一般化したものをロビンソン・シェンステッド・クヌース対応 (RSK 対応) といいます。RSK 対応の詳細については後述します。

RSK 対応には次の性質があります。

ということで、最長増加部分列に関する問題を RSK 対応の観点から紹介します。

Chokudai SpeedRun 001 H - LIS
数列 $a$ から好きな整数を好きなだけ取り除き、単調増加な数列を作るとき、その数列の長さの最大値を求めなさい。

解法

競技プログラミングの典型問題です。RSK 対応の観点から見ると、 $a$ に対応するヤング図形の 1 行目の箱の個数が答えです。そこで RSK 対応の操作を 1 行目のみに注目して行うことでこの問題を解くことができます。標準タブローであることから 1 行目は昇順に並んでいるので、ある数より大きい数の中で最も左にあるものは二分探索を用いて見つけることができます。よってこの問題は計算量 $O(N\log N)$ で解けます。

自作問題
長さ $N$ の数列 $A_1,A_2,\ldots,A_N$ が与えられます。次の条件を満たすように各数を赤・緑・青のいずれかで塗ります。

赤く塗られた数からなる部分列を取り出すと広義単調増加になっている。

青く塗られた数からなる部分列を取り出すと広義単調増加になっている。

緑色で塗られた数の個数の最小値を求めてください。

ヤング図形の 1 行目の箱の個数が最長増加部分列の長さなら、2 行目の箱の個数は何を表すか気になった方もいるかもしれません。実は次の性質があります。

$k=2$ とすることで、この問題は RSK 対応の 1,2 行目のみに注目すればよいことになります。

AtCoder Regular Contest 091 E - LISDL
$1,2,\ldots,N$ の順列であって次を満たすものがあれば構築してください。

最長増加部分列の長さが $A$

最長減少部分列の長さが $B$

解法

上で述べた定理から、1 行目の箱の個数が $A$ 、1 列目の箱の個数が $B$ であるヤング図形を考えればよいです。このようなヤング図形の箱の個数は明らかに $A+B-1$ 以上 $AB$ 以下です。よってこのような順列が存在するための条件は $A+B-1\le N\le AB$ です。構築もロビンソン・シェンステッド対応の逆を考えることでできます。

Codeforces Round #502 C. The Phone Number
長さ $n$ の順列のうち最長増加部分列の長さと最長減少部分列の長さの和が最小となるようなものを構築してください。

上の問題に帰着できます。考えてみてください。

yukicoder No.2048 L(I+D)S
$1,2,\ldots,N$ の順列であって、最長増加部分列の長さと最長減少部分列の長さの和が $N$ となるものの個数を求めてください。

ここまでに登場した定理を使って解くことができます。

ロビンソン・シェンステッド・クヌース対応とコストカ数

ロビンソン・シェンステッド対応を一般化した、ロビンソン・シェンステッド・クヌース対応 (RSK 対応) を考えます。

順列 $p_1,p_2,\ldots,p_n$ は

\begin{pmatrix} 1 & 2 & \cdots & n \\ p_1 & p_2 & \cdots & p_n \end{pmatrix}

とも表記されます。上に並ぶ $1,2,\ldots,n$ を一般化したものが今回の主役である 2 行配列と呼ばれるものです。

非負整数成分の行列 $A=(a_{ij})$ を考えます。 $\binom{i}{j}$ を $a_{ij}$ 個並べて 2 行配列を作ります。例えば

A=\begin{pmatrix} 1 & 1 & 2 \\ 3 & 0 & 1 \\ 0 & 1 & 1 \end{pmatrix}

のとき対応する 2 行配列は

\begin{pmatrix} 1 & 1 & 1 & 1 & 2 & 2 & 2 & 2 & 3 & 3 \\ 1 & 2 & 3 & 3 & 1 & 1 & 1 & 3 & 2 & 3 \end{pmatrix}

となります (並べる順番に注意)。 $A$ が置換行列、すなわち各行各列に 1 が 1 つだけありそれ以外の成分が 0 のとき、2 行配列の上側の数列が $1,2,\ldots,n$ となり、順列と同一視されます。

このようにして作った 2 行配列について、上側の数列を $u_1,u_2,\ldots,u_n$ 、下側の数列を $v_1,v_2,\ldots,v_n$ とします。ここからタブローの組を、ロビンソン・シェンステッド対応の場合と同様に作っていきます。まず $P_1$ は $v_1$ 、 $Q_1$ は $u_1$ のみからなるタブローです。 $P_{k-1},Q_{k-1}$ まで構成したとき、 $P_k$ は $P_{k-1}$ に $v_k$ を挿入して得られるタブローです。 $Q_{k-1}$ に箱を 1 個追加して $P_k$ と同じ形にします。追加した箱に $u_k$ を書き込み、 $Q_k$ を作ります。これで同じ形のタブローの組 $(P,Q)=(P_n,Q_n)$ ができました。このようにしてできた $P,Q$ は半標準タブローとなります (定義はすでに述べました)。

半標準タブローにおいて $i$ が $m_i$ 回書かれているとき、数列 $(m_1,m_2,\ldots)$ を半標準タブローのタイプといいます。 $P,Q$ のタイプをそれぞれ $(p_1,p_2,\ldots), (q_1,q_2,\ldots)$ とするとき、定義からすぐにわかりますが、 $p_i$ は $A$ の $i$ 列目の和、 $q_i$ は $A$ の $i$ 行目の和です。

形が分割 $\lambda$ 、タイプが分割 $\mu$ となっているような半標準タブローの個数を $K_{\lambda\mu}$ で表し、コストカ数と呼びます。 $i$ 行目の和が $\lambda_i$ 、 $j$ 列目の和が $\mu_j$ となっているような非負整数行列の個数を $M_{\lambda\mu}$ とおきます。RSK 対応により次の式が得られます。

AtCoder Beginner Contest 256 C - Filling 3x3 array
$3\times 3$ のマス目があり、各マスに正の整数を書き込みます。 $i$ 行目の和が $h_i$ 、 $j$ 列目の和が $w_j$ となる書き込み方は何通りありますか。

まさに $M_{\lambda\mu}$ を求める問題なので、コストカ数を計算することで解くことができます。

ただし、コストカ数の計算は #P-complete と呼ばれるクラスに属していて、効率的にはできないようです。

3 次元ヤング図形

この記事の締めくくりとして 3 次元ヤング図形を紹介します。まず次の問題を考えてみましょう。

yukicoder No.2023 Tiling is Fun
六角形 ABCDEF に三種類の図形を敷き詰める方法は何通りありますか。

図が立体的に見えると思った人もいるかもしれません。実際、この問題は 3 次元ヤング図形の特別なものとなっています。ヤング図形は平面上に正方形を並べたものでしたが、3 次元ヤング図形は空間内に立方体を並べたものです。

平面分割とは平面上に並べられた非負整数列 $(a_{i,j})_{i,j\in\mathbb{N}}$ であって

$a_{i,j}\ge a_{i,j+1}$
$a_{i,j}\ge a_{i+1,j}$
総和は有限

をみたすものです。座標 $(i,j)$ の上に $a_{i,j}$ 個の立方体を積み上げることで 3 次元ヤング図形が得られます。

上の図は平面分割 $\begin{pmatrix} 3 & 2 & 1 \\ 1 & 1 & 0 \end{pmatrix}$ に対応する 3 次元ヤング図形です。

これを平面的に見ることで、上記の問題のように 3 次元ヤング図形と敷き詰めが対応します。

問題では一本の経路と対応していましたが、一般には複数本の経路の組と対応します。

どの 2 つの経路も交わりません。よって 3 次元ヤング図形の数え上げは非交差経路の数え上げに帰着され、LGV 公式と呼ばれる式により計算することができます。結果だけ述べると、箱 $[0,r]\times [0,s]\times [0,t]$ の内部に含まれる 3 次元ヤング図形の個数は

\det\left(\binom{r+s}{r+i-j}\right)_{i,j=1}^t

となります。

マクマホンの公式によれば、この式は

\prod_{i=1}^r\prod_{j=1}^s\prod_{k=1}^t\frac{i+j+k-1}{i+j+k-2}

に等しくなります。

参考文献

基礎編

W. Fulton (池田岳・井上玲・岩尾慎介　訳), ヤング・タブロー ―表現論と幾何への応用―, 丸善出版, 2019.
- ヤング図形の入門書と言えばやはりこれです。第 1 部は予備知識を特に必要としません。最長増加部分列と RSK 対応についても述べられています。続く第 2 部は表現論、第 3 部は幾何学への応用で、それなりに予備知識が要ります。
雪江明彦, 代数学 1 群論入門, 日本評論社, 2010.
- 基礎的な群論の教科書です。対称群の共役類がヤング図形により記述されることが載っています。
池田岳, テンソル代数と表現論, 東京大学出版会, 2022.
- 基本的な線型代数を学んだ人がその先にある奥深い数学を学び始めるのに最適な本です。第 1 章～第 3 章がジョルダン標準形と線型常微分方程式への応用で、ジョルダン標準形の記述にヤング図形が現れます。第 4 章はテンソル代数で、この先で大いに用いられます。第 5 章から本格的な有限群の表現論が展開され、対称群と一般線形群の既約指標を求めるという問題に向かって進んでいきます。後半部においてもヤング図形が活躍します。
高崎金久, 線形代数と数え上げ (増補版), 日本評論社, 2021.
- 3 次元ヤング図形の話から始まります。他には完全マッチングの数え上げや行列木定理など、競プロ er にとって興味深そうな話題が豊富です。
Richard Stanley, Enumerative Combinatorics.
- 競プロ er のファンも多い数え上げ組合せ論の本です。7 章では対称群との関係も述べられています。
Amritanshu Prasad, Representation Theory: A Combinatorial Viewpoint (Cambridge Studies in Advanced Mathematics)
- 組合せ論的な表現論の本です。
Bruce E. Sagan, The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions.
- 対称群の本です。

発展編

洞彰人, 対称群の表現とヤング図形集団の解析学 ―漸近的表現論への序説, 数学書房, 2017.
- ヤング図形の極限形状など、この記事では触れられなかった話題を含みます。この本で扱われる対称群の表現論は Okounkov-Vershik approach という比較的新しい手法に基づいています。確率論の手法を用いて、ヤング図形の箱の個数や対称群の次数が無限に大きくなったときのふるまいを紐解いていきます。この分野における初期の重要な結果が、Vershik-Kerov によるヤング図形の極限形状です。この定理の系としてランダムな順列の最長増加部分列の長さがおよそ $2\sqrt{n}$ になることも従います。
中島俊樹, 結晶基底と幾何結晶　量子群からトロピカルな世界へ, サイエンス社, 2019.
- ざっくり説明すると、半単純リー代数 $\mathfrak{g}$ があったとき、普遍包絡代数 $U(\mathfrak{g})$ が定まります。量子群はパラメータ $q$ を用いて $U_q(\mathfrak{g})$ と表されるもので、 $q=1$ のとき $U(\mathfrak{g})$ になると考えられます。結晶基底は $q=0$ としたものです (以上ざっくりした説明)。特に A 型の結晶基底がヤング図形を用いて記述できます。このように結晶基底は組合せ論とも関わる重要な対象ですが、その存在を証明するのは簡単ではありません。14 個の互いに関連しあう命題からなる帰納法を用いて示すという"grand loop"と呼ばれる方法で存在証明がされています。(すごそう)

Web 記事

https://codeforces.com/blog/entry/98167

Discussion

ログインするとコメントできます