カタランの三角形を振り返る2

注　スマホでは表が正しく表示されません。CPでご覧ください。

はじめに

カタランの三角形とは、次のように対角線上にカタラン数が並ぶ三角形である。これはパスカルの三角形と対照して私的に名付けたものである。

1		111	111	111	111	111	111	111	111
1	1
1	2	2
1	3	5	5
1	4	9	14	14
1	5	14	28	42	42
1	6	20	48	90	132	132
1	7	27	75	165	297	429	429
1	8	35	110	275	572	1001	1430	1430
111	191	44	154	429	1001	2002	3432	4862	4862

これは縦方向だけの単位数列をもとに、パスカルの三角形と同じように、対角線を超えない範囲で、公式_nC_r＝_n－1C_r－1＋_n－1C_rの関係を満たしながら作られている。
この三角形の一般項を求めようと思った。パスカルの三角形でいえば、_nC_r＝n!/(n－r)!r!に対応するものである。

1　構成規則
　
碁盤の上のパスカルの三角形は、縦の単位数列と横の単位数列に対して、

1	1	1	1	1
1
1
1				111
111	111	111	111

左隣と上隣を加えることによって、次のように配置されていく。

1	1	1	1	1
1	2	3	4
1	3	6
1	4		20	111
111	111	111	111	70

これに対して、碁盤の縦方向の単位数列だけを出発点として、

1
1
1
1				111
111	111	111	111

左隣と上隣を加えることによって、数列を配置していく。最初、パスカルの三角形で1（左）＋1（上）＝2のマスには、1（左）＋0（上）＝1が入る。対角線を越えない範囲で、左隣と上隣をたしていくと次のような配置となる。

1
1	1
1	2	2	111
1	3	5	5	111
111	141	191	14	14

対角線上にカタラン数が並ぶ。
1, 1, 2, 5, 14, …
これをそれぞれ
1, 2, 3, 4, 5,…
倍したものが、
パスカルの三角形の対角線に並ぶ数列、
1, 2, 6, 20, 70, …
である。

2　カタランの三角形の拡大

カタランの三角形をもう少し拡大してみよう。

1		111	111	111	111	111	111	111	111
1	1
1	2	2
1	3	5	5
1	4	9	14	14
1	5	14	28	42	42
1	6	20	48	90	132	132
1	7	27	75	165	297	429	429
1	8	35	110	275	572	1001	1430	1430
111	191	44	154	429	1001	2002	3432	4862	4862

パスカルの三角形では、三角形の対称軸（正方形の対角線）に並ぶ数列には、次のような関係が成り立っていた。
1²＝1
1²＋1²＝2
1²＋2²＋1²＝6
1²＋3²＋3²＋1²＝20
1²＋4²＋6²＋4²＋1²＝70
…
同じようにカタランの三角形でも、正方形の対角線に並ぶ数列（カタラン数）は、角行の動きに並ぶ数列の2乗の和で構成されている。
1²＝1
1²＝1
1²＋1²＝2
1²＋2²＝5
1²＋3²＋2²＝14
1²＋4²＋5²＝42
1²＋5²＋9²＋5²＝132
…
1²＋8²＋27²＋48²＋42²＝4862

参考　　パスカルの三角形

1	1	1	1	1	1	1	1	1	1
1	2	3	4	5	6	7	8	9
1	3	6	10	15	21	28	36
1	4	10	20	35	56	84
1	5	15	35	70	126
1	6	21	56	126	252
1	7	28	84			924
1	8	36					3432
1	9							12870
111	111	111	111	111	111	111	111	111	48620

1²＋9²＋36²＋84²＋126²＋126²＋84²＋36²＋9²＋1²＝48620


3　カタラン数と二項係数の関係

ネピア数eが関連するオイラー公式が有名だが、カタラン数と二項係数をつなぐ
c_n＝1/(n＋1)･_2nC_n
も、オイラーの公式とよばれているという。
カタラン数は、様々な場面で現れてくるが、n×nの碁盤目状の経路のうち、対角線以下の最短経路としても有名である。これを使ってオイラーの公式を確認しておこう。（「高校数学こぼれ話、第17話」参照）
n×nの碁盤目状の経路に現れるカタラン数は次のように範囲外の経路を除くことによって求められる。

上の図で、P から Q への最短経路の総数 は_2nC_n通りある。
ここから範囲外の経路を除く。
（引用はじめ）
ここで、範囲外へ出る経路を考えて、範囲外へ初めて出る点を R とする。P→R の経路を破線で折り返すと、P→R→Q の経路はP'→R→Q の経路と 1 対 1 に対応する。P'→R→Q の経路数は_2nC_n－1 であるから、全体からこれを除いて、_2nC_n－_2nC_n－1となる。
（引用おわり）
あとは、これを計算する。
c_n
＝_2nC_n－_2nC_n－1
＝( 2n) ! /n! n!－(2n) !/( n－1) !(n＋ 1) !
＝( 2n) ! (n＋1－n)/n! (n＋ 1) !
＝( 2n) ! / n !(n＋ 1) !
＝1/(n＋1)･( 2n) ! /n! n!
＝1/(n＋1)･_2nC_n

ここで_2nC_nは、パスカルの三角形の対称軸（正方形の対角線）に並ぶ数列を表している。これを最初の部分を並べてみると、次のようになる。
1, 2, 6, 20, 70, 252, 924, 3432, 12870, 48620, …
これをそれぞれ
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …
で割ると、最初のカタラン数になる。
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …

これらはカタランの三角形の数列の特殊な値（正方形の対角線、直角二等辺三角形の底辺）である。

