二項係数にからんだ数列の極限を考えようとしたら闇が深かった話(後編)

ごめん、同級会には行けません。

いま、ロシアにいます。

というわけで、大学の研修でロシア第2の都市サンクトペテルブルクに来ています。いま起きたところなのですが、朝8時まで寝てようと思ったら朝5時に目が覚めてしまい、特にすることもないので、ブログ記事を書いている次第でございます。

さて、この記事は前回の続きになっておりますので、まだ前編を読んでない人は下のリンクから記事にとんでください。

halphy.hatenablog.com

念のため、忙しい人のために前回のあらすじをざっくり説明しますね。

次のような数列の$n\to\infty$でのふるまいを求めようとしていたのでした。

$$ a_n=\sum_{k=0}^n {}_n{\rm C}_k k^n $$

そして、OEIS(オンライン整数列大辞典)の記事に、このような記述を見つけ、なんとかしてこれを証明してやろうということになったのでした。

f:id:hal2000_phy:20190823233737p:plain

この式、何度見てもやばい香りがします。筑波山か富士山かでいったら富士山級です。 ちなみに、みなさんは日本で2番目に高い山を知っていますか? 僕は知ってます。北岳です。3番目は知りません。

もう一回さっきの式を書きますね。でーん。

$$ a_n=\sum_{k=0}^n {}_n{\rm C}_k k^n \sim \frac{1}{\sqrt{1+w}}\left(\frac{n}{ew}\right)^n $$

ここで$w$というのは$W(1/e)$のことで、$xe^x=1/e$を満たす実数$x$を意味します。値はおよそ$0.278$です。

さて、今からこれを証明していくわけですが、中高で合計6年間ぐらい数学を勉強してきたものの、「一般項がよくわからん数列の漸近挙動を調べる」方法を習ったことがありません。でも、だからといって簡単に諦めるのもなんだか悔しい。

こういうときは土台から固めていくのが大切です。もう一度、OEISの記事に戻ってみましょう。このページには、他にもたくさんのお役立ち情報が載っているはずです。その中で、使えそうなものを探せば、ゴールにたどりつけるはず。というわけで、記事をもう一度見直してみると……


f:id:hal2000_phy:20190823233748p:plain



まてよ……?


f:id:hal2000_phy:20190827100428p:plain



この式は何でしょう? 唐突に

$$ \frac{1}{1+W(-xe^x)} $$

という関数が書かれているのが不思議ですし、何よりランベルトのW関数が含まれています。この式が、いったい何を意味しているのか、気になります!

実は、E.g.fというのは exponential generating function の略で、日本語では指数型母関数といいます。指数型母関数について説明する前に、そもそも母関数(generating function)とは何かについて書いておきましょう。

数列$\{a_n\}$があったとき、その数列の各項を係数にもつべき級数

$$ f(x)=\sum_{n=0}^{\infty} a_nx^n $$

のことを、$\{a_n\}$の母関数といいます。母関数にはさまざまなタイプがあり、

$$ g(x)=\sum_{n=0}^{\infty} \frac{a_n}{n!}x^n $$

という形で定義することもあります。こちらのほうは指数型母関数と呼びます。これに対し、よりオーソドックスな$f(x)$のほうを通常型母関数といいます。単に「母関数」と言ったときには通常型母関数のほうを指すことが多いです。

数列の母関数が分かっていれば、母関数をべき級数に展開することで数列の各項がわかります。逆に、数列の各項が分かっていれば、そこから母関数を構成することができます。そのため、数列と母関数は1対1に対応します。

というわけで、母関数は、数列のふるまいを解析する上で、かなり役立ってくれそうです。そこで、件の数列

$$ a_n=\sum_{k=0}^n {}_n{\rm C}_k k^n $$

の指数型母関数が

$$ \frac{1}{1+W(-xe^x)} $$

であることを証明すること、これを当面の目標としましょう。指数型母関数というのは、数列の各項を$n!$で割ったものを係数にもつべき級数のことだったので、今から証明する式は

$$ \frac{1}{1+W(-xe^x)}=\sum_{n=0}^{\infty} \left(\sum_{k=0}^n {}_n{\rm C}_k k^n\right)\frac{x^n}{n!} $$

です。

指数型母関数を求める証明

証明は2ステップに分かれています。

  • Step 1 数列$n^n$の指数型母関数を求める。
  • Step 2 それを利用して、例の数列の指数型母関数を求める。

それではやっていきましょう。make it possible with †ランベルトのW関数†

Step 1

まずは、準備として

$$ \frac{1}{1+W(-x)}=\sum_{n=0}^{\infty}\frac{n^n}{n!}x^n $$

という等式を証明しましょう。この式は、$\displaystyle{\frac{1}{1+W(-x)}}$という関数のべき級数展開の係数が$\displaystyle{\frac{n^n}{n!}}$になることを意味しています。つまり、関数$\displaystyle{\frac{1}{1+W(-x)}}$は数列$n^n$の指数型母関数になっているというわけです。

ちなみに、この等式はランベルトのW関数に関する文献を漁っていたら偶然見つけました[1]。$n^n$という一見するとシンプルな数列の母関数が、$W(x)$という特殊関数を使わないと表せないというのはなんだか不思議な気がします。

証明をする前に、$\displaystyle{\frac{1}{1+W(-x)}}$のべき級数展開から本当に$n^n$が出てくるのか確かめておきましょう。今回もWolframAlphaにお世話になります。

検索バーにSeries[1/(1+ProductLog[-x]), {x,0,6}]と入力する*1と、関数$\displaystyle{\frac{1}{1+W(-x)}}$の$x=0$でのべき級数展開を、$x^6$の項まで表示してくれます。

f:id:hal2000_phy:20190827153847p:plain

もしこの関数を指数型母関数にもつ数列が$n^n$なのであれば、級数展開の各項の係数を$n!$倍したものは$n^n$になるはずです。確かめましょう。

