1. \(_{2n}C_{n}\)について

R言語を用いて関数\(y=_{2x}C_x\quad(x=1,2,\ldots)\)の増加をグラフにして、その性質を調べた。

\(n\)が大きくなるにつれ、\(_{2n}C_n\)を手で計算するのは難しくなり、その増加の性質を調べることも手計算では難しい。そこで、 R言語を用いて計算を行う関数を作成した。

また、この関数を用いて\(y=\log_{10}{}_{2x}C_x\)のグラフを描くと直線に近いグラフになった。これにより、\(_{2n} C_n\)の近似値がわかる。

さらに、\(_{2n}C_n\)を計算する関数を作ることによって、ことでカタラン数を求める関数を作ることができる。カタラン数はネットワークシステムの信頼性の計測評価法の評価などで使われる重要な数字である。ゆえに、\(_{2n}C_n\)を求めることは重要である。

カタラン数とは

カタラン(Catalan　1814ー1894)とはベルギーの数学者である。カタラン数は彼の研究に因んで名づけられた数列である。 この数列(\(\{A_n\}\)とする)の定義は以下のようになる:

一般項

\(A_n=_{2n}C_n-_{2n}C_{n-1}=\dfrac{_{2n}C_n}{n+1}\)

漸化式

\(A_n=\displaystyle\sum^{n-1}_{k=0}A_kA_{n-k-1}\)

カタラン数が現れる現象

(1)\(n+1\)チームによるトーナメントの試合の組み合わせ

\(n+1\)チームの試合の総数を\(A_n\)とする。\(n+1\)チームを決勝戦からみて、\(k+1\)チームのAグループと\(n-k\)チームのBグループの二つに分けるとAの試合の仕方は\(A_k\)通りあり、Bの試合の仕方は\(A_{n-k-1}\)通りある。ゆえに2つのグループの数の積和\(A=\displaystyle\sum^{n-1}_{k=0}A_kA_{n-k-1}\)となる。これは漸化式によるカタラン数の定義になる。

(2)凸\(n+2\)角形を三角形に分割する総数

凸\(n+2\)角形を三角形に分割する総数を\(A_n\)、凸\(n+2\)角形の頂点を\(P_0,P_1,\ldots,P_{n-1}\)とすると、三角形\(P_nP_{n+1}P_k\)を作ってできる、凸\(k+2\)角形を三角形に分割する方法は\(A_{k}\)、凸\(n-k+1\)角形を三角形に分割する方法は\(A_{n-k-1}\)通りあるから二つの凸角形の分割の積和が総数になるから\(A_n=\displaystyle\sum^{n-1}_{k=0}A_kA_{n-k-1}\)となる。

このように様々な現象にカタラン数は現れる。これには全体を二つの分けたときにそれぞれがカタラン数で表すことができるという原理があるといわれている。

2. \(_{2n}C_{n}\)の関数作成の手順

\(_{m}C_{n}(m>n)\)は次のように定義される。

\(_{m}C_{n}=\dfrac{m!}{(m-n)!n!}\)

これより, \(_{2n}C_{n}=\dfrac{(2n)!}{(2n-n)!n!}=\dfrac{(2n)!}{(n!)^2}=\dfrac{(n+1)(n+2)\cdots 2n}{n!}\)

分母と分子それぞれの値を計算する関数を作成する。

2-1. \(n!\)(分母)を計算する関数

数列\(\{a_n\}\quad(n=1,2,\ldots)\)を次のように定める。

\(n!\)階乗を計算する関数は次のように作ることができる。

\(a_1=1,a_{n+1}=(n+1)\times a_n\)

すると,

\(a_1=1\)

\(a_2=(1+1)\times a_1=2\times1\)

\(a_3=(2+1)\times a_2=3\times2\times1\)

\(a_4=(3+1)\times a_3=4\times3\times2\times1\)

同様に計算すると

\(a_n=n!\)となる.

これを繰り返し処理(for)に用いると\(n!\)を計算する関数(“Factrial”)は次のようになる。

Factrial<-function(n){
  t=1
  for(i in 1:n){
    t<- i*t
  }
  t
}

\(t=1\)は\(a_1=1\)と定めたことに対応しており、

\(t\)に\(i\times t\)を代入することは\(a_{n+1}=(n+1)\times a_{n}\)に対応する。

例えば,\(n=1,2,3,4,5\)のときの\(n!\)の値は次のようになる。