1		111	111	111	111	111	111	111	111
1	1
1	2	2
1	3	5	5
1	4	9	14	14
1	5	14	28	42	42
1	6	20	48	90	132	132
1	7	27	75	165	297	429	429
1	8	35	110	275	572	1001	1430	1430
111	191	44	154	429	1001	2002	3432	4862	4862

こんどはカタランの三角形の一般項を求めてみよう。

4　カタラン三角形の一般項

カタラン数の変数は1つ（ｎ）だが、カタランの三角形の一般項（数列）を求める場合、変数は2つ（nとm）必要になる。変数mは0≦m≦nの変域をもつ。

カタラン数を導くとき、n×nの碁盤目状の経路を考えたが、ここではn×mの碁盤目状の経路を想定して、最短経路を求めよう。


上の図で、P から Q への最短経路の総数（n×mの碁盤） は、(n＋m)!/n!m!通りある。ここから範囲外の経路を除く。
範囲外へ初めて出る点を R とする。P→R の経路（緑色）を赤い線で折り返すと、P'→R （橙色）となる。P→R→Q （緑色）の経路はP'→R→Q （橙色）の経路と 1 対 1 に対応する。P'→R→Q の経路数は、（n＋1）×（m－1）の碁盤に着目して、(n＋m)!/(n＋1)!(m－1)!となる。したがって、求める最短経路数は、(n＋m)!/n!m!－(n＋m)!/(n＋1)!(m－1)!となる。これを計算する。

(n＋m)!/n!m!－(n＋m)!/(n＋1)!(m－1)!
＝((n＋1)(n＋m)!－ m(n＋m)!)/(n＋1)!m!
＝((n＋1－m)(n＋m)!)/(n＋1)!m!

これをC_n,mとしよう。
すなわち、
C_n,m＝((n＋1－m)(n＋m)!)/(n＋1)!m!
である。これがカタランの三角形の一般項になる。

nが与えられたときのmは、0≦m≦nの範囲を動く。(n＋1－m)の因子は項数を制約する因子となっている。
n＝3で、具体的にみておこう。このときmは0≦m≦3で、4つの数列ができる。
C_3,0＝4･3! /4!･0!＝1
C_3,1＝3･4! /4!･1!＝3
C_3,2＝2･5! /4!･2!＝5
C_3,3＝1･6! /4!･3!＝5

m＝nのときは、
C_n,n＝((n＋1－n)(n＋n)!)/(n＋1)!n!
＝1･(2n) ! /(n＋1) ! n !
＝(2n) ! /(n＋1) ! n !
＝1/(n＋1)･( 2n) ! /n! n!
＝1/(n＋1)･_2nC_n
となり、カタラン数となる。

いま、縦方向に0≦n , 横方向に0≦m をとろう。0≦m≦nで、
C_n,m＝((n＋1－m)(n＋m)!)/(n＋1)!m!
を計算していくと、カタランの三角形になる。
最初から順序よく計算しなくても、直接、任意の細胞（C）の数を求めることができる。例、C_7,4＝4･11! /8!･4!＝165。

1		111	111	111	111	111	111	111	111
1	1
1	2	2
1	3	5	5
1	4	9	14	14
1	5	14	28	42	42
1	6	20	48	90	132	132
1	7	27	75	165	297	429	429
1	8	35	110	275	572	1001	1430	1430
111	191	44	154	429	1001	2002	3432	4862	4862

5　おわりに

カタランの三角形とは、次のように対角線上にカタラン数が並ぶ三角形である。

1		111	111	111	111	111	111	111	111
1	1
1	2	2
1	3	5	5
1	4	9	14	14
1	5	14	28	42	42
1	6	20	48	90	132	132
1	7	27	75	165	297	429	429
1	8	35	110	275	572	1001	1430	1430
111	191	44	154	429	1001	2002	3432	4862	4862

これは縦方向だけの単位数列をもとに、パスカルの三角形と同じように、対角線を超えない範囲で、公式_nC_r＝_n－1C_r－1＋_n－1C_rの関係を満たしながら作られている。
この三角形の一般項を求めようと思った。パスカルの三角形でいえば、_nC_r＝n!/(n－r)!r!に対応するものである。
調べていくと、ある記事（注）から、C_n,m＝((n＋1－m)(n＋m)!)/(n＋1)!m!であることを知った。しかし、これの導き方は書かれいなかった。どのようにこの公式を導けばよいのだろうか。これを課題とした。

パスカルは隣り合う2つの細胞の比例関係を帰納し、その比例関係から組合せの公式_nC_r＝n!/(n－r)!r!を作った。これを手本にして、比例関係を見つけようとしたができなかった。カタラン数の導き方には、組合せと漸化式の考え方があった。カタランの三角形には漸化式は参考にならないように思えた。組合せを参考すればいいような気になっていた。求める公式は高校数学程度のような気もしたが、もっと高度な数学が必要な気もした。わからないまま、1週間ほど経過した。最短経路の総数に着目すればいいのではないかと寝床のなかで思いついた。
カタラン数を求める図

を参考にして、次の図を作成し、カタランの三角形の一般項を導いた。


導いてみると、高校数学程度でレベルは低いのだが、自分の身の丈に合っていて、感動したものである。カタランの三角形は、パスカルの三角形と対照したもので、わたしの命名である。対角線上に（n＝m）カタラン数が並ぶところは面白いが、カタラン数自体と比べれば、魅力に欠けているような気がしている。カタラン数は様々な場面（トーナメント表の場合の数、多角形の三角形分割など）で現れている。こんどはこちらに着目してみよう。

（注）カタラン数　山上滋　http://sss.sci.ibaraki.ac.jp/teaching/catalan.pdf