$n$ $x^n$の係数 $n!$ $x^n$の係数$\times n!$ $n^n$
$0$ $1$ $1$ $1$ $1$
$1$ $1$ $1$ $1$ $1$
$2$ $2$ $2$ $4$ $4$
$3$ $\displaystyle{\frac{9}{2}}$ $6$ $27$ $27$
$4$ $\displaystyle{\frac{32}{3}}$ $24$ $256$ $256$
$5$ $\displaystyle{\frac{625}{24}}$ $120$ $3125$ $3125$
$6$ $\displaystyle{\frac{324}{5}}$ $720$ $46656$ $46656$

表のいちばん右の2列を見てください。完全に一致しています。どうやら本当に

$$ \frac{1}{1+W(-x)}=\sum_{n=0}^{\infty}\frac{n^n}{n!}x^n $$

が成り立っていそうです。安心できたところで証明にうつりましょう。

証明で大活躍するのが、次のLagrange Inversion Theorem(Wikipedia英語版)という定理です。これは逆関数のべき級数展開を求めるときに有用な公式なのですが、その主張をラフに書くと以下のようになります*2

Lagrange Inversion Theorem

関数$\varphi(y)$に対し、関係式$x=\displaystyle{\frac{y}{\varphi(y)}}$によって$x$から$y$への関数が定まるとする。このとき、

