高校数学解説

文献あり

カタラン数とその拡張その3 〜標準ヤング盤を通したカタラン数の高次元化〜

ヤング図形,カタラン数,フック長の公式

1558

前回は，最短経路の問題を通してカタラン数の拡張をしてきました．
今回注目するのは，初回でも紹介したカタラン数の次の性質です．

$2 \times n$ のマス目に $1$ から $2 n$ までの数字を１つずつ書き込むとき，次の条件を満たす方法の総数は，カタラン数 $c_{n}$ に等しい

横に隣り合う任意の2つのマスについて，左に書かれた数字よりも右に書かれた数字の方が大きい．
縦に隣り合う任意の2つのマスについて，上に書かれた数字よりも下に書かれた数字の方が大きい．

今回はこれを拡張して，次のような問題を考えてみましょう．

高次元カタラン数

$m \times n$ のマス目に $1$ から $m n$ までの数字を１つずつ書き込むとき，次の条件を満たす方法の総数を $C_{n}^{m}$ で表す．

横に隣り合う任意の2つのマスについて，左に書かれた数字よりも右に書かれた数字の方が大きい．
縦に隣り合う任意の2つのマスについて，上に書かれた数字よりも下に書かれた数字の方が大きい．

$C_{n}^{m}$ は，最短経路に当てはめれば，次のように意味づけすることもできます．

$R^{m} = {(x_{1}, x_{2}, x_{3}, \dots, x_{m}) | x_{1}, x_{2}, x_{3}, \dots, x_{m} \in R}$ 上の $(0, 0, \dots, 0)$ から $(n, n, \dots, n)$ への最短経路で，領域 $x_{1} \geq x_{2} \geq x_{3} \geq \dots \geq x_{m}$ 内にあるものの総数は， $C_{n}^{m}$ となる．

$m \times n$ のマス目に順番に $1$ から $m n$ までの数字を順番に書き込んでいくと考え，
最短経路において $x_{i}$ 軸方向の移動を $i$ 行目に数字を書き込むことに対応させれば，
マス目と最短経路の間に1対1対応が構成できる．
よって最短経路の総数は $C_{n}^{m}$ となる．

今回は，この $C_{n}^{m}$ を与える式を考えてみます．

フック長の公式

まず準備として，いくつかの用語，記号を定義します．

自然数 $N$ に対して，自然数の組 $(k_{1}, k_{2}, k_{3}, \dots, k_{n})$ が
$N = k_{1} + k_{2} + k_{3} + \dots + k_{n}, k_{1} \geq k_{2} \geq k_{3} \geq \dots \geq k_{n}$
を満たすとき，これを自然数 $N$ の分割(Partition)という．

この分割は，下図のように $i$ 行目に $k_{i}$ 個の正方形を並べた図形として表現できる．
これをヤング図形(Young diagram)という．

!FORMULA[27][-992523928][0]に対するヤング図形 $(k_{1}, k_{2}, k_{3}) = (5, 4, 2)$ に対するヤング図形

また，ヤング図形に含まれる $1 \times 1$ の正方形を箱(Box)と呼ぶ.
$i$ 行 $j$ 列にある箱を $(i, j)$ と表す．

１つの分割は１つのヤング図形と1対1に対応する．
自然数 $N$ の分割に対応するヤング図形の箱に $1$ から $N$ までの数字を1つずつ書き込むとき，次の条件を満たすものを，標準ヤング盤(Standard young tableaux)あるいは単に標準盤(Standard tableaux)という．

横に隣り合う任意の2つのマスについて，左に書かれた数字よりも右に書かれた数字の方が大きい．
縦に隣り合う任意の2つのマスについて，上に書かれた数字よりも下に書かれた数字の方が大きい．

ヤング図形 $λ$ に対して，箱の個数を $| λ |$ ，標準ヤング盤の個数を $S Y T_{λ}$ で表す.また箱 $d$ がヤング図形 $λ$ に含まれることを $d \in λ$ で表す.

ヤング図形 $λ$ 上の箱 $d = (i, j)$ に対して，

箱 $d$
同じ列で箱 $d$ の下にある箱
同じ行で箱 $d$ の右にある箱

をあわせた集合を箱 $d$ におけるフック(Hook)といい，フックに属する箱の個数をフック長(Hook length)といって， $h_{λ} (d)$ あるいは $h_{λ} (i, j)$ で表す．

