2

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?

Community
  • 1
user12290
  • 1,305

1 Answers1

1

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.
Wei Zhan
  • 740
  • 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 02: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 04:31
  • @user12290 I've got something wrong. It should be $k$ instead of $k-1$. – Wei Zhan Aug 19 '13 at 05:23
  • @user12290 Now I fixed my answer and your approximation is good. – Wei Zhan Aug 19 '13 at 05:57