PRML 第1章 1.16(難問)

---

$$
\begin{array}{ll}
(1.138) & N(D,M) = {\displaystyle \sum_{m=0}^M} n(D,m)\\[1.5em]
(1.139) & N(D,M) = \dfrac{(D+M)!}{D!M!}\\[1.5em]
(1.140) & n! \simeq n^n e^{-n}
\end{array}
$$

---

解答

　次数が異なる項は独立であるから，

$$
\begin{array}{l}
N(D,M) = n(D,0) + n(D,1) + \cdots + n(D,M) = {\displaystyle \sum_{m=0}^M} n(D,m)
\end{array}
$$

が成り立つ．

　次に，(1.139)を数学的帰納法で示す．$${M=0}$$の場合，演習問題1.15より，

$$
\begin{array}{lll}
(左辺) &=& N(D,0) = n(D,0) = \dfrac{(D+0-1)!}{(D-1)!0!} = 1\\[1em]
(右辺) &=& \dfrac{(D+0)!}{D!0!} = 1
\end{array}
$$

となり，(1.139)は$${M=0}$$で成立する．また，$${M}$$次のときに(1.139)が正しいと仮定すると，

$$
\begin{array}{lll}
N(D,M+1) &=& {\displaystyle \sum_{m=0}^{M+1}} n(D,m)
= {\displaystyle \sum_{m=0}^M} n(D,m) + n(D,M+1)\\[1.5em]
&=& \dfrac{(D+M)!}{D!M!} + \dfrac{(D+M)!}{(D-1)!(M+1)!}\\[1.5em]
&=& \dfrac{(D+M)!}{D!(M+1)!} (M+1 + D)\\[1.5em]
&=& \dfrac{(D+M+1)!}{D!(M+1)!}
\end{array}
$$

となり，$${M+1}$$次でも正しい．したがって，数学的帰納法により，0以上のすべての自然数$${M}$$について(1.139)が成り立つ．

　さらに，(1.139)で$${D \gg M}$$とすると，スターリングの公式より，

$$
\begin{array}{l}
N(D,M) \simeq \dfrac{(D+M)!}{D!}
\simeq \dfrac{(D+M)^{D+M} e^{-(D+M)}}{D^D e^{-D}}
\simeq \dfrac{D^{D+M} e^{-D}}{D^D e^{-D}}
= D^M
\end{array}
$$

のオーダーで$${N(D,M)}$$は大きくなる．同様に考えることで，$${M \gg D}$$のときは$${M^D}$$で大きくなる．

　以上の結果より，$${D}$$次元の3次多項式($${M=3}$$)の場合は，

$$
\begin{array}{l}
N(D,M) = \dfrac{(D+3)!}{D!3!} = \dfrac16 (D+3)(D+2)(D+1)
\end{array}
$$

となるので，

$$
\begin{array}{cl}
(\mathrm{i}) & N(10,3) = \dfrac{13\times 12\times 11}{6} = 286\\[1em]
(\mathrm{ii}) & N(100,3) = \dfrac{103\times 102\times 101}{6} = 176851
\end{array}
$$

となる．