1
$\begingroup$

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}\;.$$

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

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} $$

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

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} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.