# Calculate the following sum:

For fixed positive integers $n$ and $k$, $$\sum_{n_1 ,n_2 , \cdots , n_k \geq 0 }^n \prod_{i=1}^k \min(n_1,n_2,\cdots,\langle n_i\rangle,\cdots, n_k )\;,$$ where $\min(n_1,n_2,\cdots,\langle n_i\rangle,\cdots, n_k )$ is the minimum of $\{ n_1, \cdots, n_k \} - \{n_i\}.$ See arxiv:math/0606163v1 for motivation.

-
Orders given, no motivation indicated, no answer accepted: three reasons to leave. –  Did Apr 28 '12 at 15:16
How can I do it? In fact, I don't know how to accept it! –  hkju Apr 28 '12 at 15:20
See there. –  Did Apr 28 '12 at 15:26
Thanks for the kind information!!! –  hkju Apr 28 '12 at 15:37
It isn't the points; without accepting, we have no idea if what we're writing is helpful to you, and if it's not helpful to you, why should we bother writing? –  Ｊ. Ｍ. Apr 28 '12 at 16:01

For fixed $n_1, \ldots, n_k$, with $n_{(1)}$ the smallest, $n_{(2)}$ the second smallest of these etc., the latter product over $i$ is equal to $n_{(1)}^{k-1} n_{(2)}$. So the sum is equivalent to:

$$\sum_{n_{(1)} = 1}^n \ \sum_{n_{(2)} = n_{(1)}}^n \ \sum_{n_{(3)}, \ldots, n_{(k)} = n_{(2)}}^n n_{(1)}^{k-1} \cdot n_{(2)} = \sum_{n_{(1)} = 1}^n \ \sum_{n_{(2)} = n_{(1)}}^n n_{(1)}^{k-1} \cdot n_{(2)} \sum_{n_{(3)}, \ldots, n_{(k)} = n_{(2)}}^n 1.$$

Now the last summation is equal to the number of terms, which is $(n - n_{(2)} + 1)^{k-2}$, so this is equal to

$$\sum_{n_{(1)} = 1}^n \ \sum_{n_{(2)} = n_{(1)}}^n n_{(1)}^{k-1} \cdot n_{(2)} \cdot (n - n_{(2)} + 1)^{k-2}.$$

Switching the first and second summation, we get

$$\sum_{n_{(2)} = 1}^n n_{(2)} \cdot (n - n_{(2)} + 1)^{k-2} \sum_{n_{(1)} = 1}^{n_{(2)}} n_{(1)}^{k-1}.$$

You can approximate the last summation with $n_{(2)}^k/k + n_{(2)}^{k-1}/2 + O(n_{(2)}^{k-2})$ as described here, but even with this approximation, solving the remaining summation seems hard. My (educated) guess for a final approximation would be $\Theta(n^{2k})$, with constant $1/(2k)$. This may not be very helpful, but I doubt you can get a nicer expression than this.

-
Thanks for trying. But I want to get explicit formula in $n$, probably polynomial in $n$. –  hkju Apr 28 '12 at 15:48
Recently I encounted with so-called <Maxalgebra>. But I have no deep knowledge about it. Maybe it could make us to solve the problem I proposed here. –  hkju May 8 '12 at 5:56
Maxplus algebra is related with Tropical Geometry. –  hkju May 8 '12 at 5:59