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

トーナメント戦の総数や最短経路の数などを求めるときに出てくるカタラン数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₄＋……
となる。
これを求めてみよう。

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

縦に並ぶ数列の母関数は、一般にf_n＝(1－x) ^－nとなる。これを書き下してみよう。

f(x)＝(1－x) ^－nをマクローリン展開する。f(0)＝1
f '(x)＝n(1－x) ^－n－1　f '(0)＝n
f ''(x)＝n(n＋1)(1－x) ^－n－2　　f ''(0)＝n(n＋1)
f⁽³⁾(x)＝n(n＋1)(n＋2)(1－x) ^－n－3　 f⁽³⁾(0)＝n(n＋1)(n＋2)
…
f^(k)(x)＝n(n＋1)…(n＋k－1)(1－x) ^－n－k 　　 f^(k)(0)＝n(n＋1)…(n＋k－1)
…
f⁽ⁿ⁾(x)＝n(n＋1)…(n＋(n－1))(1－x) ^－n－n 　　 f⁽ⁿ⁾(0)＝n(n＋1)…(n＋(n－1))
したがつて、
(1－x) ^－n
＝1＋nx＋1/2!･n(n＋1)x²＋1/3!･n(n＋1)(n＋2)x³ ＋……＋1/n!･n(n＋1)…(n＋(n－1))xⁿ
＝1＋_nC₁ x＋_n＋1C₂x²＋_n＋2C₃x³＋……＋_n＋(n－1)C_nxⁿ
縦に並ぶ数列の母関数の一般項は、
_n＋(k－1)C_kx^k
であり、xの0次、1次、2次、3次、…の係数を見ると、
それぞれ、
単位数（1,1,1,…）、自然数（1,2,3,…）、三角数（1,3,6…）、四面体数（1,4,10,…）…
の係数の一般項を表していることがわかる。

また、f_n＝(1－x) ^－n
＝1＋nx＋1/2!･n(n＋1)x²＋1/3!･n(n＋1)(n＋2)x³ ＋……
＝1＋_nC₁ x＋_n＋1C₂x²＋_n＋2C₃x³＋……
に、n＝1,2,3,4,…を代入すると、
f₁＝(1－x) ^－1＝1＋x＋x²＋x³ ＋……
f₂＝(1－x) ^－2＝1＋2x＋3x²＋4x³ ＋…
f₃＝(1－x) ^－3＝1＋3x＋6x²＋10x³ ＋…
f₄＝(1－x) ^－4＝1＋4x＋10x²＋20x³ ＋…
…
となり、
縦に並ぶ数列は母関数(1－x) ^－nで統一的に把握できることがわかる。


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

対照しておこう。
(1＋x) ⁿ
＝1＋nx＋1/2!･n(n－1)x²＋1/3!･n(n－1)(n－2)x³ ＋……
＝1＋_nC₁ x＋_nC₂x²＋_nC₃x²＋……
(1－x) ^－n
＝1＋nx＋1/2!･n(n＋1)x²＋1/3!･n(n＋1)(n＋2)x³ ＋……
＝1＋_nC₁ x＋_n＋1C₂x²＋_n＋2C₃x³＋……

こんどは斜めに横切る（桂馬跳び）フィボナッチ数列の母関数をとりあげよう。

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

単位数（1,1,1,…）を係数にもつ関数（母関数）は次のようになる。
1＋x＋x²＋…＋xⁿ＋…
これは初項1、公比x (|x|＜1)の無限等比級数である。したがって、
1＋x＋x²＋…＋xⁿ＋…
＝1/(1－x)
＝(1－x) ^－1
これをf₁としよう。

自然数（1,2,3,…）の数列は、単位数（1,1,1,…）の数列を1つずつ次数をずらしてたすことによって得られる。
1　1　1　1　1　1
　 1　1　1　1　1
　　　1　1　1　1
　　　　 1　1　1　

1　2　3　4　5　
これを係数にもつ関数は次のようになる。
1＋2x＋3x²＋…＋nx^n－1＋…

これはf₁を1つずつ次数をずらしてたすことによって得られる。
＝f₁＋xf₁＋x²f₁＋…＋xⁿf₁＋…
＝(1＋x＋x²＋…＋xⁿ＋…)×f₁
＝f₁×f₁
＝f₁²
＝(1－x) ^－2
これをf₂とする。

三角数（1,3,6…）の場合は、
1＋3x＋6x²＋…＋1/2･n(n－1)x^n－2＋…
となる。これはf₂を1つずつ次数をずらしてたすことによって得られる。
＝f₂＋xf₂＋x²f₂＋…＋xⁿf₂＋…
＝(1＋x＋x²＋…＋xⁿ＋…)×f₂
＝f₁×f₂
＝(1－x) ^－3
＝f₃
…
縦に並ぶ数列の母関数は、一般にf_n＝(1－x) ^－nとなる。
こんどはf(x)＝(1－x) ^－nをマクローリン展開して、係数を確認してみよう。

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

