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

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

(2024/08/04: 大幅に改訂しました)

ヤング図形とは

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

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

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

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

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

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

分割数

箱の総数が $nn$ のヤング図形の個数、すなわち $nn$ の分割の個数を分割数といい、$p(n)p(n)$ と表します。$p(1)=1,p(2)=2,p(3)=3,p(4)=5,p(5)=7,p(6)=11,⋯p(1)=1, p(2)=2, p(3)=3, p(4)=5, p(5)=7, p(6)=11,\cdots$ となっています。

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

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

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

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

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

https://combinatorics-fun.vercel.app/natori/202302/

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

共役図形

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

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

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

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

定理: 最大値が $kk$ であるような $nn$ の分割の個数と、$kk$ 個の数からなる $nn$ の分割の個数は等しい。

このように、条件 A をみたす分割の個数と条件 B をみたす分割の個数が等しいという定理は多くあります。興味のある方はぜひ調べてみてください。

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

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

マヤ図形とマヤゲーム

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

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

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

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

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

それを調べるためにフックについて説明します。ヤング図形のあるマスについて、そのマスを角とするフックとは、そのマスより右または下にあるマスからなる図形 (そのマス自身を含む) です。フックに含まれるマスの個数をフック長といいます。

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

マヤゲームの盤面のことをマヤ図形と呼びます。ヤング図形を調べるにあたってはマヤ図形を調べることが大切になることもあります。

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

この問題はマヤゲームと同じです。この問題を解くにはマヤゲームの解析をする必要がありますが、ここでは省略します。有名なニムゲームと比べて難しいです。

World Tour Finals 2024 B - 01 Inversion Expected
(問題文省略)

解法

0,1 列をマヤ図形だと思うことで、操作はヤング図形からフックを引き抜く操作となります。この言い換えにより解くことができるようです。

カタラン数

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

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

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

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

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

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

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

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

$11$	$22$	$44$
$33$	$55$	$66$

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

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

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

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

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

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

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

与えられたヤング図形 $λ\lambda$ に対し、標準タブローがいくつあるかを求める公式があります。

定理 (フック長公式): 箱の総数が $nn$ のヤング図形 $λ\lambda$ に対し、標準タブローの個数は

$$n!∏h(i,j) \frac{n!}{\prod h(i,j)}$$

に等しい。ここで $h(i,j)h(i,j)$ はマス $(i,j)(i,j)$ を角とするフックの長さ (フック長) である。

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

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

$n+1n+1$	$nn$	$n−1n-1$	$…\ldots$	$33$	$22$
$nn$	$n−1n-1$	$n−2n-2$	$…\ldots$	$22$	$11$

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

フック長公式の証明は表現論を用いるもの、全単射を構成するもの、確率を用いるものなど、さまざまな手法があります。詳しくは以下の記事をご覧ください。

https://combinatorics-fun.vercel.app/natori/202305/

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

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

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

解法

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

yukicoder No.2149 Vanitas Vanitatum
ヤング図形から縦または横向きのドミノを引き抜くことを繰り返して空にする方法は何通りありますか。

解法

マヤ図形を考えると、ドミノを引き抜く操作は黒石を 2 つ左の空きマスに移動させる操作と対応します。マヤ図形の偶数番目と奇数番目を取り出すことで 2 つのマヤ図形が得られます。ここからヤング図形を復元し、フック長公式を使います。以下の記事もご覧ください。

https://combinatorics-fun.vercel.app/natori/202301/

半標準タブロー

標準タブローとよく似た、半標準タブローと呼ばれるものがあります。それはヤング図形 $λ\lambda$ の箱に正の整数を書き込んだタブローであって

• 各行について書かれている数は広義単調増加
• 各列について書かれている数は狭義単調増加

をみたすものです。

定義から、書き込まれた数の最大値は $λ\lambda$ の行数以上です。書き込まれた数が $kk$ 以下であるような半標準タブローの個数を求める公式があります。これを $dλ(k)d_{\lambda}(k)$ とおくと、次のようになります。

$$dλ(k)=∏1≤i<j≤kλi−λj+j−ij−i=∏(i,j)∈λk+c(i,j)h(i,j) \begin{align*} d_{\lambda}(k) &= \prod_{1\le i<j\le k}\frac{\lambda_i-\lambda_j+j-i}{j-i} \\ &= \prod_{(i,j)\in\lambda}\frac{k+c(i,j)}{h(i,j)} \end{align*}$$

ここで $h(i,j)h(i,j)$ はフック長で、$c(i,j)=j−ic(i,j)=j-i$ は容量です。詳しくは以下の記事をご覧ください。なお、この 2 つの公式とフック長公式を合わせることで標準タブローの個数を求める別の公式を得ることもできます。

https://combinatorics-fun.vercel.app/natori/202405/

