スターリングの近似（Stirling's approximation）

2.1 Worst-Case Entropyでスターリングの近似が紹介されています。

$n! = \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n \left(1+\mathcal{O}\left(\frac{1}{n}\right)\right)$

その後、2.3.1 Bit Sequencesにて以下のような等式が出てきます。

$\log{\binom{n}{m}} = n\log{n} - m\log{m} - (n-m)\log{(n-m)} - \mathcal{O}(\log{n})$

これに関して we used Stirling's approximation と書いてあるのですが、どこがだよ感がすごい。

スターリングの近似はNavarro本序盤の人権数式なので、きちんと育成（理解）しておかないと詰みかねません。

というわけで落ち着いて導出をしていきます。

まず√nについてO()で表現して以下を得ます。後ろのO(1/n)はO(√n)に含まれるので消しちゃっていいはず（自信なし）。

$n! = \mathcal{O}(\sqrt{n}) \left(\frac{n}{e}\right)^n$

次にn!の対数をとります。log(√n)=(1/2)log(n)なのでlog O(√n)=O(log(n))な点に注意。

$\log{n!} = n\log{n} - n\log{e} + \mathcal{O}(\log{n})$

logの底がeだったらnlog(e)はnになりますが、Navarro本では底は2なのでそうはなりません。

Wikipediaには底がeのバージョンが「よく使われる」として書いてあります。

なんにせよ、ここまできたら以下を得ることができます（はてなブログでなぜかtexの改行が効かなかったので見た目がよくない）。

$\log{\binom{n}{m}} = \log{\left(\frac{n!}{m!(n-m)!}\right)}$ $=\log{n!} - \log{m!} - \log{(n-m)!}$ $= n\log{n} - m\log{m} - (n-m)\log{(n-m)} - (n - m - (n - m))\log{e}$ $+ \mathcal{O}(\log{n}) - \mathcal{O}(\log{n}) - \mathcal{O}(\log{n})$ $= n\log{n} - m\log{m} - (n-m)\log{(n-m)} - \mathcal{O}(\log{n})$