フック長が1である箱を角(Corner)という．

このとき，次の公式が成り立つことが知られています．強すぎです．

フック長の公式

ヤング図形 $λ$ について，次が成立する．
$S Y T_{λ} = \frac{| λ |!}{\prod_{d \in λ} h_{λ} (d)}$
ただし，分母の積は， $λ$ 上のすべての箱に対してそのフック長を掛けることを意味する．

証明は難しいですが，理解できないレベルでもないので，この記事の最後に載せようと思います．
まずはこの公式の威力を体感してみましょう．

まず，いろいろ試行錯誤した $c_{n}$ の一般項ですが，フック長の公式を使えば2秒で求められます！

$c_{n}$ は，分割 $(k_{1}, k_{2}) = (n, n)$ に対するヤング図形 $λ$ の標準盤の個数なので，
$c_{n} = S Y T_{λ} = \frac{| λ |!}{\prod_{d \in λ} h_{λ} (d)} = \frac{(2 n)!}{(n + 1)! n!} = \frac{1}{n + 1}_{2 n} C_{n}$

前回最初に紹介した傾き1の直線の最短経路の総数は，特殊な場合に限定すればこの公式で求められます．

$m \geq n$ とする． $(0, 0)$ から $(m, n)$ への最短経路で，直線 $y = x$ を越えないものの総数は，次のように表せる．
$\frac{m - n + 1}{m + 1}_{m + n} C_{m}$

最短経路において $x$ 軸方向の移動を，ヤング図形の $1$ 行目に数字を書き込むことに対応させ，
$y$ 軸方向の移動を，ヤング図形の $1$ 行目に数字を書き込むことに対応させると，
求める場合の数は，分割 $(k_{1}, k_{2}) = (m, n)$ に対するヤング図形 $λ$ の標準盤の個数に等しい．
よって，
$S Y T_{λ} = \frac{| λ |!}{\prod_{d \in λ} h_{λ} (d)} = \frac{(m + n)!}{\prod_{j_{1} = 1}^{m} h_{λ} (1, j_{1}) \prod_{j_{2} = 1}^{m} h_{λ} (2, j_{2})} = \frac{(m + n)!}{\frac{(m + 1)!}{m - n + 1} n!} = \frac{m - n + 1}{m + 1}_{m + n} C_{m}$

では早速これを使って， $C_{n}^{m}$ の一般項をもとめてみましょう！

高次元カタラン数

$C_{n}^{m}$ は分割 $(k_{1}, k_{2}, \dots, k_{m}) = (n, n, \dots, n)$ に対する標準盤の個数なので，フック長の公式を認めれば簡単に求められます．

$C_{n}^{m}$ は，次のように表せる．
$C_{n}^{m} = (m n)! \prod_{i = 1}^{m} \prod_{j = 1}^{n} \frac{1}{i + j - 1} = (m n)! \frac{0!}{n!} \frac{1!}{(n + 1)!} \frac{2!}{(n + 2)!} \dots \frac{(m - 2)!}{(m + n - 2)!} \frac{(m - 1)!}{(m + n - 1)!}$

超階乗 $s f (n) = \prod_{i = 1}^{n} i!$ を導入すれば，次のようにも表現できる．
$C_{n}^{m} = \frac{(m n)! s f (m - 1) s f (n - 1)}{s f (m + n - 1)}$

$λ$ を分割 $(k_{1}, k_{2}, \dots, k_{m}) = (n, n, \dots, n)$ に対するヤング図形とする．フック長の公式より，
$C_{n}^{m} = S Y T_{λ} = \frac{| λ |!}{\prod_{d \in λ} h_{λ} (d)} = \frac{(m n)!}{\prod_{i = 1}^{m} \prod_{j = 1}^{n} h_{λ} (i, j)} = (m n)! \prod_{i = 1}^{m} \prod_{j = 1}^{n} \frac{1}{i + j - 1}$
また，これを書き換えると，
$C_{n}^{m} = (m n)! \prod_{i = 1}^{m} \prod_{j = 1}^{n} \frac{1}{i + j - 1} = (m n)! \prod_{i = 1}^{m} \frac{(i - 1)!}{(i + n - 1)!} = \frac{(m n)! s f (m - 1) s f (n - 1)}{s f (m + n - 1)}$

フック長の公式の証明

