公式が母関数から導かれていたが、

フィボナッチ数列の一般項を表す式は「ビネの公式」と呼ばれている。ここに黄金数が出てくる。これはフィボナッチ数列の漸化式を解く過程で確認できる。

小林さんは「ビネの公式」をフィボナッチ数列の母関数から求めている。フィボナッチ数列を0からはじめ、
　　　　0,1, 1, 2, 3, 5, 8, 13, 21, …
この母関数を求めている。この母関数はフィボナッチ数列を1からはじめる、
　　　　1, 1, 2, 3, 5, 8, 13, 21, …　　　　
ときの母関数とは異なっている。0からの場合は、分子xとなるが、1からの場合は、分子が1となる。分母は1－x－x²。

0から始めるとその後の展開がスムーズで、それをまねて、1からの場合でやってみたが、うまく導けなかった。

今日、フィボナッチ数列の漸化式からやってみて、「ビネの公式」（94ページ）と同じ公式が出て来た。1から始める場合、初項a₁＝1だが、0から始める場合の初項はa₁＝1ではなく、a₀＝0となっていて、納得した。0から始める場合でもa₁＝1だった。

a₀＝0と初項を延長することによって、母関数での変形がやりやすくなっていた。

フィボナッチ数列と「階段上り」2

パスカルの三角形に「階段」を設定しみよう。
　　
左側の１は間隔1で並んでいるとする。右側の１は間隔2で並んでいるとする。階段は左側を下、右側を上として、同じ数字同士（3と3,4と4など）をつなぐ。右側は2の間隔だから、数字1の間に階段の上部がくる場合がある。次のようになる。

右の青い数字がフィボナッチ数列である。
　　　1, 1, 2, 3, 5, 8, 13, 21, …
「何段あっても、最後が1段で上るときの場合の数は「前回の場合の数」となり、最後を2段で上るときは「前々回の場合の数」となり、その合計が着目している階段の上り方の場合の数となる。」これは上の数列で3＋5＝8、5＋８＝13など確認できる。

もう少し立ち入ってみよう。
フィボナッチ数列の項を、パスカルの三角形の要素で表わすと次のようになる。
1 ＝ ₀C₀
1 ＝ ₁C₀
2 ＝ ₂C₀＋₁C₁
3 ＝ ₃C₀＋₂C₁
5 ＝ ₄C₀＋₃C₁＋₂C₂
8 ＝ ₅C₀＋₄C₁＋₃C₂
13＝₆C₀＋₅C₁＋₄C₂＋₃C₃
……
Cで表示すると、階段は、左下添え字が1つずつ減り、右下添え字が1つずつ増えていく過程に対応しているとわかる。
これがどうしてフィボナッチ数列になるかといえば、パスカルの三角形が、
　_nC_r＝_n－1C_r－1＋_n－1C_r
という規則で並べられているからである。nに対して、２つのn－1が、１つ前の「階段」と、２つ前の「階段」に位置していることによっている。全体の関係が、それを構成する要素においても成立していることによっている。

3,5,8で確認してみよう。
3＝　　 ₃C₀＋₂C₁
＋　　　＋　＋
5＝₄C₀＋₃C₁＋₂C₂
　　↓　　↓　　↓　　₃C₀＋₃C₁＝₄C₁　,　₂C₁＋₂C₂＝₃C₂　,　₄C₀＝₅C₀
8＝₅C₀＋₄C₁＋₃C<sub>2

3</sub>C₀（2つ前の階段）＋₃C₁（1つ前）＝₄C₁　,　₂C₁（2つ前）＋₂C₂（1つ前）＝₃C₂　,　₄C₀（1つ前、2つ前は0）＝₅C₀

5,8,13でも確認しておこう。
5 ＝　　 ₄C₀＋₃C₁＋₂C₂
＋　　　 ＋　　＋　　
8 ＝ ₅C₀＋₄C₁＋₃C₂
　　　↓　 ↓　　↓　　↓　₄C₀＋₄C₁＝₅C₁　,　₃C₁＋₃C₂＝₄C₂　,　₅C₀＝₆C₀　,　₂C₂＝₃C₃
13＝₆C₀＋₅C₁＋₄C₂＋₃C₃

