1.15 多項式の独立パラメータの数

D次元の多項式のM次の項、すなわち \({\bf x} = (x_1, x_2, \cdots, x_D)^T\)という縦ベクトルのD個の要素からM個を重複して選んで掛け合わせるという話です。
重複してというのがポイントです。

\(
\begin{eqnarray}
\sum_{i_1=1}^D\sum_{i_2=1}^D\cdots\sum_{i_M=1}^D w_{i_1i_2\cdots i_M}x_{i_1}x_{i_2}\cdots x_{i_M}
\end{eqnarray}
\)

式にすると相当分かりづらいですが、2次元の3次の項を例にすると、

\(
\begin{eqnarray}
&&\sum_{i_1=1}^2\sum_{i_2=1}^2\sum_{i_3=1}^2 w_{i_1i_2i_3}x_{i_1}x_{i_2}x_{i_3} \\
&=& w_{111}x_1x_1x_1+w_{112}x_1x_1x_2+w_{121}x_1x_2x_1+w_{122}x_1x_2x_2 \\
& & +w_{211}x_2x_1x_1+w_{212}x_2x_1x_2+w_{221}x_2x_2x_1+w_{222}x_2x_2x_2 \\
&=& w_{111}x_1^3+(w_{112}+w_{121}+w_{211})x_1^2x_2+(w_{122}+w_{212}+w_{221})x_1x_2^2+w_{222}x_2^3
\end{eqnarray}
\)

\(x_1^2x_2\)と\(x_1x_2^2\)の項がまとめられるので、もともと\(2^3=8\)項あったものが4項にまとめられる。
D次元のM次の多項式も同様で、

\(
\begin{eqnarray}
\sum_{i_1=1}^D\sum_{i_2=1}^{i_1}\cdots\sum_{i_M=1}^{i_{M-1}} \tilde{w}_{i_1i_2\cdots i_M}x_{i_1}x_{i_2}\cdots x_{i_M}
\end{eqnarray}
\)

とまとめられる。
独立なパラメータの数は、

\(
\begin{eqnarray}
n(D,M)=\sum_{i_1=1}^D{\color{red}{\sum_{i_2=1}^{i_1}\cdots\sum_{i_{M-1}=1}^{i_{M-2}}\sum_{i_M=1}^{i_{M-1}}}}1
\end{eqnarray}
\)

で求められるが、上の式の赤字の部分に注目すると、

\(
\begin{eqnarray}
n(D,M)=\sum_{i_1=1}^D n(i_1,M-1)
\end{eqnarray}
\)

であることが分かる。\(i_1\)を\(i\)に変更して書き直すと、

\(
\begin{eqnarray}
n(D,M)=\sum_{i=1}^D n(i,M-1)
\end{eqnarray}
\)

次に、

\(
\begin{eqnarray}
\sum_{i=1}^D \frac{(i+M-2)!}{(i-1)!(M-1)!} = \frac{(D+M-1)!}{(D-1)!M!}
\end{eqnarray}
\)

を数学的帰納法により証明する。
まず、\(D=1\) の場合、左辺は、

\(
\begin{eqnarray}
\sum_{i=1}^1 \frac{(i+M-2)!}{(i-1)!(M-1)!} = \frac{(M-1)!}{0!(M-1)!} = 1
\end{eqnarray}
\)

右辺に\(D=1\)を代入すると

\(
\begin{eqnarray}
\frac{(D+M-1)!}{(D-1)!M!} = \frac{M!}{0!M!} = 1
\end{eqnarray}
\)

したがって、\(D=1\) で成立する。
D次元で成立するとすると、D+1次元の場合、

\(
\begin{eqnarray}
\sum_{i=1}^{D+1} \frac{(i+M-2)!}{(i-1)!(M-1)!} &=& \frac{(D+1+M-2)!}{(D+1-1)!(M-1)!} +
\sum_{i=1}^D \frac{(i+M-2)!}{(i-1)!(M-1)!} \\
&=& \frac{(D+M-1)!}{D!(M-1)!} + \frac{(D+M-1)!}{(D-1)!M!} \\
&=& \frac{M(D+M-1)!+D(D+M-1)!}{D!M!} \\
&=& \frac{(D+M)(D+M-1)!}{D!M!} \\
&=& \frac{(D+M)!}{D!M!}
\end{eqnarray}
\)

となり、D+1次元でも成立することが分かる。

最後に

\(
\begin{eqnarray}
n(D,M) = \frac{(D+M-1)!}{(D-1)!M!}
\end{eqnarray}
\)

を数学的帰納法により証明する。
まず、M=2の場合、

\(
\begin{eqnarray}
n(D,2) &=& \sum_{i=1}^D n(i,1) \\
&=& n(1,1)+n(2,1)+\cdots+n(D,1) \\
&=& 1+2+\cdots+D \\
\end{eqnarray}
\)

となる。\(n(1,1)\)は1次元の1次の項、すなわち \(x_1\)しかないので1になるし、\(n(2,1)\)は2次元の1次の項、\(x_1, x_2\)の2つになる・・・とやっていくと、

\(
\begin{eqnarray}
n(D,2)
&=& 1+2+\cdots+D
&=& \frac{D(D+1)}{2}
\end{eqnarray}
\)

となる。したがって、M=2の場合は成立する。
\(M-1\)で成立すると仮定すると、

\(
\begin{eqnarray}
n(D,M-1) = \frac{(D+M-2)!}{(D-1)!(M-1)!}
\end{eqnarray}
\)

なので、

\(
\begin{eqnarray}
n(D,M) &=& \sum_{i=1}^D n(i,M-1) \\
&=& \sum_{i=1}^D \frac{(i+M-2)!}{(i-1)!(M-1)!} \\
\end{eqnarray}
\)

ここで、

\(
\begin{eqnarray}
\sum_{i=1}^D \frac{(i+M-2)!}{(i-1)!(M-1)!} = \frac{(D+M-1)!}{(D-1)!M!}
\end{eqnarray}
\)

はすでに証明済みであることを思い出すと、

\(
\begin{eqnarray}
n(D,M)
&=& \frac{(D+M-1)!}{(D-1)!M!}
\end{eqnarray}
\)

となり、証明できた。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です