Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is the extension of my previous question. Let $A= \sum_{x_1=0}^m \sum _{x_2=0}^m \cdots \sum_{x_n=0}^m \min_r(x_1, x_2,.., x_n)$ where $\min_r$ is the $r^{th}$ minimum of $(x_1, x_2,.., x_n)$. For example if $x_1\leq x_2 \leq \cdots x_r \leq \cdots $ then $\min_r(x_1, \ldots, x_n)=x_r.$

Now let $B =\sum_{k=0}^m n \binom{n-1}{r-1}k^{r-1}(m-k)^{n-r}k.$ Is it true $\frac{A}{B} \rightarrow 1$ as $m $ approaches to infinity?

For each $k$, we need $\{y_1,\ldots, y_{r-1}, y_n\}=\{x_1, \ldots, x_n\}$ such that $y_1 \leq y_2 \ldots \leq y_{r-1}\leq k \leq y_r\ldots \leq y_n$.

Now choice of $y_1 \leq y_2 \ldots \leq y_{r-1}$ is $k^{r-1}$ and for $y_{r+1},\ldots y_n$ is $(m-k)^{n-r}$. For each such choice we add $k$.

Am I missing anything?

share|cite|improve this question
Is there special meaning to $k^{r-1}k$ in the definition of $B$? – Jonathan Y. Aug 18 '13 at 23:55
up vote 1 down vote accepted

You are to count the $\{y_1,\ldots,y_n\}$ so that $$y_1\leq\ldots\leq y_{r-1}\leq k = y_r\leq\ldots\leq y_n$$ The number of it should be $k^{r-1}(m-k)^{n-r}$. However, this CAN NOT show the number of corresponding $\{x_1,\ldots,x_n\}$, if you just multiply it by the "choices" $nC_{n-1}^{r-1}$. The reseason here is that there may be other $y_i$'s whose values equal $k$ but you ignored them.

So you have to take multiplicity of $k$ into consideration. The formula should be: $$\sum_{i=0}^{r-1}\sum_{j=0}^{n-r}C_{n}^{i+j+1}C_{n-i-j-1}^{r-i-1}k^{r-i-1}(m-k)^{n-r-j}$$ Here we suppose $y_{r-1}=\ldots=y_{r-i}=k$ and similarly for $j$. In a briefer version $$\sum_{i=0}^{r-1}\sum_{j=0}^{n-r}C_n^{i+j}C_{i+j}^ik^i(m-k)^j$$

So the sum is $$A=\sum_{k=0}^mk\sum_{i=0}^{r-1}\sum_{j=0}^{n-r}C_n^{i+j}C_{i+j}^ik^i(m-k)^j$$ and your $B$ select only the terms with indices $i=r-1,j=n-r$.

Added: The remained part is to know the asymptotic behavior of sum $$S(m)=\sum_{k=0}^mk^i(m-k)^j$$ when $m\rightarrow\infty$ with fixed $i,j$. We divide it by $m^{i+j+1}$ to get $$\sum_{k=0}^m\frac{1}{m}\left(\frac{k}{m}\right)^i\left(1-\frac{k}{m}\right)^j$$ Notice its limit is just the form of a integral, so we have: $$\lim_{m\rightarrow\infty}\frac{S(m)}{m^{i+j+1}}=\int_0^1x^i(1-x)^j\mathrm{d}x$$ and the right side is a constant. So we get the asymptotics: $S(m)=\Theta(m^{i+j+1})$. With this and the expression of $A$ and $B$, it's easy to know that $A\sim B$ when $m\rightarrow\infty$. You are right.

share|cite|improve this answer
Yes, I knew that it does not cover all. But I want to calculate good approximation such that these two sums A& B be such that A/B tends to 1 for large m. I need compact form. – user12290 Aug 19 '13 at 2:31
For $m=2$, $\sum_{x_1,.., x_5=0}^2 \min_2(x_1,x_2,x_3,x_4,x_5)$ will be 123. But your equation gives 38. $\min_2$ is the second minimum. For example $\min_2(1,3,2,5,2)=2$ – user12290 Aug 19 '13 at 4:31
@user12290 I've got something wrong. It should be $k$ instead of $k-1$. – Willard Zhan Aug 19 '13 at 5:23
@user12290 Now I fixed my answer and your approximation is good. – Willard Zhan Aug 19 '13 at 5:57
Thank very much. – user12290 Aug 19 '13 at 17:01

Your Answer


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.