多重和の解法

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

一般に, 多重和問題

構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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}\}}\,}

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

構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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\leq n\leq N.}\end{array}}\,}

ただし, 構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x^{n}=(x_{1},x_{2},\ldots ,x_{n}).\,}