母関数とは、数列の項
a₀, a₁, a₂,…, a_n
を係数とする整関数
a₀＋a₁x＋ a₂x²＋…＋ a_n xⁿ
のことである。

例えば、1,3,3,1の母関数は(1＋x) ³である。

一般に、パスカルの三角形において水平方向に並ぶ数列
_nC₀ , _nC₁ , _nC₂ , … , _nC_n
の母関数は
(1＋x) ⁿで与えられる。これは二項展開そのものである。

パスカルの三角形を直角三角形の形に並べてみる（左側に傾け、左側を縦にそろえる）と、次のようになる。

ここで水平方は母関数(1＋x) ⁿで統一的に見ることができる。
垂直方向には、
単位数（1,1,1,…）、自然数（1,2,3,…）、三角数（1,3,6…）、四面体数（1,4,10,…）が並ぶが、これらの数列は
母関数(1－x) ^－nで統一的に見ることができるという。これを確かめてみよう。

桂馬跳びとフィボナッチ数列

数3角形を桂馬跳びしてできる数列の和の一般項anは
an
＝_k＝0Σ^[n/2]_n－kC_k
＝_nC₀＋_n－1C₁＋_n－2C₂＋……＋_n－[n/2]C_[n/2]
となった。
これがフィボナッチ数列の条件
an－1＋an＝an＋1
を満たしていることを見ておこう。

(1) nが偶数の場合
n＝2mとおくと、
an－1＋an
＝a2m－1＋a2m
＝　　　_2m－1C₀＋_2m－2C₁＋　……　＋_mC_m－1
＋_2mC₀＋_2m－1C₁＋_2m－2C₂＋　……　＋_mC_m
　　↓　　　　↓　　　　↓　　　　　　↓　　公式　_nC_r＝_n－1C_r－1＋_n－1C_rより
＝_2m＋1C₀＋_2mC₁＋_2m－1C₂＋　……　＋_m＋1C_m
＝a2m＋1
＝an＋1

(2) nが奇数の場合
n＝2m＋1とおくと、
an－1＋an
＝a2m－1＋a2m
＝　　　　_2mC₀＋_2m－1C₁＋　……　＋_m＋1C_m－1＋_mC_m
＋_2m＋1C₀＋_2mC₁＋_2m－2C₃＋　……　＋_m＋1C_m
　　↓　　　　↓　　　↓　　　　　　　　↓　　　　↓　　公式_nC_r＝_n－1C_r－1＋_n－1C_rより
＝_2m＋2C₀＋_2m＋1C₁＋_2mC₂＋　……　＋_m＋2C_m＋_m＋1C_m＋1
＝a2m＋2
＝an＋1

したがって、数3角形を桂馬跳びしてできる数列の和
an
＝_k＝0Σ^[n/2]_n－kC_k
＝_nC₀＋_n－1C₁＋_n－2C₂＋……＋_n－[n/2]C_[n/2]
は、
an－1＋an＝an＋1
を満たし、フィボナッチ数列になっている。


（注）前の記事の「フィボナッチ数列の一般項」を「数3角形を桂馬跳びしてできる数列の和の一般項」と読みかえてください。

フィボナッチ数列の一般項

数3角形にできるフィボナッチ数列の項のいくつかをCを使って表示すると、次のようになる。
5 ＝ ₄C₀＋₃C₁＋₂C₂
8 ＝ ₅C₀＋₄C₁＋₃C₂
13＝₆C₀＋₅C₁＋₄C₂＋₃C₃

左下添え字が1つずつ減り、右下添え字が1つずつ増えている。どこで終わるかといえば、_nC_rのnの半分程度（桂馬跳びなので、2:1）で終わるが、偶数か奇数かによって区別される。数3角形でいえば、偶数の場合は最上段（単位数）で終わり、奇数の場合は第2段（自然数）で終わる。rに着目して、区別してみよう。偶数の場合、nとrは同じ値で終わる（₂C₂、₃C₃）。それはn/2にあたる。奇数の場合、nとrは異なる値（₃C₂）でrは1だけ小さい。これをガウス記号[　]（ある値を超えないもっとも大きな整数）を用いると、偶数と奇数の場合を統一して把握できる。[4/2]＝2、[6/2]＝3、[5/2]＝2が最終項のrの値である。
数3角形にできるフィボナッチ数列の一般項anは
an＝_nC₀＋_n－1C₁＋_n－2C₂＋……＋_n－[n/2]C_[n/2]
となる。
Σでまとめると、
an＝_k＝0Σ^[n/2]_n－kC_k
となる。（k＝0はΣ（シグマ）の真下、[n/2]が真上にあると思ってください。）