You are currently browsing the tag archive for the ‘summation’ tag.

I am caught with a little trouble to figure out an easier way to set up and solve a  summation of a function of several variables.  I just realized that Mathematica doesnt allow me to add a constraint in the summation operation.  My problem  is that, the summation should be performed over  the ordered partition set of a number

An example, will illustrate the problem definition a lot better.  Suppose I want to compute the sum of a function of $3$ variables over all variables such that, the sum of the index variables always equal to a constant $n$

$\displaystyle \sum_{\underset{i+j+k=n}{i,j,k}}f(i,j,k)$

Clearly, the indices here runs over all the ordered partitions of the number $3$.  Since $3$ is not that big a number, we can simply write these partitions by hand and somehow get the job done.  Let us say denote the ordered partitions and unordered partitions of the number $n$ by $P(n)$ and $Q(n)$ respectively.

$Q(3) =( (3), (2, 1),(1, 1, 1))$. The ordered partition will have the permutations of each of these on the three positions! So $(0,0,3)$ and $(0,3,0)$ are different sets of $P(3)$ whereas, they are considered as one $(3)$ in $Q(3)$.  The summation needs to be carried over the ordered partition list $P(n)$.  Since both $Q(n)$  and $P(n)$ grow pretty big with even modest $n$, the job of manual summation is not that appealing. I really hoped mathematica to aid me here. Unfortunately, I don’t see a way out here, other than the painful individual partition sum.  Anyway, for the curious reader, the sum I attempt are of the following types:

$\displaystyle \sum_{n_1+n_2+\ldots+n_k=n}{(n_1+1)a_1\frac{n!}{n_1!n_2!\ldots n_k!}\frac{a_{1}^{n_1} a_{2}^{n_2} \ldots a_{k}^{n_k}}{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}} }$

$\displaystyle \sum_{n_1+n_2+\ldots+n_k=n}{(n_1+1-n_2)a_1\frac{n!}{n_1!n_2!\ldots n_k!}\frac{a_{1}^{n_1} a_{2}^{n_2} \ldots a_{k}^{n_k}}{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}} }$

typical values for $n$ is $20$ and $k$ is around $10$. If any enthused reader finds a way/trick, I will be happy to sponsor a coffee 🙂 (Sorry at this recession time, nothing more 😦 sadly…).

In fact, the first one is easy (Interestingly, I just found a way, while typesetting the blog).  I can do a differential with respect to $a_1$ and then scale it to get the requisite sum.  It can be written as follows:

$\displaystyle \sum_{n_1+n_2+\ldots+n_k=n}{(n_1+1)a_1\frac{n!}{n_1!n_2!\ldots n_k!}\frac{a_{1}^{n_1} a_{2}^{n_2} \ldots a_{k}^{n_k}}{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}} }$

$=\frac{a_1}{{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}}} \frac{\partial}{\partial a_1}\left[a_1 \left(a_1+a_2+\ldots+a_k\right)^{n}\right]$

$=\frac{a_1}{{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}}} \left[n a_1 \left(a_1+a_2+\ldots+a_k\right)^{n-1}+\left(a_1+a_2+\ldots+a_k\right)^{n}\right]$

Second one is the trouble maker 😦

Oh man! power of a coffee.  As I am typing this on a moody Lausanne swiss weather, here comes the trick.  I just made a coffee and that seemed to have worked.  I guess I can apply a similar trick to the second one too.  Basically, we can split them into two expressions and then write each as differential versions of a multinomial sum. Here it is:

$\displaystyle \sum_{n_1+n_2+\ldots+n_k=n}{(n_1+1-n_2)a_1\frac{n!}{n_1!n_2!\ldots n_k!}\frac{a_{1}^{n_1} a_{2}^{n_2} \ldots a_{k}^{n_k}}{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}} }$

$=\displaystyle \sum_{n_1+n_2+\ldots+n_k=n}{(n_1+1)a_1\frac{n!}{n_1!n_2!\ldots n_k!}\frac{a_{1}^{n_1} a_{2}^{n_2} \ldots a_{k}^{n_k}}{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}} }$

$-\displaystyle \sum_{n_1+n_2+\ldots+n_k=n}{(n_2)a_1\frac{n!}{n_1!n_2!\ldots n_k!}\frac{a_{1}^{n_1} a_{2}^{n_2} \ldots a_{k}^{n_k}}{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}} }$

$=\frac{a_1}{{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}}} \frac{\partial}{\partial a_1}\left[a_1 \left(a_1+a_2+\ldots+a_k\right)^{n}\right]$

$-\frac{a_1 a_2}{{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}}} \frac{\partial}{\partial a_2}\left[\left(a_1+a_2+\ldots+a_k\right)^{n}\right]$

$=\frac{a_1}{{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}}} \left[n a_1 \left(a_1+a_2+\ldots+a_k\right)^{n-1}+\left(a_1+a_2+\ldots+a_k\right)^{n}\right]$

$-\frac{a_1 a_2}{{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}}} \left[n \left(a_1+a_2+\ldots+a_k\right)^{n-1}\right]$

Amazingly, we can simplify both to get a simple looking expression. I am glad! Here is what I finally got:

$\displaystyle \sum_{\sum_{j}{ n_j}=n}{\frac{n!(n_1+1)a_1}{n_1!n_2!\ldots n_k!}\frac{a_{1}^{n_1} a_{2}^{n_2} \ldots a_{k}^{n_k}}{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}} }=\frac{a_1\left(na_1+\sum_{i}{a_i}\right)}{{\left(\sum_{i=1}^{k}{a_i}\right)^{2}}}$

$\displaystyle \sum_{\sum_{j}{ n_j}=n}{\frac{n!(n_1+1-n_2)a_1}{n_1!n_2!\ldots n_k!}\frac{a_{1}^{n_1} a_{2}^{n_2} \ldots a_{k}^{n_k}}{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}} }=\frac{a_1\left(n(a_1-a_2) +\sum_{i}{a_i}\right)}{{\left(\sum_{i=1}^{k}{a_i}\right)^{2}}}$

$\displaystyle \sum_{\sum_{j}{ n_j}=n}{\frac{n!(n_l)a_1}{n_1!n_2!\ldots n_k!}\frac{a_{1}^{n_1} a_{2}^{n_2} \ldots a_{k}^{n_k}}{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}} }=\frac{a_1 a_l n}{{\left(\sum_{i=1}^{k}{a_i}\right)^{2}}}$