yukicoder No.2556 Increasing Matrix
成分が正の整数である $NN$ 次正方行列であって、次の条件を満たすものは何通りありますか。

• 各行について広義単調増加
• 各列について広義単調増加
• $i=1,2,…,Ni=1,2,…,N$ に対して、$(i,i)(i,i)$ 成分は $AiA_i$ である。

この問題は半標準タブローの個数を求める問題に帰着されます。

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

数列 $A=(A1,A2,…,An)A=(A_1,A_2,\ldots,A_n)$ の (広義) 増加部分列は、部分列 $(Ai1,Ai2,…,Aik) (i1<⋯<ik)(A_{i_1},A_{i_2},\ldots,A_{i_k}) \ (i_1<\cdots<i_k)$ であって $Ai1≤⋯≤AikA_{i_1}\le\cdots\le A_{i_k}$ をみたすものです。最長増加部分列は長さ $kk$ が最大となる増加部分列です。

与えられた数列の最長増加部分列の長さを求める方法として、次の有名なアルゴリズムがあります。

$dpjdp_j$ を長さが $jj$ の増加部分列における末尾の要素の最小値とします。ただし長さが $jj$ の増加部分列が存在しないときは $dpj=∞dp_j=\infty$ とします。これをいきなり求めるのは難しいので、$(A1,…,Ai)(A_1,\ldots,A_i)$ に制限した場合の $dpjdp_j$ を $i=1,2,…,ni=1,2,\ldots,n$ の順に更新していくことを考えます。例えば $A=(1,2,3,1,4)A=(1,2,3,1,4)$ とします。

• $i=1i=1$ : $dp=(1,∞,∞,∞,∞)dp=(1,\infty,\infty,\infty,\infty)$
• $i=2i=2$ : $dp=(1,2,∞,∞,∞)dp=(1,2,\infty,\infty,\infty)$
• $i=3i=3$ : $dp=(1,2,3,∞,∞)dp=(1,2,3,\infty,\infty)$
• $i=4i=4$ : $dp=(1,1,3,∞,∞)dp=(1,1,3,\infty,\infty)$
• $i=5i=5$ : $dp=(1,1,3,4,∞)dp=(1,1,3,4,\infty)$

これを見ると、更新箇所は 1 箇所で、それは $Ai<dpjA_i<dp_j$ をみたす最小の $jj$ であることがわかります。このような更新操作を適切に行うことで、最長増加部分列の長さ (すなわち $dpj≠∞dp_j\ne\infty$ となる最大の $jj$) を時間計算量 $O(nlog⁡n)O(n\log n)$ で求めることができます。

更新というのは元の数を新しい数で置き換えるという操作ですが、捨てちゃうのはもったいないですよね？そこで 2 本目の配列を用意して、元の数をそちらに移動させることを考えましょう。2 本目の配列でも更新操作が行われ、そこで追い出される数は 3 本目の配列に移動させます。配列の $∞\infty$ の部分を無視するとこれはタブローとなります。

すると、最長増加部分列の長さを求めるアルゴリズムは次のように拡張されます。まずタブロー $Pk−1P_{k-1}$ があるとします。

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

このようにして得られるタブローを $P_k$ とおきます。空のタブロー $P_0$ から出発してこの操作を繰り返すことで、タブロー $P_n$ が得られます。

これは数列からタブローへの写像を定めます。さらにこのタブローは半標準タブロー（数列が $(1,2,\ldots,n)$ の順列のときは標準タブロー）になります。しかし、この写像は全単射ではありません。$(3,1,4,5,2,6), (3,4,1,2,5,6)$ という 2 つの異なる数列から同じタブローが得られます。

そこで、新たなタブローの列 $Q_1,Q_2,\ldots,Q_n$ を次のように定めます。$P_k$ の形は $P_{k-1}$ の形に 1 つ箱を加えたものです。$Q_{k-1}$ が定まっているとき、$Q_k$ は $Q_{k-1}$ に $k$ が書かれた箱を、$P_k$ と $Q_k$ が同じ形のタブローとなるように加えたものとして定めます。

作り方から明らかに、$Q_1,\ldots,Q_n$ は標準タブローです。

このようにしてタブローの組の列 $(P_1,Q_1),(P_2,Q_2),\ldots,(P_n,Q_n)$ が作られます。数列から $(P,Q)=(P_n,Q_n)$ を得る操作をロビンソン・シェンステッド対応と呼びます。これは全単射となることが知られています。

定理 (ロビンソン・シェンステッド対応): ロビンソン・シェンステッド対応は長さ $n$ の順列からなる集合と、大きさ $n$ の同じ形の標準タブローの組からなる集合の間の全単射を与える。

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

