多重和の解法

【たじゅうわのかいほう (solution of multiple summation)】

一般に, 多重和問題

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \displaystyle{\sum \{g(x_{1}, x_{2}, x_{3}, \ldots , x_{N+1})} \displaystyle{\mid (x_{2}, x_{3}, \ldots , x_{N+1}) \in X^{N} \} } \,}

は次の後向き再帰式で解ける:

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \begin{array}{l} \displaystyle{w_{N+1}(x^{N+1}) = g(x^{N+1}), \quad x^{N+1} \in X^{N+1} } \\ \displaystyle{ w_{n}(x^{n}) = \sum_{y \in X}w_{n+1}(x^{n}, y), } \ \ \ \ \displaystyle{x^{n} \in X^{n},~ 1 \le n \le N. } \end{array} \,}

ただし, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x^{n} = (x_{1}, x_{2}, \ldots , x_{n}). \,}