【たじゅうわのかいほう (solution of multiple summation)】
一般に, 多重和問題
∑ { g ( x 1 , x 2 , x 3 , … , x N + 1 ) ∣ ( x 2 , x 3 , … , x N + 1 ) ∈ X N } {\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}\}}\,}
は次の後向き再帰式で解ける:
w N + 1 ( x N + 1 ) = g ( x N + 1 ) , x N + 1 ∈ X N + 1 w n ( x n ) = ∑ y ∈ X w n + 1 ( x n , y ) , x n ∈ X n , 1 ≤ n ≤ N . {\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}}\,}
ただし, x n = ( x 1 , x 2 , … , x n ) . {\displaystyle x^{n}=(x_{1},x_{2},\ldots ,x_{n}).\,}