順列ではなく一般の正整数列の場合も似たような結果が成り立ちます。この場合、$Q$ は標準タブローのままですが $P$ は半標準タブローとなります。さらに一般化したものをロビンソン・シェンステッド・クヌース対応 (RSK 対応) といいます。RSK 対応の詳細については後述します。

ロビンソン・シェンステッド対応には次の性質があります。

定理: 順列 $p$ がロビンソン・シェンステッド対応により標準タブローの組 $(P,Q)$ と対応するとき、逆順列 $p^{-1}$ は $(Q,P)$ と対応する。

ロビンソン・シェンステッド対応が最長増加部分列の長さを求めるアルゴリズムの拡張であったことから、次の定理の 1 つ目の主張がわかります。

定理: 数列 $A$ から形 $\lambda$ のタブローの組が得られたとき

• $A$ の最長増加部分列の長さは $\lambda$ の 1 行目の箱の個数に等しい。
• $A$ の最長減少部分列の長さは $\lambda$ の 1 列目の箱の個数に等しい。

最長増加部分列に関する問題をロビンソン・シェンステッド対応の観点から紹介します。

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

最長増加部分列の典型問題です。

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

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

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

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

定理: 数列 $A$ はロビンソン・シェンステッド対応により形 $\lambda$ のタブローの組と対応したとする。$A$ から共通要素をもたない $k$ 本の増加部分列をとったとき、長さの和の最大値は $\lambda$ の 1 から $k$ 行目の箱の個数に等しい。

$k=2$ とすることで、この問題はロビンソン・シェンステッド対応の 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$ となるものの個数を求めてください。

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

降下点集合

順列 $p$ に対して、$D(p)=\{i\mid p_i>p_{i+1}\}$ を降下点集合といいます。AtCoder の EDPC-T は与えられた降下点集合をもつ順列を数え上げる問題であり、組合せ論の中心問題です。以下の記事もご覧ください。

https://combinatorics-fun.vercel.app/natori/202209/

実はロビンソン・シェンステッド対応は降下点集合とも大いに関係します。それを見るために、順列の降下点集合に加えてタブローの降下点集合も定義します。

標準タブロー $T$ において、$i$ が $i+1$ よりも上の行に書かれているような $i$ の集合を $T$ の降下点集合といい、$D(T)$ で表します。

定理: 順列 $p$ がロビンソン・シェンステッド対応によって標準タブローの組 $(P,Q)$ と対応するとき、$D(p)=D(Q)$ が成り立つ。

この定理は $p_i<p_{i+1}$ か $p_i>p_{i+1}$ で場合分けして、タブロー $P_i$ から $P_{i+1}$ を作るときに $p_{i+1}$ が書かれた箱がどこに行くかを考えることで証明できます。

自作問題
順列 $p$ がグラスマンであるとは、$p_i>p_{i+1}$ となる $i$ がただ 1 つ存在することをいいます。
$(1,2,\ldots,N)$ の順列 $p$ であって、$p$ も $p^{-1}$ もグラスマンであるものはいくつありますか。

解法

$p_i>p_{i+1}$ となるただ 1 つの $i$ を決めると、降下点集合が決まります。順列 $p$ の降下点集合とタブロー $Q$ の降下点集合が等しいことから、$Q$ がどのような形になるかがわかります。一方、$p^{-1}$ はロビンソン・シェンステッド対応により $(Q,P)$ に対応するので、$p^{-1}$ の降下点集合とタブロー $P$ の降下点集合は等しいです。このことから $p,p^{-1}$ の降下点を決めたときの順列の個数が求められます。そのまま式にすると二重ループになりますが、単純にすることができます。

自作問題
$(1,2,\ldots,N^2)$ の順列であって、最長増加部分列の長さが $N$、最長減少部分列の長さが $N$、かつ交代的なものを 1 つ構築してください。

ぜひ考えてみてください。

yukicoder No.2794 I Love EDPC-T
$(1,2,\ldots,N)$ の順列であって、最長増加部分列の長さが 2 であり、降下点集合が指定されたものであるものはいくつありますか。

難しいです。

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

ロビンソン・シェンステッド対応を一般化した、ロビンソン・シェンステッド・クヌース対応 (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$ は半標準タブローとなります。

定理 (RSK 対応): この対応は非負整数行列と同じ形の半標準タブローの組 $(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 対応により次の式が得られます。

系: $M_{\lambda\mu}=\displaystyle\sum_{\nu}K_{\nu\lambda}K_{\nu\mu}$

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}$$

に等しくなります。

4 次元以上のヤング図形も考えたくなりますが、あまりよい性質がないようです。

参考文献

本

• 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.
  • 対称群の教科書です。

Web 記事

https://codeforces.com/blog/entry/98167
https://qiita.com/hotman78/items/bbad58e5042da7837334
https://zenn.dev/339/articles/9ca3b883a85508