フック長の公式にはいくつかの証明が知られていますが，ここでは1979年に発見されたC.Greene, A.Nijenhuis, H.S.Wilfらによる証明を紹介します．

フック長の積について成り立つべき漸化式を考え，それに確率論的な解釈を与えるというものです．

証明

まず，次の補題が成り立つ．

$S Y T_{λ} = \sum_{c \in λ, h_{λ} (c) = 1} S Y T_{λ ∖ {c}}$
ただし右辺の総和は，ヤング図形 $λ$ に対して，どこかの角を取り除いたヤング図形全体に対して，その標準盤の個数を足し合わせることを意味する．

$N$ 個の箱を持つヤング図形 $λ$ では，その標準盤において $N$ はどこかの角に存在する．
$N$ が角 $c$ にある $λ$ の標準盤の個数は， $λ$ から角 $c$ を取り除いて得られるヤング盤 $λ ∖ {c}$ の標準盤の個数に等しい．よって補題は成立する．

ヤング図形 $λ$ に対し， $H_{λ} = \prod_{c \in λ} h_{λ} (c)$ とする．
また， $l$ 個の角 $c_{k} = (α_{k}, β_{k}) (k = 1, 2, 3, \dots, l)$ を持つヤング図形 $λ$ に対し， $λ$ から $c_{k}$ を取り除いたヤング図形を $λ_{k}$ とする．

$| λ | = 1$ の場合は $S Y T_{λ} = \frac{1!}{H_{λ}} = 1$ が成り立つことと，
補題6に注意すれば，次のことが成り立てば良いとわかる．

主張
$n$ 個の箱をもつヤング図形 $λ$ において，
$\frac{n!}{H_{λ}} = \sum_{k = 1}^{l} \frac{(n - 1)!}{H_{λ_{k}}}$
が成立する．

ここで，この式を変形すると，
$\frac{n!}{H_{λ}} = \sum_{k = 1}^{l} \frac{(n - 1)!}{H_{λ_{k}}} ⟺ \frac{1}{n} \sum_{k = 1}^{l} \frac{H_{λ}}{H_{λ_{k}}} = 1$
となり，右辺は全確率空間と考えることができる．
これに確率論的解釈を与えてみよう．

まず，次のような試行を考える

フックウォーク

$λ$ を $n$ 個の箱をもつヤング図形とする．次のような操作を考える．
この操作をフックウォーク(Hook walk)という．

$λ$ から箱を無作為に $1$ つ選ぶ．
前に選んだ箱のフックの中にあり，それとは異なる箱を無作為に $1$ つ選ぶ．
(ii)を繰り返す．

このとき，必ず有限回の操作でどこかの角に到達する．
角 $c = (α, β)$ に到達する確率を $p_{λ} (c)$ あるいは $p_{λ} (α, β)$ で表す．

実はこのとき，
$p_{λ} (c_{k}) = \frac{1}{n} \frac{H_{λ}}{H_{λ_{k}}}$
が成り立つ．
これを証明できれば，左辺の総和は全確率空間であって $1$ に等しいので，フック長の公式が証明できたことになる．