for (j in 1:5) {
  n<- j
  print(Factrial(n))
}
## [1] 1
## [1] 2
## [1] 6
## [1] 24
## [1] 120

となる。

これも階乗を計算する関数であるが、ここでは“prod(1:n)”で\(n!\)を計算する。

prod(i)　(i=\(1,2,\ldots,10\))は次のようになる。

for (i in 1:10) {
  print(prod(1:i))
}
## [1] 1
## [1] 2
## [1] 6
## [1] 24
## [1] 120
## [1] 720
## [1] 5040
## [1] 40320
## [1] 362880
## [1] 3628800

2-2. \((n+1)\times(n+2)\times\cdots\times2n\)(分子)を計算する

2-1と同様に、2-1では\(n!\)すなわち\(1\times2\times\cdots\times n\)を計算する関数を作ったので、2-1の\(1\)を\(n+1\)、2-1の\(n\)を\(2n\)に書き直せばよい。 分母を計算する関数は以下のようになる。

molecule<-function(n){
  t<-1
  for(i in (n+1):(2*n)){
    t<- t*i
  }
  t
}

例えば、\(n=1,2,3,4,5\)の場合は

for (j in 1:5) {
  n<- j
  print(molecule(n))
}
## [1] 2
## [1] 12
## [1] 120
## [1] 1680
## [1] 30240

2-3.\(_{2n}C_n\)を計算する

\(_{2n}C_n=\dfrac{(n+1)\times(n+2)\times\cdots\times2n}{n!}\)より、

Combination<-function(n){
  #n!=prod(1:n),(n+1)*(n+2)*...*2n=molecule(n)としたので
  D<- molecule(n)*1/prod(1:n)
  D
}

とすればよい。 例えば、\(n=1,2,3,4,5\)の場合は

for (j in 1:5) {
  n <- j 
  print(Combination(n))
}
## [1] 2
## [1] 6
## [1] 20
## [1] 70
## [1] 252

2-4.カタラン数を計算する

上で求めた\(_{2n}C_n\)の関数を用いると、 \(A_n=\dfrac{_{2n}C_n}{n+1}\)より、

Catalan<-function(n){
  #カタラン数を計算する関数は_{2n}C_nを$n+1$で割ったものを考えればよい
  #_{2n}C_{n}の値を与える関数をC(n)としたので
  x<- Combination(n)/(n+1)
}

例えば、\(n=1,2,3,4,5,6,7\)の場合は

for (j in 1:7) {
  n <- j 
  print(Catalan(n))
}
## [1] 1
## [1] 2
## [1] 5
## [1] 14
## [1] 42
## [1] 132
## [1] 429

この\(_{2n}C_n\)を計算する関数とカタラン数を計算する関数により、次のような様々なグラフが書くことができる。

3 \(_{2n}C_n\)とカタラン数によるグラフ

3-1 関数\(y=_{2x}C_x\)のグラフ

\(y=\log_{10}{}_{2x}C_x\quad(x=1,2,\ldots,30)\)のグラフの関数とグラフは下のようになる。 下に\(y=_{2x}C_x\quad(x=1,2,\ldots,30)\)のグラフの関数とグラフを示す。

m<- 30
n<- 1:m
x<- n
y<- numeric(m)
for (i in x){
  y[i] <- Combination(i)
}
plot(x,y)

3-2 \(y=\log_{10}{}_{2x}C_{x}\)のグラフ

\(y=\log_{10}{}_{2x}C_{x}\quad (x=1,2,\ldots,30)\)のグラフは次のようになる。

m<- 30
n<- 1:m
x<- n
y<- numeric(m)
for (i in x){
  y[i] <- log10(Combination(i))
}
plot(x,y)

3-3 カタラン数列\(y=A_x\quad(x=1,2,\ldots,10)\)のグラフ

次のように関数を作れば\(y=\dfrac{_{2x}C_x}{x+1}\)のグラフになる。

m<- 30
n<- 1:m
x<- n
y<- numeric(m)
for (i in x){
  y[i] <- Catalan(i)
}
plot(x,y)

3-4\(\{A_n\}\)をカタラン数列とするときの\(\log_{10}{}A_x\)のグラフ

m<- 30
n<- 1:m
x<- n
y<- numeric(m)
for (i in x){
  y[i] <- log10(Catalan(i))
}
plot(x,y)

3-5 \(\{A_n\}\)をカタラン数列とするときの\(\dfrac{A_x}{4^xx^\frac{-3}{2}}\)のグラフ

