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

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

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週間ほど経過した。最短経路の総数に着目すればいいのではないかと寝床のなかで思いついた。
カタラン数を求める図

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


カタランの三角形3、カタランの三角形4を参考。

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

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

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

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

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

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

カタランの三角形

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

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, …
である。

対称軸の数列とカタラン数

トーナメント戦の総数や最短経路の数などを求めるときに出てくるカタラン数c_nは
c_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, …

カタラン数について調べてみよう。

三角形の対称軸にならぶ数列2

三角形の対称軸にならぶ数列には次の関係が成り立っている。
_nC₀²＋_nC₁²＋_nC₂²＋……＋_nC_n²＝_2nC_n
これは
(1＋x) ⁿ(1＋x) ⁿ＝(1＋x) ²ⁿ
のxⁿの係数を比較することによつて導くことができる。
左辺(1＋x) ⁿ(1＋x) ⁿ
＝(_nC₀＋_nC₁ x＋_nC₂x²＋……＋_nC_nxⁿ)(_nC₀＋_nC₁ x＋_nC₂x²＋……＋_nC_nxⁿ)

xⁿの係数は、
_nC₀･_nC_n＋_nC₁･_nC_n－1＋……＋_nC_r･_nC_n－r＋……＋_nC_n･_nC₀
となる。
ここで
_nC_r＝_nC_n－r
だから、xⁿの係数は、
_nC₀²＋_nC₁²＋_nC₂²＋……＋＋_nC_n²
となる。
右辺の_2nC_nのxⁿの係数は公式そのまま
_2nC_n
である。
したがって、
_nC₀²＋_nC₁²＋_nC₂²＋……＋_nC_n²＝_2nC_n
縮めると、
_k＝0Σⁿ(_nC_k)²＝_2nC_n
となる。

エクセルには平方和の関数SUMSQ、組み合わせの関数COMBINがある。これを利用すると最初の数列は次のようになる。

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

三角形の対称軸にならぶ数列

1²＝1
1²＋1²＝2
1²＋2²＋1²＝6
1²＋3²＋3²＋1²＝20
1²＋4²＋6²＋4²＋1²＝70
……

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
1	7	28	84
1	8	36
1	9
111	111	111	111	111	111	111	111	111	111

一般に次の関係が成り立っている。
_nC₀²＋_nC₁²＋_nC₂²＋……＋_nC_n²＝_2nC_n

パスカルの三角形と母関数5

フィボナッチ数列の母関数をFとすれば、
F＝f₁＋x²f₂＋x⁴f₃＋x⁶f₄＋……
となる。
f_n＝(1－x) ^－nだから、Fは次のようになる。
F＝f₁＋x²f₂＋x⁴f₃＋x⁶f₄＋……
＝(1－x) ^－1＋x²(1－x) ^－2＋x⁴(1－x) ^－3 ＋x⁶(1－x) ^－4＋……
これは初項(1－x) ^－1、公比x²(1－x) ^－1の無限等比級数である。（母関数表わす冪（ベキ）級数は形式的な級数なので収束条件は考えなくてもいいのだという）。
F＝(1－x) ^－1 / (1－x²(1－x) ^－1)
＝1/((1－x)－x²)
＝1/(1－x－x²)
これがフィボナッチ数列の母関数である。

F＝1/(1－x－x²)
＝1＋x＋2x²＋3x³＋5x⁴＋8x⁵＋13x⁶＋……
＝₀C₀＋₁C₀x＋(₂C₀＋₁C₁)x²＋(₃C₀＋₂C₁)x³＋(₄C₀＋₃C₁＋₂C₂)x⁴＋(₅C₀＋₄C₁＋₃C₂)x⁵＋……＋(_nC₀＋_n－1C₁＋_n－2C₂＋……＋_n－[n/2]C_[n/2])xⁿ＋……
まとめると、次のようになる。
F＝1/(1－x－x²)＝_n＝0Σ^∞C_nxⁿ
ここでC_nは
C_n＝_k＝0Σ^[n/2]_n－kC_k
である。

（注）
1/(1－x－x²)を内的に展開して_n＝0Σ^∞C_nxⁿを導く方法もあるようだが、複雑でよくわからない。ここでは、以前の記事（フィボナッチ数列の確認、フィボナッチ数列の一般項）の結果を外的に結びつけたものである。

パスカルの三角形と母関数4

次のように並べたパスカルの三角形において、水平方向は母関数(1＋x) ⁿによつて、垂直方向は母関数(1－x) ^－nで統一的に見ることができた。


これをオリジナルの数3角形で確認してみよう。

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
1	7	28	84
1	8	36
1	9
111	111	111	111	111	111	111	111	111	111

これは将棋盤のように見えるので、駒の動きを援用しよう。水平方向の母関数(1＋x) ⁿ（二項展開）の係数（1,11,121,1331,14641,……）は直角二等辺三角形の斜辺に並ぶ。この動きは角行の動きに見立てることができる（左下から右上の方向）。
垂直方向の母関数(1－x) ^－nの係数は、水平方向と垂直方向のどちらにも並んでいる。上からも左からも
f₁ , f₂ , f₃ , f₄ , …
が並んでいる。これは飛車の軌跡に見立てることができる。

フィボナッチ数列はこの将棋盤を桂馬跳びすることによって作られる。左側の単位数列の1から桂馬跳びしていく。例えば、赤色で示された1,5,6,1はフィボナッチ数列の7番目（左の単位数列の上から7番目に対応する）の項13になる。桂馬跳びだから上に2つ移動するときに右へ1つ移動する。右へ移動するときf₂ , f₃ , f₄ , …を横切り、その項を取り込んでいく。上に2つ移動するから取り込む次の母関数の項の次数は2つずれる。
桂馬跳びによって取り込まれていく数は次のようになる。最上段（111…）は縦のf₁である。2段目（123…）は縦の f₂、3段目（136…）はf₃である。フィボナッチ数列の最初は次のようになる。

1	1	1	1	1	1	1	1	1	1
		1	2	3	4	5	6	7	8
				1	3	6	10	15	21
						1	4	10	20
								1	5
1	1	2	3	5	8	13	21	34	55
111	111	111	111	111	111	111	111	111	111

桂馬跳びで取り込む項は、次の母関数の次数を2つずらして、同次になった項と言いかえることができる。
フィボナッチ数列の母関数をFとすれば、
F＝f₁＋x²f₂＋x⁴f₃＋x⁶f₄＋……
となる。
これを求めてみよう。