Problem to find arithmetic mean of the largest elements of $r$-subsets of ${1,2,...,n}$

Question

Let $1\le r\le n$ and consider all $r$-element subsets of the set $\{1,2,...,n\}$. Each of these subsets has a largest element. Let $H(n,r)$ denote the arithmetic mean of these largest numbers. Find $H(n,r)$ and simplify your result.

I have made the following attempt, but get stuck:

Possible largest elements in $r$-element subsets are: $\{r, r+1,\ldots,n-1,n\}$

If $r$ is the largest elements, other elements must be taken from the $r-1$ elements $\lt r$. Their sum of given by: $$r{r-1 \choose r-1}$$

Similarly, summing over $\{r, r+1,...,n\}$ gives:

$$r{r-1 \choose r-1} + (r+1){r \choose r-1}+\cdots+n{n-1 \choose r-1}$$

Dividing the above expression by ${n \choose r}$ should give me their arithmetic mean. But I know not how to simplify the expression...

All help is greatly appreciated! Thanks you!

P.S.: And, on a lighter note, could someone tell me about how probability is useful in Combinatorics?... I'm a newbie, so I don't know...

Answer 1

Observe that

$$(r+k)\binom{r+k-1}{r-1}=\frac{(r+k)!}{(k!)(r-1)!}\cdot \color{blue}{\frac{r}{r}}=\underbrace{r\binom{r+k}{k}=r\binom{r+k}{r}}_{\binom{a}{b}=\binom{a}{a-b}}.$$ Thus $$r\binom{r-1}{r-1}+(r+1)\binom{r}{r-1}+\dotsb+n\binom{n-1}{r-1}=r\sum_{k=0}^{n-r}\binom{r+k}{r}$$

Now use the Hockey-stick identity to get $$r\sum_{k=0}^{n-r}\binom{r+k}{r}=\color{red}{r\binom{n+1}{r+1}}.$$ So

$$H(n,r)=\frac{r\binom{n+1}{r+1}}{\binom{n}{r}}=r\left(\frac{n+1}{r+1}\right).$$

Answer 2

Nothing wrong with Anurag's answer. I just feel like describing a slightly different recursive approach. The proof will be by induction on $n$, but before we get to that part we need to build a conjecture of what the answer might be.

Consider the $r$-subsets of $\{1,2,\ldots,n\}$, so obviously $r\le n$. There are $\binom n r$ such sets. Let us split them into two subcollections according to whether the maximum, $n$, is included. There are $\binom {n-1} r$ ways of choosing $r$ numbers without including $n$, and $\binom {n-1} {r-1}$ ways of choosing $r$ numbers including $n$.

For the latter collection $n$ is always the largest. For the former collection we only know that the average of the largest is $H(n-1,r)$ – after all we are selecting $r$ numbers from $\{1,2,\ldots, n-1\}$. This gives us a recurrence formula: $$ \begin{aligned}H(r,r)&=r,\\ H(n,r)&=\frac{\binom{n-1}r H(n-1,r)+\binom{n-1}{r-1}n}{\binom n r} \end{aligned} $$ that allows us to recursively calculate all the numbers $H(n,r)$ for a fixed $r$, the starting point $H(r,r)=r$ being obvious.

Armed with this simple recursion it is easy to calculate several numerical cases, and build the conjecture that $H(n,r)=r(n+1)/(r+1)$. Proving this formula by induction on $n$ is then a banal calculation $$ \begin{aligned} H(k+1,r)&=\frac{\binom{k}r H(k,r)+\binom{k}{r-1}(k+1)}{\binom {k+1} r}\\ &=\frac{(k+1-r)H(k,r)+r(k+1)}{k+1}\\ &=(k+1-r)\frac r{r+1}+r\\ &=\frac{(k+2)r}{r+1}, \end{aligned} $$ where in the first step the common factorials of the binomial coefficients were cancelled, and the induction hypothesis was applied in the next step. Anyway, with the induction step thus completed we are done.

Not much to it:

• An advantage may be to get away without the hockey stick identity. But that identity is useful to know anyway.
• A disadvantage may be the need to first build a conjecture as to what the answer is. But this is also a useful skill in problem solving.