m<- 30
n<- 1:m
x<- n
y<- numeric(m)
for (i in x){
  y[i] <- Catalan(i)/(4^i*i^(-3/2))
}
plot(x,y)

\(_{2n}C_n\)の関数からわかったこと

\(_{2n}C_n\)を計算する関数を作ることで、\(_{2n}C_n\)の関数の増加を様々な視点で見ることができた。

まず\(y=_{2x}C_x\quad x=1,2,\ldots,30\)のグラフ(3-1)は指数的に増加している。

\(y=\log_{2x}{}C_x\)のグラフ(3-2)を見ると直線に近い形になっているので一次関数のグラフと近似できる。

このグラフの傾きを考えると、\(y=\dfrac{1}{2}x\)に近づいていくと考えられる。

これにより、\(x\)から大まかな\(y\)の値が求まり\(_{2x}C_x\)の近似値がわかる。さらにこれを\(x+1\)で割ることで、\(x\)におけるカタラン数の近似値を求めることができるようになった。

また、\(y=\log\dfrac{_{2x}C_x}{n+1}\)のグラ(3-4)を見ると、\(x=25\)のとき、\(y=14\)となる。これにより、カタラン数の第25項は\(10^{14}\)になる。このように\(n\)が25のように大きい数をとってもこの関数によって大体の値を求めることができた。

そして、最後のグラフ(3-5)をみると、0.55に近づいていくと予測される。具体的に何に収束するか考える。

ここで、スターリングの漸近公式を用いる。

スターリングの公式

式だけで書けば次が成り立つことである。ただし、“\(\sim\)”は近似を表す記号とする。

\(n!\sim\sqrt{2\pi n}\left(\dfrac{n}{e}\right)^n\)

スターリングの公式は統計力学などに使われる。

ここでは厳密な証明は行わず、証明の方針と流れを紹介する。

スターリングの公式の証明の方針

\(\displaystyle\lim_{n\rightarrow \infty}\dfrac{n!}{\sqrt{2\pi n}e^{-n}n^n}=1\) を示す。

次のような流れで示す。

(1)\(a_n=\dfrac{n!}{\sqrt{n}}\left(\dfrac{e}{n}\right)^n\)について、\(n\longrightarrow\infty\)が0より大きい数\(\alpha\)に収束することを示す。 (2)\(\alpha=\sqrt{2\pi}\)をウォリスの公式

\(\displaystyle\lim_{n\rightarrow \infty}\dfrac{2^{4n}(n!)^4}{((2n)!)(2n+1)}=\dfrac{\pi}{2}\)

で示す。

証明

\(\displaystyle\lim_{n\rightarrow \infty}\dfrac{2^{4n}(n!)^4}{((2n)!)(2n+1)}=\lim_{n\rightarrow\infty}\left\{\dfrac{n!}{\sqrt{n}}\left(\dfrac{e}{n}\right)^n\right\}^4\times\left\{\dfrac{\sqrt{2n}}{(2n)!}\left(\dfrac{2n}{e}\right)^{2n}\right\}^2\times\dfrac{n}{2^{4n+1}}=\dfrac{\pi}{2}\)

これより,(1)を用いて

\(\dfrac{\alpha^4}{\alpha^2}\displaystyle\lim_{n\rightarrow\infty}\dfrac{n}{2(2n+1)}=\dfrac{\pi}{2}\)

よって

\(\alpha=\sqrt{2\pi}\)

\(\{A_n\}\)をカタラン数列とするときの\(\dfrac{A_x}{4^xx^\frac{-3}{2}}\)の収束先

\(A_n=\dfrac{_{2n}C_n}{n+1}=\dfrac{1}{n+1}\dfrac{(2n)!}{n!n!}\sim\dfrac{\sqrt{2\pi2n}(2n)^{2n}e^{-2n}}{n(\sqrt{2\pi n}n^ne^{-n})^2}=\dfrac{4^n}{n\sqrt{\pi}n}=\dfrac{4^n}{\sqrt{\pi}n^\frac{3}{2}}\) よって、 \(\{A_n\}\)をカタラン数列とするときの\(\dfrac{A_n}{4^nn^\frac{-3}{2}}=\sqrt{\pi}\) となり、グラフは\(\sqrt{\pi}\)に収束することが確認できた。

このように、\(_{2n}C_n\)の関数から、カタラン数の関数を作り、グラフから数列\(\dfrac{A_n}{4^nn^\frac{-3}{2}}\)が収束することを推測し実際に\(\sqrt{\pi}\)に収束することが確認できた。