$$ \frac{1}{1-x\varphi'(y)}=\sum_{n=0}^{\infty}\frac{x^n}{n!}\left.\frac{d^n}{dy^n}(\varphi(y))^n\right|_{y=0} $$

が成り立つ。

ここで注意ですが、定理の主張はやや大雑把に書いており、細かい前提条件は省略しています。気になる人は専門の書物を読んでください。

定理の証明は文献[4]などを見ていただくとして、さっそくこの定理を利用してみましょう。そのためには、関数$\varphi(y)$の形を適切に決める必要がありますが、実は$\varphi(y)=e^y$とおくとうまくいきます。実際、$\varphi(y)=e^y$ならば$x$と$y$の関係は

$$ x=\frac{y}{e^y}=ye^{-y} $$

すなわち

$$ y=-W(-x) $$

です。一方、定理の式の左辺において$\varphi'(y)=(e^y)'=e^y$ですから

$$ \frac{1}{1-x\varphi'(y)}=\frac{1}{1-xe^y}=\frac{1}{1-y}=\frac{1}{1+W(-x)} $$

となり、うまく証明したい式の形を作ることができました。あとは、定理1の右辺である

$$ \sum_{n=0}^{\infty}\frac{x^n}{n!}\left.\frac{d^n}{dy^n}(\varphi(y))^n\right|_{y=0} $$

を計算してやるだけです。ここで問題なのは

$$ \left.\frac{d^n}{dy^n}(\varphi(y))^n\right|_{y=0}=\left.\frac{d^n}{dy^n}(e^y)^n\right|_{y=0}=\left.\frac{d^n}{dy^n}e^{ny}\right|_{y=0} $$

の部分ですが、これは「関数$e^{ny}$の$y=0$での$n$階微分係数」という意味なので、関数$e^{ny}$を繰り返し微分してそこに$y=0$を代入すればよいですね。計算してみると分かりますがその値は$n^n$になります。というわけで、証明したかった式である

$$ \frac{1}{1+W(-x)}=\sum_{n=0}^{\infty}\frac{n^n}{n!}x^n $$

が導出できました。やったぜ。

というわけで、Step 1の定理はLagrange Inversion Theoremという強力な定理を利用することで証明できました。ちなみに、この定理は複素解析*3の手法を用いた証明が知られているそうです。

Step 2

次はStep 2です。Step 2は証明がやや長い上にそこそこ複雑なので、結果だけ見たい人は次にとんでください。

さて、ここでは、先ほど証明した

$$ \frac{1}{1+W(-x)}=\sum_{n=0}^{\infty}\frac{n^n}{n!}x^n $$

から

$$ \frac{1}{1+W(-xe^x)}=\sum_{n=0}^{\infty} \left(\sum_{k=0}^n {}_n{\rm C}_k k^n\right)\frac{x^n}{n!} $$

を導きます。2つの式をじっと見比べると、1つ目の式において$x\to xe^x$という置き換えを行なうと2つ目の式になることに気づきます*4。ということは、1つ目の式の$x$を$xe^x$に置き換えた式を考えればよさそうです。やってみましょう。

$$ \frac{1}{1+W(-xe^x)}=\sum_{n=0}^{\infty}\frac{n^n}{n!}(xe^x)^n $$

ここで行き詰まりそうになりますが、$xe^x$という関数もべき級数で書くことができるので、それを利用しましょう。$e^x$のべき級数展開を覚えている人は多いと思うので*5、それを$x$倍するだけです。

$$ xe^x=x\sum_{n=0}^{\infty} \frac{x^n}{n!}=\sum_{n=1}^{\infty} \frac{x^n}{(n-1)!}=\sum_{n=1}^{\infty} \frac{n}{n!}x^n $$

これを先ほどの式に代入します。どーん。

$$ \frac{1}{1+W(-xe^x)}=\sum_{n=0}^{\infty}\frac{n^n}{n!}\left(\sum_{m=1}^{\infty} \frac{m}{m!}x^m\right)^n $$

いきなりmという文字が登場しても戸惑わないでくださいね。シグマ記号で使うダミー変数は何でもいいのですが、内側のシグマ記号で$n$を使ってしまうと外側のシグマ記号のダミー変数$n$と被ってしまうので仕方なくmにしただけです。

さてこの式。無限和の中に無限和があって、見た目の醸し出すオーラが半端じゃない。どうにかしてこれを簡単にしたいです。 問題なのは$\displaystyle{\left(\sum_{m=1}^{\infty} \frac{m}{m!}x^m\right)^n}$の部分です。よく見ると、無限個の項の和の$n$乗になっていて、これを展開するのは少し厄介な気がします。

とはいえ、ゆっくり考えればそれほど怖くはありません。いま知りたいのは、関数$\displaystyle{\frac{1}{1+W(-xe^x)}}$のべき級数展開の各項の係数です。では、例えば$x^N$の係数を知りたいときどうすればよいでしょう?

答えは単純です。二重シグマの式を展開した結果が$x^N$になるような項を、ひとつ残らず拾い集めればよいのです。

ここから先の話はいささか抽象的なので、その前に具体的な値で感覚をつかみましょう。例えば$N=2$としてみましょう。関数$\displaystyle{\frac{1}{1+W(-xe^x)}}$のべき級数展開の$x^2$の項の係数はいくつになるでしょうか。式を展開した結果が$x^2$になるような項をすべてかき集めてみましょう。

まず、外側のシグマ記号を考えます。$n=0,1,2,\cdots$のそれぞれに対して、$x^2$の項がどこに現れるかを探してみましょう。

$n=0$のとき、シグマの中身は$1$ですから、これが$x^2$の項を生み出すことはありません。

次に$n=1$のとき、シグマの中身は

$$ \left(\sum_{m=1}^{\infty} \frac{m}{m!}x^m\right) $$

になりますから、$x^2$の項は、このうち$m=2$に対応する項に現れます。つまり、$n=1$のときの和から

$$ \frac{2}{2!}x^2=x^2 $$

という項が現れることが分かります。

さらに$n=2$のときを調べましょう。シグマの中身は

$$ \frac{2^2}{2!}\left(\sum_{m=1}^{\infty} \frac{m}{m!}x^m\right)^2=2\left(\sum_{m=1}^{\infty} \frac{m}{m!}x^m\right)\left(\sum_{m=1}^{\infty} \frac{m}{m!}x^m\right) $$

という2つの無限和の掛け算になっています。よって、ここから$x^2$の項が出てくるのは、

  • 1番目の和で1次の項を選び、2番目の和で1次の項を選んだとき

です。したがって、$n=2$のときの和からは

$$ 2\cdot \frac{1}{1!}x\cdot \frac{1}{1!}x=2x^2 $$

という項が現れることが分かります。

最後に$n=3$以降ですが、最低でも次数が$3$の項しか現れないので、ここから$x^2$の項が出てくることはありません。

というわけで、$x^2$の項は

$$ x^2+2x^2=3x^2 $$

になることが分かりました。

具体的な例で仕組みが分かったところで、今までの話を一般化しましょう。$x^N$の係数を求めるために、$n=1,2,\cdots, k,\cdots, N$のそれぞれについて、$x^N$が現れる項を探します。

一般に、$n=k$のときを考えましょう。シグマ記号の中身は

$$ \frac{k^k}{k!}\left(\sum_{m=1}^{\infty} \frac{m}{m!}x^m\right)^k $$

ですから、あとは$\displaystyle{\left(\sum_{m=1}^{\infty} \frac{m}{m!}x^m\right)^k}$を展開したときに、$x^N$が現れるような項の選び方を考えます。

さて、$\displaystyle{\left(\sum_{m=1}^{\infty} \frac{m}{m!}x^m\right)^k}$というのは

$$ \left(\sum_{m=1}^{\infty} \frac{m}{m!}x^m\right)\cdot \left(\sum_{m=1}^{\infty} \frac{m}{m!}x^m\right)\cdots \left(\sum_{m=1}^{\infty} \frac{m}{m!}x^m\right) $$

という$k$個の無限次多項式の積です。それぞれの因数からどの項を選べばよいか考えましょう。掛け算は順序によらないので、何次の項を何個選んでくるかのみが重要です。そこで、$x$の項を$p_1$個、$x^2$の項を$p_2$個、…、$x^{N-k+1}$の項を$p_{N-k+1}$個選んだとします*6。項は合計$k$個あるので、もちろん

$$ p_1+p_2+\cdots+p_{N-k+1}=k \tag{*} $$

です。これを満たすように$p_1, p_2,\cdots,p_{N-k+1}$を選んだとき、掛け算した結果ちょうど次数が$N$になる($x^N$の項になる)ためには、さらに

$$ p_1+2p_2+\cdots+(N-k+1)p_{N-k+1}=N \tag{**} $$

が成り立っている必要があります。

逆に言えば、(*)かつ(**)を満たすような負でない整数$p_1, p_2,\cdots,p_{N-k+1}$の組ならば、どんなものを選んできてもよいということです。

さらに、$p_1, p_2,\cdots,p_{N-k+1}$の組それぞれに対して、どの因子からどの次数の項をとってくるかで

$$ \frac{k!}{p_1!p_2!\cdots p_{N-k+1}!} $$

通りの場合があります。いきなりごつい式が登場して面食らうかもしれませんが、これは高校数学でおなじみの「同じものを含む順列」というやつです。$p_1$個の項、$p_2$個の項、…、$p_{N-k+1}$個の項の合計$p_1+p_2+\cdots+p_{N-k+1}=k$個を並べる順列の総数を求めるには、$k$個の項の順列を$p_1!p_2!\cdots p_{N-k+1}!$で割って同一視してやる必要がありますからね。

というわけで、$n=k$のときに現れる$x^N$の項の合計は

$$ \frac{k^k}{k!}\sum\frac{k!}{p_1!p_2!\cdots p_{N-k+1}!}\left(\frac{1\cdot x}{1!}\right)^{p_1}\left(\frac{2\cdot x^2}{2!}\right)^{p_2}\cdots \left(\frac{(N-k+1)x^{N-k+1}}{(N-k+1)!}\right)^{p_{N-k+1}} $$

と表すことができます。ここでシグマ記号に何も書かれていませんが、この式においては$p_1+p_2+\cdots+p_{N-k+1}=k$かつ$p_1+2p_2+\cdots+(N-k+1)p_{N-k+1}=N$を満たす非負整数$p_1, p_2,\cdots,p_{N-k+1}$すべてにわたる和を考えることと約束します。

あとは、$n=1,2,\cdots, k,\cdots, N$について、$x^N$が現れる項をすべて足してやれば、それが求めたかった$x^N$の項の合計になっています*7

$$ \sum_{k=0}^N\frac{k^k}{k!}\sum\frac{k!}{p_1!p_2!\cdots p_{N-k+1}!}\left(\frac{1\cdot x}{1!}\right)^{p_1}\left(\frac{2\cdot x^2}{2!}\right)^{p_2}\cdots \left(\frac{(N-k+1)x^{N-k+1}}{(N-k+1)!}\right)^{p_{N-k+1}} $$

見るからに複雑な式ができてしまい自分でもびっくりしています。あとはこれを頑張って変形していくのでしばしお付き合いください。見てるだけで疲れそうですね。

まずは$x$のべき乗を指数法則を使ってまとめていきます。また同時に、分子と分母に$k!$がいるので並行して約分してやります。

$$ \begin{eqnarray} &&\sum_{k=0}^N\frac{k^k}{k!}\sum\frac{k!}{p_1!p_2!\cdots p_{N-k+1}!}\left(\frac{1\cdot x}{1!}\right)^{p_1}\left(\frac{2\cdot x^2}{2!}\right)^{p_2}\cdots \left(\frac{(N-k+1)x^{N-k+1}}{(N-k+1)!}\right)^{p_{n-k+1}}\\ &=&\sum_{k=0}^Nk^k\sum\frac{1}{p_1!p_2!\cdots p_{N-k+1}!}\left(\frac{1}{1!}\right)^{p_1}\left(\frac{2}{2!}\right)^{p_2}\cdots \left(\frac{(N-k+1)}{(N-k+1)!}\right)^{p_{N-k+1}}x^{p_1+2p_2+\cdots+(N-k+1)p_{N-k+1}}\\ &=&\sum_{k=0}^Nk^k\sum\frac{1}{p_1!p_2!\cdots p_{N-k+1}!}\left(\frac{1}{1!}\right)^{p_1}\left(\frac{2}{2!}\right)^{p_2}\cdots \left(\frac{(N-k+1)}{(N-k+1)!}\right)^{p_{N-k+1}}x^N \end{eqnarray} $$

これ以上簡単にならなそうですが、実は、次のような等式を用いると、この式を格段にきれいにすることができます。

ベル多項式の特殊値

$p_1, p_2,\cdots,p_{N-k+1}$を$p_1+p_2+\cdots+p_{N-k+1}=k$かつ$p_1+2p_2+\cdots+(N-k+1)p_{N-k+1}=N$を満たす非負整数であるとするとき

$$ \sum\frac{N!}{p_1!p_2!\cdots p_{N-k+1}!}\left(\frac{1}{1!}\right)^{p_1}\left(\frac{2}{2!}\right)^{p_2}\cdots \left(\frac{(N-k+1)}{(N-k+1)!}\right)^{p_{N-k+1}}={}_N{\rm C}_k k^{N-k} $$

が成り立つ。

いきなり公式が天から降ってきた感じは否めませんがご容赦ください。この等式の証明の詳細は文献[5], [6]を見てもらうとして、ここでは証明の概略だけ紹介します。証明のステップは次の通りです。

  1. 数列$\displaystyle{\sum_{k=0}^n{}_n{\rm C}_k k^{n-k}}$の指数型母関数が$\exp{(x\exp{x})}$であることを証明する*8
  2. 関数$\exp{(x\exp{x})}$のべき級数展開の各項に$\displaystyle{\sum_{k=0}^n\sum\frac{1}{p_1!p_2!\cdots p_{n-k+1}!}\left(\frac{1}{1!}\right)^{p_1}\left(\frac{2}{2!}\right)^{p_2}\cdots \left(\frac{(n-k+1)}{(n-k+1)!}\right)^{p_{n-k+1}}}$が現れることを証明する。

特に2.については、上の証明と全く同じ流れをたどるため、比較的理解しやすいでしょう。

この定理が成り立つことは認めれば、あとはもうゴールに向かって突き進むだけです。

$$ \begin{eqnarray} &&\sum_{k=0}^Nk^k\sum\frac{1}{p_1!p_2!\cdots p_{N-k+1}!}\left(\frac{1}{1!}\right)^{p_1}\left(\frac{2}{2!}\right)^{p_2}\cdots \left(\frac{(N-k+1)}{(N-k+1)!}\right)^{p_{N-k+1}}x^N\\ &=&\sum_{k=0}^N\frac{k^k}{N!}\sum\frac{N!}{p_1!p_2!\cdots p_{N-k+1}!}\left(\frac{1}{1!}\right)^{p_1}\left(\frac{2}{2!}\right)^{p_2}\cdots \left(\frac{(N-k+1)}{(N-k+1)!}\right)^{p_{N-k+1}}x^N\\ &=&\sum_{k=0}^N\frac{k^k}{N!}{}_N{\rm C}_k k^{N-k}\\ &=&\sum_{k=0}^N\frac{k^N}{N!}{}_N{\rm C}_k \end{eqnarray} $$

こんなにすっきりした式になりました。$\displaystyle{\sum_{k=0}^N\frac{k^N}{N!}{}_N{\rm C}_k}$というのはそもそも、関数$\displaystyle{\frac{1}{1+W(-xe^x)}}$のべき級数展開の$x^N$の係数を表していましたから、結局

$$ \frac{1}{1+W(-xe^x)}=\sum_{n=0}^{\infty} \left(\sum_{k=0}^n {}_n{\rm C}_k k^n\right)\frac{x^n}{n!} $$

が証明できたことになります。すなわち、例の数列$\displaystyle{\sum_{k=0}^n {}_n{\rm C}_k k^n}$の指数型母関数が$\displaystyle{\frac{1}{1+W(-xe^x)}}$という関数であることが分かりました。

結果を噛みしめる

ふー。さすがに疲れましたね。とはいえ、いま証明した内容を見直してみると、なかなか興味深いことを言っていることが分かります。数列の一般項は和の形でしか表せないのに、その母関数の形はきっちり分かってしまうんです。結構すごくないですか。

さて、せっかく指数型母関数が$\displaystyle{\frac{1}{1+W(-xe^x)}}$であることが分かったので、実際に$\displaystyle{\frac{1}{1+W(-xe^x)}}$の級数展開を求めることで例の数列の各項を求めてみましょう。今回使用するのはやっぱりWolframAlphaくんです。なんだかWolfram Research社の回し者みたいになってきました。スポンサーについてくれないかなあ()

検索窓にSeries[1/(1+ProductLog[-xe^x]), {x,0,6}]と入力して、数列の第$6$項までを求めてやりましょう。

f:id:hal2000_phy:20190828101448p:plain

級数展開の各項の係数を$n!$倍すれば、それが$\displaystyle{\sum_{k=0}^n {}_n{\rm C}_k k^n}$になっているはずです。はたしてそうなっているでしょうか。

$n$ $x^n$の係数 $n!$ $x^n$の係数$\times n!$
$0$ $1$ $1$ $1$
$1$ $1$ $1$ $1$
$2$ $3$ $2$ $6$
$3$ $9$ $6$ $54$
$4$ $\displaystyle{\frac{85}{3}}$ $24$ $680$
$5$ $\displaystyle{\frac{275}{3}}$ $120$ $11000$
$6$ $\displaystyle{\frac{4529}{15}}$ $720$ $217392$

$1,1,6,54,680,11000,217392,\cdots$これは紛れもなくあの数列です。達成感ありますね。

母関数がわかれば漸近挙動がわかる

いやちょっと待って。なんか終わった気になっていませんか? 母関数を求めただけで満足しちゃってますよね? まだ大事な仕事が残っています。そう、「例の数列の漸近挙動を求める」ためにこの記事を書いているんでした。

実は、例の数列の母関数を求めたことは、数列の漸近挙動を求めるための大事な準備になっているのです。なぜなら、「母関数が分かっていれば、それを利用して数列の漸近挙動を求めることができる」からです。

もう一度言いますよ。

「母関数が分かっていれば、それを利用して数列の漸近挙動を求めることができる」んです。

信じられない? ほんとです。Wikipediaもそう言っています()

f:id:hal2000_phy:20190828112142p:plain

ちょっとできそうな気がしてきましたね。

でも、どうやって?

この記述を見つけてからというもの、その方法を探し求めてネットの海を彷徨いましたが、一向に見つかりません。情報が結構ありそうなトピックなのに、探してみると意外にないものです。

ようやく文献を見つけたときには、探し始めてから2日が経っていました。

"Analytic Combinatorics"とかいう本が神

その文献というのがこちらです。

Analytic Combinatorics

Analytic Combinatorics

"Analytic Combinatorics"(直訳すると「解析的組合せ論」)は、解析学微分積分学)の手法を用いて組合せ論の問題を解く方法について解説した824ページにわたる大著です。しかもなんとこの本、著者の方がWebページに全文を公開してくれています。なんて優しいんだ。というか採算とれてるのかな。

とにかく目次を見ると、「Part B: Complex Asymtotics」という部分に、数列の漸近挙動を解析する話が述べられているようなのですが、なんとその説明に400ページ弱も費やされています。きっとそこに知りたい情報があるはず。さっそく読んでみました(流し読みですが)。

この本の言いたいことを要約すると

  • 数列の漸近挙動は、母関数の特異点まわりのふるまいによって決まる

ということです。標語的に言っただけではよく分からないでしょうから、もう少し詳しく説明します。

いま、数列$\{f_n\}$の漸近挙動を知りたいとします。数列$\{f_n\}$の母関数$f(x)$をがんばって発見したとしましょう。この関数$f(x)$は$x=a$という点を(発散するなどして)特異点に持つとします。このとき、$x$を$a$に近づけたときの発散(or収束)の仕方、すなわち$x\to a$での漸近挙動が$f(x)$と同じであるような標準的な関数$g(x)$が存在して、しかも$g(x)$を母関数にもつ数列$\{g_n\}$の漸近挙動が既知ならば、もとの数列$\{f_n\}$の漸近挙動を知ることができます。なぜなら、数列$\{f_n\}$の漸近挙動は数列$\{g_n\}$の漸近挙動と実は同じになるからです。

これを今回の話に当てはめると、つまりこういうことです。いま、

$$ f_n=\sum_{k=0}^n {}_n{\rm C}_k k^n $$

という数列の漸近挙動を求めようとしています。僕たちは、この数列$\{f_n\}$の(指数型)母関数$f(x)$が

$$ f(x)=\frac{1}{1+W(-xe^x)} $$

であることを知っています。この関数は、分母が$0$になるときがあるため特異点を持ちます。そのときの$x$の値を求めておきましょう。$1+W(-xe^x)=0$となるような$x$は

$$ -xe^x=-\frac{1}{e} $$

すなわち

$$ x=W\left(\frac{1}{e}\right)(=w) $$

です。さて、いまからやることは、$x\to w$での漸近挙動が$f(x)$と同じになるような$g(x)$をなんとかして発見することです。式で書けば

$$ f(x)\sim g(x) \; (x\to w) $$

となります。記号「$\sim$」は数列の$n\to \infty$の極限を考えるときにしか定義していませんでしたが、それを拡張して、関数については

$$ \lim_{x\to w}\frac{f(x)}{g(x)}=1 $$

が成り立つとき$f(x)\sim g(x) \; (x\to w)$と表す、と約束します。

ところで、$g(x)$は何でもいいわけではありません。$g(x)$は、これを母関数にもつ数列の漸近挙動が既知であるような、そういう標準的な関数である必要があります。もし運良くそのような$g(x)$を発見できれば、$g(x)$を母関数にもつ数列の漸近挙動を求めることで、もとの数列$\{f_n\}$の漸近挙動を知ることができるというわけです。めでたしめでたし。

まずは練習

いま説明したことをいきなり$\displaystyle{\frac{1}{1+W(-xe^x)}}$でやるのは荷が重いので、その前にもっと簡単な例で感覚をつかみましょう。まずは$f_n=n^n$を例にとり、

$$ f(x)=\frac{1}{1+W(-x)} $$

を調べてみます。この関数は、分母が$0$になる点をもちます。そのような点の$x$座標を求めるには、$1+W(-x)=0$を解けばよいので、最終的に

$$ x=\frac{1}{e} $$

を得ます。すなわち、この関数は$x=1/e$を特異点にもつことが分かりました。そこで、

$$ \frac{1}{1+W(-x)}\sim g(x) \; \left(x\to \frac{1}{e}\right) $$

となるような標準的な関数$g(x)$を探しましょう。ここからの計算は、大部分を"Analytic Combinatorics"のp.403(Example VI.8)に依拠しています。適宜参考にしてください。

さて、まず$y=-W(-x)$とおきます。すると、$x$と$y$の関係は

$$ x=ye^{-y} $$

と表すことができます。ここで、両辺を$y$の関数とみなして$y=1$($x=1/e$)のまわりでテイラー展開します。暗算でもできますが面倒くさいのでWolframAlphaにSeries[ye^(-y), {y, 1, 2}]と入力しましょう。

f:id:hal2000_phy:20190828130153p:plain

はい。2次の項で打ち切ると

$$ x=\frac{1}{e}-\frac{1}{2e}(y-1)^2+O( (y-1)^3) $$

となります($O( (y-1)^3)$は誤差項を表します)。これを$y$についての2次方程式とみなし、解の公式を使って$y$について解いてみましょう。ただし、関数$ye^{-y}$の定義域が$y\leq 1$であることに注意してマイナスの符号を採用することに注意しましょう。結果はこうなります。

$$ y=1-\sqrt{2}\sqrt{1-ex}+O(1-ex) $$

ところで$y=-W(-x)$だったので

$$ 1+W(-x)=\sqrt{2}\sqrt{1-ex}+O(1-ex) $$

が成り立ちます。これは

$$ 1+W(-x)\sim\sqrt{2}\sqrt{1-ex} \; \left(x\to \frac{1}{e}\right) $$

を意味していますから、両辺の逆数をとれば

$$ \frac{1}{1+W(-x)}\sim\frac{1}{\sqrt{2}\sqrt{1-ex}} \; \left(x\to \frac{1}{e}\right) $$

がいえたことになります。というわけで、探していた関数

$$ g(x)=\frac{1}{\sqrt{2}\sqrt{1-ex}} $$

が見つかりました。あとは、$g(x)$を母関数にもつ数列の一般項を求めるだけです。

このまま計算してもいいのですが、いろいろ定数が入っていてごちゃごちゃしているので、まずは

$$ G(x)=\frac{1}{\sqrt{1-x}} $$

という、より標準的な関数を考えて、その結果を利用することにしましょう。そのほうが応用がききます。

$G(x)$を母関数にもつ数列を求めるためには、$G(x)$のべき級数展開を求める必要があります。そのために、$G(x)$の$n$階微分を計算しましょう。

$$ \begin{eqnarray} G(x)&=&(1-x)^{-\frac{1}{2}}\\ G'(x)&=&\frac{1}{2}(1-x)^{-\frac{3}{2}}\\ G''(x)&=&\frac{1}{2}\frac{3}{2}(1-x)^{-\frac{5}{2}}\\ G^{(n)}(x)&=&\frac{1}{2}\frac{3}{2}\cdots\frac{2n-1}{2}(1-x)^{-\frac{2n+1}{2}}\\ \end{eqnarray} $$

この計算から、$G(x)$の$x=0$での$n$階微分係数

$$ G^{(n)}(0)=\frac{1}{2}\cdot\frac{3}{2}\cdots\left(n-\frac{1}{2}\right) $$

になることが分かりました。よって、$G(x)$のべき級数展開の$x^n$の項の係数$G_n$は

$$ G_n=\frac{1}{n!}\cdot\frac{1}{2}\cdot\frac{3}{2}\cdots\left(n-\frac{1}{2}\right) $$

になります。この式は、一般化二項係数*9を用いると

$$ G_n=\binom{n-1/2}{n} $$

と表すことができます。あとは、この数列の漸近挙動を求めるだけですが、実は

$$ \binom{n-1/2}{n}\sim \frac{1}{\sqrt{n}\Gamma(1/2)}=\frac{1}{\sqrt{\pi n}} \; (n\to\infty) $$

であることが知られています*10。ただし$\Gamma(x)$はかの有名なガンマ関数です。

したがって、

$$ G(x)=\frac{1}{\sqrt{1-x}} $$

という関数を母関数にもつ数列$G_n$の漸近挙動が

$$ G_n \sim \frac{1}{\sqrt{\pi n}} \; (n\to\infty) $$

であることが分かりました。さて、そもそもどうしてこんなことをしていたかというと

$$ g(x)=\frac{1}{\sqrt{2}\sqrt{1-ex}} $$

を母関数にもつ数列$g_n$の漸近挙動を知りたかったのでした。いま計算した結果をさっそく利用しましょう。母関数の定義より

$$ G(x)=\sum_{n=0}^{\infty} G_nx^n $$

ですが、ここで$x\to ex$という置き換えを行い、両辺を$1/\sqrt{2}$倍すれば、左辺は$g(x)$になって

$$ g(x)=\frac{1}{\sqrt{2}\sqrt{1-ex}}=\sum_{n=0}^{\infty} e^nG_nx^n $$

が成り立ちます。すなわち、$g(x)$を母関数にもつ数列$g_n$と、$G_n$の関係は

$$ g_n=e^nG_n $$

です。したがって、$g_n$の漸近挙動が

$$ g_n \sim \frac{e^n}{\sqrt{2\pi n}} \; (n\to\infty) $$

になることが分かりました。そもそも$n!g_n$は、数列$n^n$と同じように漸近する数列だった*11のですから、最終的に

$$ n^n \sim \frac{n! e^n}{\sqrt{2\pi n}} \; (n\to\infty) $$

がいえたことになります。

ここでやったことを簡単にまとめておきましょう。

  1. 数列$f_n=n^n$の漸近挙動を調べるため、$f_n$の指数型母関数が$f(x)=\displaystyle{\frac{1}{1+W(-x)}}$であることを求めた。
  2. $f(x)$は$x=1/e$に特異点をもつため、$x\to 1/e$での漸近挙動が一致する標準的な関数$g(x)$を探した。その結果、$g(x)=\displaystyle{\frac{1}{\sqrt{2}\sqrt{1-ex}}}$を発見した。
  3. $g(x)$を通常型母関数にもつ数列$g_n$の漸近挙動が$\displaystyle{g_n \sim \frac{e^n}{\sqrt{2\pi n}}}$であることを求めた。
  4. $f_n$の漸近挙動と$n!g_n$の漸近挙動は一致するので、$f_n$の漸近挙動が$\displaystyle{f_n \sim \frac{n! e^n}{\sqrt{2\pi n}}}$であることがわかった。

数列の世界で「$n\to\infty$での漸近挙動が同じ」ものどうしが、母関数の世界では「特異点まわりでの漸近挙動が同じ」ものどうしである、というシンプルな対応がとてもきれいです。せっかくですから、頭を整理するためにもここで用いた事実を定理としてまとめておきましょう。

すごい定理

関数$f(x)$およびある実数$x_0$に対して

$$ f(x)\sim \frac{C}{\displaystyle{\sqrt{1-\frac{x}{x_0}}}}\; (x\to x_0) $$

が成り立つならば、$f(x)$を母関数にもつ数列$f_n$は

$$ f_n\sim \frac{C}{x_0^n\sqrt{\pi n}}\; (n\to\infty) $$

を満たす。ただし$C$は定数である。

この定理において$x_0=1/e, C=1/\sqrt{2}$としてみると、ちょうど今までやってきたことに対応します。

ところで、ついさっき求めた

$$ n^n \sim \frac{n! e^n}{\sqrt{2\pi n}} \; (n\to\infty) $$

スターリングの公式(Stirling's formula)と呼ばれる有名な式です。この式は、おもに階乗$n!$の$n\to\infty$での漸近挙動を求めるために使われ、これを変形した

$$ n! \sim\sqrt{2\pi n}\left(\frac{n}{e}\right)^n \; (n\to\infty) $$

という形でお目にかかることが多いです。

ラストスパート

数列$n^n$で感覚をつかんだところで、最終目標である

$$ \sum_{k=0}^n {}_n{\rm C}_k k^n $$

の漸近挙動を求める準備が整いました。いよいよ本番ですよ!

むっちゃドキドキしてきた…。

皆さん、今日くらいは休んで明日に備えますよね?



……………。




いやファボゼロのボケすんな!

はい。というわけで始めていきましょう。出発点となるのは、この数列の指数型母関数である

$$ \frac{1}{1+W(-xe^x)} $$

です。この関数は$x=W(1/e)=w$に特異点をもつので、$x\to w$での漸近挙動が同じ関数を発見してやりましょう。

そのときに活躍するのが、さっき求めた

$$ \frac{1}{1+W(-y)}\sim\frac{1}{\sqrt{2}\sqrt{1-ey}} \; \left(y\to \frac{1}{e}\right) $$

という式*12。2つの式を比較すると、これに$y=xe^x$を代入すればいいことがありそうです。

$$ \frac{1}{1+W(-xe^x)}\sim\frac{1}{\sqrt{2}\sqrt{1-xe^{x+1}}} \; \left(x\to w\right) $$

はい、こんな感じです($x\to w$のとき$y=xe^x \to 1/e$になるので、きちんと辻褄が合っています*13)。

というわけで、$x\to w$での漸近挙動が同じになる

$$ \frac{1}{\sqrt{2}\sqrt{1-xe^{x+1}}} $$

という関数を発見しました。とはいえ、このままでは関数の形が複雑で都合が悪いので、さらに変形をしていきましょう。ルートの中身である$1-xe^{x+1}$を$x=w$のまわりで$1$次の項までテイラー展開してやります。結果はこちら。

$$ 1-xe^{x+1}=(1+e^{1+w})(w-x)+O( (x-w)^2 ) $$

WolframAlphaにSeries[1-xe^(x+1), {x, ProductLog[1/e], 1}]と入力すれば一瞬で出ますが、頼りすぎはいけません。普通に$1-xe^{x+1}$を1回微分して$x=w$を代入すれば$1+e^{1+w}$という値が出てきます。ちなみに僕は怠惰なのでWolframAlphaを使いました。

さて、この結果を用いれば

$$ \frac{1}{1+W(-xe^x)}\sim\frac{1}{\sqrt{2}\sqrt{1-xe^{x+1}}}\sim\frac{1}{\sqrt{2(1+e^{1+w})}\sqrt{w-x}} \; \left(x\to w\right) $$

が分かります。こうして、$x\to w$での漸近挙動が同じになる「単純」な関数

$$ \frac{1}{\sqrt{2(1+e^{1+w})}\sqrt{w-x}} $$

が見つかりました! この関数は、形としては$\displaystyle{\frac{1}{\sqrt{1-x}}}$型に分類されるので、さっきの定理の結果を利用することができます。これはもう勝ちましたね。

定理の形に当てはめるために

$$ \frac{1}{\sqrt{2(1+e^{1+w})}\sqrt{w-x}}=\frac{1}{\sqrt{2w(1+e^{1+w})}\displaystyle{\sqrt{1-\frac{x}{w}}}}=\frac{1}{\sqrt{2(1+w)}\displaystyle{\sqrt{1-\frac{x}{w}}}} $$

と変形します。最後の等式では、$we^w=1/e$であることを利用して

$$ w(1+e^{1+w})=w+we^{1+w}=w+we^w\cdot e=w+\frac{1}{e}\cdot e=1+w $$

という変形を行いました。あとは

$$ x_0=w, C=\frac{1}{\sqrt{2(1+w)}} $$

として定理を適用するだけです。$\displaystyle{\frac{1}{1+W(-xe^x)}}$が「指数型」母関数であることに注意して$n!$を忘れなければ

$$ \sum_{k=0}^n {}_n{\rm C}_k k^n\sim \frac{n!}{w^n \sqrt{2\pi n(1+w)}} \; (n\to\infty) $$

という式を得ます。

あとはもうひと踏ん張りです。さっき導出したスターリングの公式

$$ n! \sim\sqrt{2\pi n}\left(\frac{n}{e}\right)^n \; (n\to\infty) $$

を用いて$n!$を消去します。すると……?

$$ \sum_{k=0}^n {}_n{\rm C}_k k^n \sim \frac{1}{\sqrt{1+w}}\left(\frac{n}{ew}\right)^n \; (n\to\infty) $$

お!

おおおお!!!!!!

おおおおおおおおお!!!!

おおおおおおおおおおおおおおおおおううううううううぅぅぅぅぅぅぅsdくfgdしfじゃwfゔぇいうwfhwfhwfうあえsgつwdgづy!!!!!!!!!(語彙力)

できた! できました! 「二項係数を含む和で表された数列」という単純なつくりのものから、ランベルトのW関数が現れるのを見届け、そして漸近挙動を解き明かしていく過程を、(端折ったところはあるものの)すべて追うことができました……!

おわりに

というわけで、とある数列を題材に、さまざまな手法を用いてその性質を探る旅のもようをお送りしてきましたが、皆さんいかがでしたか。数列の母関数、漸近挙動、それを解析的な手法を用いて調べる方法。これらはおそらく、中学、高校、大学初年度で学ぶ数学にはあまり登場しない話題でしょう。高校数学の花形は微分積分でしょうし*14、今回紹介した組合せ論という分野はどちらかといえばマイナーな部類に入ると思います。だからこそ、今回はそういうニッチな分野の数学に触れることができてとても新鮮でした。一見単純で研究し尽くされたようなトピックであっても、ちょっと脇道に入ると、そこには豊かな数学の謎が広がっているんだなあ、ということを感じました。

また、今回紹介した証明は、完全に自力で到達したわけでは決してありません。インターネット上に転がっているたくさんの資料や、WolframAlphaやDesmosなどのWebアプリケーションの力を借りて始めてできたことです。いわば、巨人の肩から肩へとぴょんぴょん飛び移りまくったわけですが、それだけでもめちゃくちゃ達成感があります。地道に文献を探すのは骨が折れますが、様々な論文や書籍の記述をもとに証明の道筋を完成させたときの喜びはひとしおです。

この記事を通して、数学で遊ぶ楽しさのようなものを少しでも感じていただければ幸いです。

最後に、この問題を僕のところに持ち込んできてくれ、一緒に証明を考えてくれた友人に感謝します。

それではまた次の記事で会いましょう。さようなら。

参考文献

[1] Corless, R. M., Gonnet, G. H., Hare, D. E., Jeffrey, D. J., & Knuth, D. E. (1996). On the LambertW function. Advances in Computational mathematics, 5(1), 329-359.
[2] Knuth, D. E., & Pittel, B. (1989). A recurrence related to trees. Proceedings of the American Mathematical Society, 105(2), 335-349.
[3] Riordan, J. (1968). Combinatorial identities., Wiley, New York.
[4] Gessel, I. M. (2016). Lagrange inversion. Journal of Combinatorial Theory, Series A, 144, 212-249.
[5] Harris, B., & Schoenfeld, L. (1967). The number of idempotent elements in symmetric semigroups. Journal of Combinatorial Theory, 3(2), 122-135.
[6] Comtet, L. (2012). Advanced Combinatorics: The art of finite and infinite expansions. Springer Science & Business Media.
[7] Flajolet, P., & Sedgewick, R. (2009). Analytic Combinatorics. cambridge University press.

*1:ProductLog[x]はランベルトのW関数のことです。

*2:この定理には等価な表現が複数あることに注意してください。

*3:簡単に言えば、複素数の範囲での微分積分を考える分野のことです。

*4:すなわち、関数$\displaystyle{\frac{1}{1+W(-xe^x)}}$は$\displaystyle{\frac{1}{1+W(-x)}}$と$xe^x$の合成関数になっているということです。

*5:過激派「$e^x$のべき級数展開ぐらい生まれたときから知ってろ」

*6:各因数の次数は少なくとも$1$あるので、$x^{N-k+1}$より次数の大きい項をとってくることはできません。掛け合わせた結果が$x^N$を超えてしまいます。

*7:ここで紹介したのは、べき級数で表された関数を合成したときに、合成後の関数のべき級数展開を求めるための最も一般的な手法です。その方法を一般的に書き表した公式はFaà di Bruno's formulaと呼ばれています。

*8:余談ですが、$\displaystyle{\sum_{k=0}^n{}_n{\rm C}_k k^{n-k}}$は冪等数(idempotent number)と呼ばれる数列で、$n$個の元からなる集合から自分自身への写像のうち、冪等写像であるものの総数を表します(OEIS:A000248を参照)。ここで$f$が冪等写像であるとは、$f^2=f$が成り立つことをいいます。

*9:二項係数${}_n{\rm C}_r$は通常$n,r$が$0\leq r\leq n$なる自然数であるときに定義されますが、それを拡張して、$n$が一般の実数のときにも$\binom{n}{r}=n(n-1)\cdots (n-r+1)/r!$でもって二項係数を定義することができます。これを一般化二項係数といいます。

*10:証明は文献[7] (Flajolet & Sedgewick, 2009)のp.381-383などを参照してください。

*11:$f(x)$が$f_n$の「指数型」母関数であるのに対し、$g(x)$は$g_n$の「通常型」母関数です。$n!$のファクターを忘れないでください。

*12:説明が分かりやすくなるように、変数を$x$から$y$に変えています。

*13:よく考えたら合成関数なんだから#それはそうでした。

*14:異論は認めます。