5
$\begingroup$

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...

$\endgroup$
4
$\begingroup$

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).$$

$\endgroup$
  • 1
    $\begingroup$ Thanks sir! Just what I needed!!! $\endgroup$ – Sen47 Jul 25 at 8:52
  • $\begingroup$ so r=1 or r=n as that's when the numerator would be the answer ... $\endgroup$ – Roddy MacPhee Jul 25 at 20:00
  • $\begingroup$ @RoddyMacPhee for both cases $r=1,n$ the same expression holds. Because for $r=1$, you have $n$ sets $\{k\}$ and in each set $k$ itself is the largest element so the mean of those will be $\frac{1+2+\dotsb+n}{n}=\frac{n+1}{2}$. The expression I gave also gives the same answer with $r=1$. Likewise you can check with $r=n$, there is only one set namely, $[n]$ and the largest element is $n$, so the mean is $\frac{n}{1}=n$ which is the same as $H(n,n)=n$. $\endgroup$ – Anurag A Jul 25 at 20:04
  • 2
    $\begingroup$ Why a downvote? Just arbitrarily assigning a down vote is of no value. If there is an error then by all means point it out and then down vote. But having the down vote with no rhyme and reason is not helpful for either OP or me. $\endgroup$ – Anurag A Jul 25 at 20:05
1
$\begingroup$

Nothing wrong with Anurag's answer. I just feel like pointing out 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 cuonjecture 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.
$\endgroup$
  • $\begingroup$ Thank you sir for this insight. I have been trying to improve my recursion skills. This will help tons! Upvoted! $\endgroup$ – Sen47 Jul 26 at 9:53

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.