まずは右辺について詳しく見ていく．
$h_{λ_{k}}$ は $h_{λ}$ から角 $(α_{k}, β_{k})$ を取り除いたものなので， $h_{λ_{k}}$ と $h_{λ}$ のフック長の間には次の関係がある．
$h_{λ_{k}} (i, j) = \begin{array}{r} {\begin{cases} h_{λ} (i, j) - 1 i = α_{k} \lor j = β_{k} \\ h_{λ} (i, j) o t h e r w i s e . \end{cases} \end{array}$

したがって， $i = α_{k} \lor j = β_{k}$ 以外においては分母と分子がキャンセルすることと， $h_{λ} (α_{k}, β_{k}) = 1$ に注意して，
$\frac{H_{λ}}{H_{λ_{k}}} = \prod_{i = 1}^{α_{k} - 1} \frac{h_{λ} (i, β_{k})}{h_{λ} (i, β_{k}) - 1} \prod_{j = 1}^{β_{k} - 1} \frac{h_{λ} (α_{k}, j)}{h_{λ} (α_{k}, j) - 1} = \prod_{i = 1}^{α_{k} - 1} (1 + \frac{1}{h_{λ} (i, β_{k}) - 1}) \prod_{j = 1}^{β_{k} - 1} (1 + \frac{1}{h_{λ} (α_{k}, j) - 1})$
を得る．

次に，左辺について考えてみる．

始点を $(i_{1}, j_{1})$ に固定したフックウォークについて考える．
$k$ 回目に選んだ箱を $(i_{k}, j_{k}) (i = 1, 2, \dots, m)$ で表すとする．

これに対し，集合 $A, B$ を次のように定める．（ただし重複は無視する）
$A = {i_{1}, i_{2}, \dots, i_{m}} B = {j_{1}, j_{2}, \dots, j_{m}}$
つまり， $A$ はフックウォークの経路に現れる行番号からなる集合で， $B$ は列番号からなる集合である．

このとき，始点が $(i_{1}, j_{1})$ であるという条件の下で行番号の集合が $A$ ，列番号の集合が $B$ となる条件付き確率を $p (A, B)$ で表す．

これに対し，次の補題が成り立つ．

$A = {a_{1}, a_{2}, \dots, a_{p}}, B = {b_{1}, b_{2}, \dots, b_{q}}$
とする．ただし， $a_{1} < a_{2} < \dots < a_{p}, b_{1} < b_{2} < \dots < b_{q}$
このとき，次が成立する．
$p (A, B) = \prod_{s = 1}^{p - 1} \frac{1}{h_{λ} (a_{s}, b_{q}) - 1} \prod_{s = 1}^{q - 1} \frac{1}{h_{λ} (a_{p}, b_{s}) - 1}$

行番号の集合が $A$ ，列番号の集合が $B$ であり，最初に選ぶ箱が $(a_{1}, b_{1})$ であることから，
2つ目に選ぶ箱は $(a_{1}, b_{2})$ あるいは $(a_{2}, b_{1})$ であり，これらが選ばられる確率は $\frac{1}{h_{λ} (a_{1}, b_{1}) - 1}$ である．
また，2つ目の箱として $(a_{1}, b_{2})$ を選んだ時， $(a_{1}, b_{2})$ からスタートしたものとみなせば，行番号の集合は $A$ ，列番号の集合が $B ∖ {b_{1}}$ ということになる． $(a_{1}, b_{2})$ を選んだ場合も同様．

よって， $p (A, B)$ には次の漸化式が成り立つ事がわかる．
$p (A, B) = \frac{1}{h_{λ} (a_{1}, b_{1}) - 1} {p (A ∖ {a_{1}}, B) + p (A, B ∖ {b_{1}})}$
これを使って，補題が成り立つことを $| A | + | B |$ に関する数学的帰納法で証明する．

$| A | + | B | = 2$ のとき
$A = a_{1}, B = b_{1}$ であり，左辺の確率は $1$ ，右辺は空積で $1$ なので成立．
$| A | + | B | = n - 1$ のとき成立すると仮定して， $| A | + | B | = n$ のとき
漸化式より，
$p (A, B) = \frac{1}{h_{λ} (a_{1}, b_{1}) - 1} (p (A ∖ {a_{1}}, B) + p (A, B ∖ {b_{1}})) = \frac{1}{h_{λ} (a_{1}, b_{1}) - 1} {\prod_{s = 2}^{p - 1} \frac{1}{h_{λ} (a_{s}, b_{q}) - 1} \prod_{s = 1}^{q - 1} \frac{1}{h_{λ} (a_{p}, b_{s}) - 1} + \prod_{s = 1}^{p - 1} \frac{1}{h_{λ} (a_{s}, b_{q}) - 1} \prod_{s = 2}^{q - 1} \frac{1}{h_{λ} (a_{p}, b_{s}) - 1}} = \frac{h_{λ} (a_{p}, b_{1}) - 1 + h_{λ} (a_{1}, b_{q}) - 1}{h_{λ} (a_{1}, b_{1}) - 1} \prod_{s = 1}^{p - 1} \frac{1}{h_{λ} (a_{s}, b_{q}) - 1} \prod_{s = 1}^{q - 1} \frac{1}{h_{λ} (a_{p}, b_{s}) - 1}$
ここで， $a_{1}$ 行目の長さを $u$ ， $b_{1}$ 列目の長さを $v$ とする．
$a_{p}$ 行目の長さは $b_{q}$ ， $b_{q}$ 列目の長さは $a_{p}$ であることも合わせて，
$h_{λ} (a_{1}, b_{1}) - 1 = u + v - a_{1} - b_{1}$
$h_{λ} (a_{p}, b_{1}) - 1 = b_{q} + v - a_{p} - b_{1}$
$h_{λ} (a_{1}, b_{q}) - 1 = u + a_{p} - a_{1} - b_{q}$
であるから， $h_{λ} (a_{1}, b_{1}) - 1 = h_{λ} (a_{p}, b_{1}) - 1 + h_{λ} (a_{1}, b_{q}) - 1$ が成り立つ．よって，
$p (A, B) = \prod_{s = 1}^{p - 1} \frac{1}{h_{λ} (a_{s}, b_{q}) - 1} \prod_{s = 1}^{q - 1} \frac{1}{h_{λ} (a_{p}, b_{s}) - 1}$

よって，補題は示された．

それではこれらを使って証明を完成させよう

$\frac{H_{λ}}{H_{λ_{k}}} = \prod_{i = 1}^{α_{k} - 1} (1 + \frac{1}{h_{λ} (i, β_{k}) - 1}) \prod_{j = 1}^{β_{k} - 1} (1 + \frac{1}{h_{λ} (α_{k}, j) - 1})$
であることは証明したので，この式の右辺を展開する．まず，
$\prod_{i = 1}^{α_{k} - 1} (1 + \frac{1}{h_{λ} (i, β_{k}) - 1}) = \sum_{A^{'} \subset {1, 2, \dots, α_{k} - 1}} \prod_{a \in A^{'}} \frac{1}{h_{λ} (a, β_{k}) - 1}$
が成り立つ．ここで，右辺の和において $A^{'}$ は ${1, 2, \dots, α_{k} - 1}$ の部分集合全体を動く． $A^{'}$ に $α_{k}$ を加えた集合を $A$ とすると，
$\prod_{i = 1}^{α_{k} - 1} (1 + \frac{1}{h_{λ} (i, β_{k}) - 1}) = \sum_{A} \prod_{a \in A, a \neq α_{k}} \frac{1}{h_{λ} (a, β_{k}) - 1}$
となる．ただし $A$ は $1, 2, 3, \dots, α_{k}$ の部分集合であって $α_{k}$ を含むもの全体を動く．同様に，
$\prod_{j = 1}^{β_{k} - 1} (1 + \frac{1}{h_{λ} (α_{k}, j) - 1}) = \sum_{B} \prod_{b \in B, b \neq β_{k}} \frac{1}{h_{λ} (α_{k}, b) - 1}$
であるから，
$\frac{H_{λ}}{H_{λ_{k}}} = \sum_{(A, B)} \prod_{a \in A, a \neq α_{k}} \frac{1}{h_{λ} (a, β_{k}) - 1} \prod_{b \in B, b \neq β_{k}} \frac{1}{h_{λ} (α_{k}, b) - 1}$
となる．補題7を使うと，
$\frac{1}{n} \frac{H_{λ}}{H_{λ_{k}}} = \frac{1}{n} \sum_{(A, B)} p (A, B)$
を得る．ここで最初に箱 $(a_{1}, b_{1})$ を選ぶ確率は $\frac{1}{n}$ で， $(A, B)$ をすべて動かせば $(α_{k}, β_{k})$ に達する経路の確率をすべて足すことになるので，この式の右辺は $p_{λ} (c_{k})$ に等しい．よってフック長の公式は示された． $◼$

いかかでしたでしょうか．最後はなかなか大変な証明になりましたが，これを機にカタラン数の面白さがわかってもらえたら嬉しいです．

参考文献

[1]

枡田幹也,福川由貴子, 格子から見える数学

投稿日：2022年3月30日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

dragoemon

143

31534

大学3年生です

他の人のコメント

コメントはありません。

読み込み中

dragoemon

カタラン数とその拡張その3 〜標準ヤング盤を通したカタラン数の高次元化〜

フック長の公式
高次元カタラン数
フック長の公式の証明
参考文献

カタラン数とその拡張 その3 〜標準ヤング盤を通したカタラン数の高次元化〜

フック長の公式

高次元カタラン数

フック長の公式の証明

証明

参考文献

この記事を高評価した人

この記事に送られたバッジ

投稿者

コメント

他の人のコメント

カタラン数とその拡張その3 〜標準ヤング盤を通したカタラン数の高次元化〜