1
$\begingroup$

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.

3 Answers 3

1

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

  • 0
    This seems like magic to me.2012-11-23
2

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.

  • 0
    Oh, I see! thank you. I accepted saposcat's answer because it is more elegant.2012-11-20
1

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

  • 0
    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)$.2012-11-21