2018-01-31

スターリングの公式

定理解説

この記事ではStirlingの公式を次の形で証明します(Robbinsによる)。

Stirlingの公式 $n$ を正整数とするとき、

$\displaystyle n!=\sqrt{2\pi}n^{n+\frac{1}{2}}e^{-n}e^{r_n}$

が

$\displaystyle \frac{1}{12n+1} < r_n < \frac{1}{12n}$

を満たす形で成り立つ。

H. Robbins, A remark on Stirling's formula, Amer. Math. Monthly, Vol. 62, No. 1 (1955), 26-29.

証明. $S_n:=\log (n!) = \sum_{j=1}^{n-1}\log(j+1)$ とし、

$\displaystyle \log (j+1) = A_j+B_j-\varepsilon_j$

と分ける。ここで、

$\begin{align} A_j &:= \int_j^{j+1}\log xdx \\ B_j &:= \frac{1}{2}(\log(j+1)-\log j) \\ \varepsilon_j &:= \int_j^{j+1}\log xdx - \frac{1}{2}(\log(j+1)+\log j)= \frac{2j+1}{2}\log \frac{j+1}{j}-1\end{align}$

である。すると、

$\displaystyle S_n = \sum_{j=1}^{n-1}(A_j+B_j-\varepsilon_j) = \int_1^n\log x dx+\frac{1}{2}\log n-\sum_{j=1}^{n-1}\varepsilon_j = \left(n+\frac{1}{2}\right)\log n-n+1-\sum_{j=1}^{n-1}\varepsilon_j$

となる。対数関数のマクローリン展開によって

$\displaystyle \log \frac{1+x}{1-x} = 2\sum_{k=0}^{\infty}\frac{x^{2k+1}}{2k+1}, \quad \left|x\right| < 1$

なので、 $x=(2j+1)^{-1}$ とおくと $\frac{1+x}{1-x} = \frac{j+1}{j}$ であり、

$\displaystyle \varepsilon_j = \sum_{k=1}^{\infty}\frac{1}{(2k+1)(2j+1)^{2k}}$

である。よって、

$\displaystyle \varepsilon_j < \frac{1}{3(2j+1)^2}\sum_{k=0}^{\infty}\frac{1}{(2j+1)^{2k}} = \frac{1}{3(2j+1)^2}\cdot \frac{1}{1-(2j+1)^{-2}}=\frac{1}{12}\left(\frac{1}{j}-\frac{1}{j+1}\right)$

$\begin{align} \varepsilon_j &> \frac{1}{3(2j+1)^2}\left(1+\sum_{k=1}^{\infty}\frac{1}{(3(2j+1)^2)^k}\right) =\frac{1}{3(2j+1)^2}\cdot \frac{1}{1-(3(2j+1)^2)^{-1}} \\ &> \frac{1}{12}\left(\frac{1}{j+\frac{1}{12}}-\frac{1}{j+1+\frac{1}{12}}\right)\end{align}$

と望遠鏡和のパーツで押さえられる。故に、 $r_n:=\sum_{j=n}^{\infty}\varepsilon_j$ とすれば

$\displaystyle \frac{1}{12n+1} < r_n < \frac{1}{12n}$

かつ

$\displaystyle S_n=\left(n+\frac{1}{2}\right)\log n-n+1-r_1+r_n$

となって、 $C:=e^{1-r_1}$ とすれば

$\displaystyle n!=Cn^{n+\frac{1}{2}}e^{-n}e^{r_n}$

が示された。 $C$ の決定は

mathtrain.jp

を見よ。 Q.E.D.

2018-01-30

凸多角形を分割したときの小凸多角形の辺数の平均について

整数整数-6

問凸 $n$ 角形( $3 \leq n \leq 7$ )を二つ以上の凸多角形に分割するとき、各小多角形の辺の数の平均は $6$ より小さいことを示せ。

解答分割の個数を $k$ とし、分割によってできる平面グラフの頂点数を $v$ , 辺数を $e$ とする。このとき、面数は $k+1$ なので、Eulerの定理より

$v-e+(k+1)=2, \quad v=e-k+1$

が成り立つ。次数が $2$ であるような頂点の個数を $m$ とする( $m \leq n$ )。グラフの各頂点の次数の総和は $2e$ なので、

$2m+3(v-m) \leq 2e, \quad m \geq 3v-2e$

と評価できる。凸 $n$ 角形の外領域の境界上の辺の数を $l$ , 各小多角形の辺の数の平均を $a$ とすると、

$ka+l=2e$

であり、凸 $n$ 角形の外領域の境界上に次数が $3$ 以上の頂点が少なくとも二つはあるので、 $m \leq l-2$ である。以上より、

$2m \geq 6v-4e=6(e-k+1)-4e =ka+l-6k+6$

となって、

$k(a-6) \leq 2m-l-6 \leq m-8 \leq n-8$

が得られる。 $n \leq 7$ なので、 $a < 6$ でなければならない。 Q.E.D.

2018-01-24

Carlitzの恒等式

関−Bernoulli数

$B_n$ は関-Bernoulli数*1とする。このとき、次の恒等式が成り立つ：

$\displaystyle (-1)^m\sum_{k=0}^m\binom{m}{k}B_{n+k}=(-1)^n\sum_{k=0}^n\binom{n}{k}B_{m+k}.$

証明*2. 次のように母関数を計算する：

$\begin{align} \sum_{m, n=0}^{\infty}(-1)^m\sum_{k=0}^m\binom{m}{k}B_{n+k}\frac{x^my^n}{m!n!} &=\sum_{n=0}^{\infty}\frac{y^n}{n!}\sum_{k=0}^{\infty}\frac{B_{n+k}}{k!}\sum_{m=k}^{\infty}\frac{(-x)^m}{(m-k)!}\\ &=\sum_{n=0}^{\infty}\frac{y^n}{n!}\sum_{k=0}^{\infty}\frac{B_{n+k}}{k!}(-x)^ke^{-x} \\ &=e^{-x}\sum_{l=0}^{\infty}\frac{B_l}{l!}\sum_{k=0}^l\binom{l}{k}(-x)^ky^{l-k} \\ &=e^{-x}\sum_{l=0}^{\infty}\frac{B_l}{l!}(y-x)^l \\ &=e^{-x}\frac{y-x}{e^{y-x}-1}\\ &=\frac{y-x}{e^y-e^x} \end{align}$