Algorithm to iterate terms of a sum

I face the situation where I have to manipulate power series and calculate coefficients. My goal is to write a program and let mathematica do the computations. So I run into this problem. When I try to calculate the $n$-th power of a power series I have the term I denote $x_{n,k}$, $n,k\in\mathbb{N}$, defined by $$x_{n,k}:=\sum_{m_1+\ldots+m_n=k} x_{m_1}\cdot x_{m_2}\cdot\ldots\cdot x_{m_n}$$ with $x_i$'s known and $m_i$'s positive integers or zero. So my goal is to write a function such that when I provide $n$ and $k$ it returns the value. My problem is how to write the sum correctly in a way computer will understand. I don't ask for specific syntax, but rather for an algorithm that will iterate every term in this sum.

-

The easiest may be to write your function recursively :

If your sum is indexed by all the n-tuples such that the sum is equal to $k$, $$x_{n,k}= \sum_{m_1=0}^k x_{m_1}x_{n-1, k-m_1}$$ and $x_{0,k}=\mathbf{1}_{k=0}$.

-
This is a very elegant solution! I'll just note that $x_{1,k}=x_k$, so there is no need to go to $k=0$, but nevertheless it is great. –  tst Nov 20 '12 at 19:24
This is almost good, the only problem is that plain recursion is $O(k^n)$, while adding memoization (compute each state only one times) fasten the process to $O(k^2*n)$. –  carlop Nov 21 '12 at 11:04

The best solution seem to me dynamic programming.

Store a matrix DP[0....n][0....k], where each element DP[i][j] represent the sum over each product of $i$ elements and with $\sum{m}=j$.

You have as starting value $DP[0][0]=1$ and $DP[0][j]=0$ iff $j\ge1$, and then you need to iterate over each $i$ and $j$ with $DP[i][j]=\sum_{a=0}^{j} {DP[i-1][j-a]*x_a}$.

After all the calculation $DP[n][k]$ is the solution that you are looking, and you can compute it in $O(k^2*n)$ time. For smaller value of $k$ you can also try a brute force approach, but this seem better to me.

-
your sum should be indexed by a=0 to j i think, because the m_i's can be zero. And i think the initial condition sould be DP[O][i]=1 iff i=0 and 0 else. –  saposcat Nov 20 '12 at 17:00
problems fixed, thanks –  carlop Nov 20 '12 at 17:12
Oh, I see! thank you. I accepted saposcat's answer because it is more elegant. –  tst Nov 20 '12 at 19:45

The following is a Mathematica solution, based simply on mapping over the weak $n$-compositions of $k$ (i.e. letting Mathematica worry about recursion and/or iteration):

xnk[n_, k_] := Plus @@ Times @@@ Map[Subscript[x, #] &,
Join @@ Permutations /@ IntegerPartitions[k + n, {n}] - 1, {2}]


For example,

xnk[3,7]


gives $$3 x_2^2 x_3+3 x_1 x_3^2+6 x_1 x_2 x_4+6 x_0 x_3 x_4+3 x_1^2 x_5+6 x_0 x_2 x_5+6 x_0 x_1 x_6+3 x_0^2 x_7.$$

-
This seems like magic to me. –  tst Nov 23 '12 at 2:30