# arithmetic mean of smallest numbers of all subsets of r elements formed out of (1,2,..n)

Consider all subsets of r elements of the set $\{1,2,3,......,n\}$ where $1 \leq r \leq n$. Each of these subsets has a smallest member. Let $F(n,r)$ denote the arithmetic mean of these smallest numbers then $$F(n,r)=\frac{n+1}{r+1}\;.$$ I got this solution on a page but couldn't understand it as how he started and what are the different steps one needs to take. Throw light on every single step.

\begin{align*} \sum_{k=1}^nk\binom{n-k}{r-1}&=\sum_{k=1}^{n-(r-1)}k\binom{n-k}{r-1}\\ &=\sum_{i=1}^{n-(r-1)}\sum_{k=i}^{n-(r-1)}\binom{n-k}{r-1}\\ &=\sum_{i=1}^{n-(r-1)}\binom{n-i+1}r\\ &=\binom{n+1}{r+1}\;. \end{align*}

And

$$\frac{\binom{n+1}{r+1}}{\binom{n}r}=\frac{n+1}{r+1}\;.$$

• You can typeset it beautifully using MathJax (this is a link to a turotial). – String Apr 27 '16 at 9:11
• @String I don't have enough knowledge of Matjax – satyajeet jha Apr 27 '16 at 9:12
• @string it is (n+1)/(r+1) not what you wrote – satyajeet jha Apr 27 '16 at 9:17
• @string i edited it completely so its clear now ,i think – satyajeet jha Apr 27 '16 at 9:23

The number of subsets having $k$ as its smallest element will be $$\binom{n-k}{r-1}$$ since the remaining $r-1$ elements in such a subset must be chosen from the remaining $n-k$ larger elements. But we cannot choose $r-1$ elements unless we have $n-k\geq r-1$ elements to choose from. Thus it follows by rearranging that $1\leq k\leq n-(r-1)$. So the sum of the smallest elements $k$ counted by multiplicity $\binom{n-k}{r-1}$ must be: $$\sum_{k=1}^{n-(r-1)}k\binom{n-k}{r-1}$$

Next step uses that $$\sum_{k=1}^m k\cdot f(k)=\sum_{i=1}^m\sum_{j=i}^m f(j)$$ since in the second double sum a given value $k$ of $j$ is only iterated through if $i\leq k$ which happens exactly $k$ times, namely for $i=1,2,...,k$.

For the final two steps the principle is $$\sum_{s=a}^b\binom{s}{a}=\binom{a}{a}+\binom{a+1}{a}+...+\binom{b}{a}=\binom{b+1}{a+1}$$ which is true since choosing $a+1$ elements from a set containing $b+1$ elements can be done by choosing the smallest element first and then choosing the remaining $a$ elements from the remaining $s\in[a,b]$ larger elements.

The first time it is used where $s=n-k$ ranges from $a=r-1$ to $b=n-i$ and the second time it is used where $s=n-i+1$ ranges from $a=r$ to $b=n$. To be explicit: $$\sum_{k=i}^{n-(r-1)}\binom{n-k}{r-1}=\sum_{s=r-1}^{n-i}\binom{s}{r-1}=\binom{n-i+1}{r}$$ and $$\sum_{i=1}^{n-(r-1)}\binom{n-i+1}{r}=\sum_{s=r}^n\binom{s}{r}=\binom{n+1}{r+1}$$

So now we have the sum of all the smallest elements. Then we just need to divide by the number of them, namely $\binom nr$ and so the average smallest element will be: $$\mu=\frac{\binom{n+1}{r+1}}{\binom{n}{r}}=\frac{n+1}{r+1}$$

• please explain the remaining part after second = to in solution as how it has been done. – satyajeet jha Apr 27 '16 at 9:35
• @satya: I am working on it ... – String Apr 27 '16 at 9:35

The number of ways that $k$ is the smallest of $r$ numbers from $1\dots n$ is $$\binom{n-k}{r-1}\tag{1}$$ As one would expect, the total number of ways to arrange the $r$ numbers from $1\dots n$ is $$\sum_{k=1}^{n-r+1}\binom{n-k}{r-1}=\binom{n}{r}\tag{2}$$ Thus, the expected smallest of $r$ numbers from $1\dots n$ times $(2)$ is \begin{align} \sum_{k=1}^{n-r+1}\binom{n-k}{r-1}k &=(n+1)\binom{n}{r}-\sum_{k=1}^{n-r+1}\binom{n-k}{r-1}(n-k+1)\\ &=(n+1)\binom{n}{r}-\sum_{k=1}^{n-r+1}\binom{n-k+1}{r}\,r\\ &=(n+1)\binom{n}{r}-\binom{n+1}{r+1}\,r\\ &=(n+1)\binom{n}{r}-\frac{n+1}{r+1}\binom{n}{r}\,r\\ &=\frac{n+1}{r+1}\binom{n}{r}\tag{3} \end{align} Therefore, the expected smallest of $r$ numbers from $1\dots n$ is $$\frac{n+1}{r+1}\tag{4}$$