カタランの三角形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