こんどは一般的な階段、フィボナッチ数列の一般項についてみておこう。

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

左下添え字が1つずつ減り、右下添え字が1つずつ増えている。どこで終わるかといえば、_nC_rのnの半分程度で終わるが、偶数か奇数かによって区別される。rに着目して、区別してみよう。左下添え字が偶数の場合、nとrは同じ値で終わる（₂C₂、₃C₃）。それはn/2にあたる。奇数の場合、nとrは異なる値（₃C₂）でrは1だけ小さい。これをガウス記号[　]（ある値を超えないもっとも大きな整数）を用いると、偶数と奇数の場合を統一して把握できる。[4/2]＝2、[6/2]＝3、[5/2]＝2が最終項のrの値である。パスカルの三角形に出てくるフィボナッチ数列の一般項Fnは
　　　Fn＝_nC₀＋_n－1C₁＋_n－2C₂＋……＋_n－[n/2]C_[n/2]
となる。

注　図は「やまでぃーのブログ」を拝借した。

フィボナッチ数列と「階段上り」

パスカルの三角形にフィボナッチ数列が出てくる理由を「階段上り」の方法で説明してある（小林吹代『ベルヌーイ数』）。この階段の上り方は1段か2段の2通りである。0段、1段、2段、3段、…と場合の数を数えていく。階段の最後の1歩を、1段で上るか、2段で上るかの2種類で場合分けをする。何段あっても、最後が1段で上るときの場合の数は「前回の場合の数」となり、最後を2段で上るときは「前々回の場合の数」となり、その合計が着目している階段の上り方の場合の数となる。

　　　1, 1, 2, 3, 5, 8, 13, 21, …

パスカルの三角形を斜めに足したときにフィボナッチ数列が出てくる（図省略）。

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

昨日の記事（「カタランの三角形を振り返る2」）は文字数の制限に引っ掛かり、本来の形では投稿できなかった。パスカルの三角形の図とまえがきを削除することになった。それで補完しておくことにしよう。本来の目次は次のようだった。

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

まえがき
はじめに
1　構成規則
2　カタラン三角形の拡大
3　カタラン数と二項係数の関係
4　カタラン三角形の一般項
5　おわりに

「まえがき」が入らなかった。まえがきは次のようだった。

まえがき

5年ほど前にカタラン数について考察した。先日、その記事にコメントが付いた。カタラン数の独特な捉え方が披露してあると思い、考えてみたが、よくわからない。いろいろ検索してみると、「カタラン予想」というものがあった。コメントはこれに関連するものだと思った。これは「カタラン数」とはまったく違った分野の問題であると結論した。

以前の記事の内容も忘れかけていたので、ここにまとめておくことにした。カタラン数が現れる具体的な場面に着目したのではなく、パスカルの三角形と対照して、構成規則からカタラン数を見たもので、カタラン三角形の一般項を求めることを課題としていた。


日記

このブログの1記事は30000文字が最大だった。昨日投稿したのは29764文字である。これは目に見える文字数ではなく、表や色などを示すタグも含めた文字数である。記事は表が多く、このタグで文字数を消費していた。プレブューは問題なく表示されていたが、いざ投稿する段になって、投稿不可となった。そのときは33331文字だった。パスカルの三角形の表を1つ削って、29984まで削除したが、受け付けられなかった。文字数は目安ということだった。さらに「まえがき」を削減した。

文字制限があることを知ったが、これまでで1番長いと思っていた「跳ぶのか、踊るのか。ーーロドスはマルクスの薔薇（全）」の文字数を調べてみると、26381だった。これも結構な文字数だったが（90％弱）、記事のページ数から言えば、雲泥の差がある。

カタランの三角形を振り返る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

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

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

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