Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

3 Answers 3

up vote 1 down vote accepted

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}$.

share|improve this answer
    
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
add comment

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.

share|improve this answer
1  
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
add comment

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.$$

share|improve this answer
    
This seems like magic to me. –  tst Nov 23 '12 at 2:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.