Show that arithmetic mean of numbers obtained is $\frac{n+1}{r+1}$

Question

Consider the smallest number in each of the $n \choose r$ subsets (of size r) of $S = \{1, 2, \ldots, n\}$. Show that the arithmetic mean of the numbers so obtained is $\frac{n+1}{r+1}$

I've tried counting the number of times every integer appears, but it seems too complicated (for me). Is there any way this can be done without induction?

Answer 1

It won't be complicated.

Let's talk about each number, first $1$.

The number of sets which have $1$ as smallest number is the same as selecting subsets of containig $r-1$ elements from the set $\{2,3 \dots n-1\}$.

Which is equal to :

$$ \binom{n-1}{r-1}$$

Similarly for number $i$ to be smallest in group of $r$ elements, all the remaining $r-$ elements must be selected from the set $\{i+1,i+2 \dots n\}$.That is :

$$ \binom{n-i}{r-1}$$

The mean of these numbers will be : $$ \displaystyle\sum_{i=1}^{n-r+1}i \cdot \binom{n-i}{r-1} \over \displaystyle\binom{n}{r}$$

Now, it can be proved by induction that : $$ \displaystyle\sum_{i=1}^{n-r+1}i \cdot \binom{n-i}{r-1}=\binom{n+1}{r+1}$$ Hence, the mean : $$ \frac{\displaystyle\sum_{i=1}^{n-r+1}i \cdot \binom{n-i}{r-1}}{\displaystyle\binom{n}{r}}=\frac{\displaystyle\binom{n+1}{r+1}}{\displaystyle\binom{n}{r}} =\frac{n+1}{r+1}$$

Answer 2

By the tail sum formula for expectation, and the hockey stick identity, $$E[X] = \sum_{k=1}^{n-r+1} P(X \ge k) = \frac{1}{\binom{n}{r}}\sum_{k=1}^{n-r+1} \binom{n-k+1}{r} = \frac{1}{\binom{n}{r}}\sum_{j=r}^n \binom{j}{r} = \frac{1}{\binom{n}{r}}\binom{n+1}{r+1} = \frac{n+1}{r+1}.$$

Answer 3

This is the problem of finding the expectation of a random $r$-element subset $A$ of $\{1,2,\ldots,n\}$ (chosen uniformly). Let the elements of $A$ be the discrete random variables $X_1<X_2<\ldots<X_r$. So our task is to find $E(X_1)$.

Introduce new random variables:

$Y_1=X_1$, $Y_2=X_2-X_1$, $Y_3=X_3-X_2,\ldots, Y_r=X_r-X_{r-1}$, $Y_{r+1} =n+1-X_r$.

These take positive integer values and $Y_1+\cdots+Y_{r+1}=n+1$. Each sequence of integers which fulfils these conditions corresponds to a unique set $A$. Therefore each such sequence occurs with the same probability. These conditions are symmetric in $1,\ldots,r+1$ so the $Y_i$ all have the same distribution. In particular $E(Y_1)=E(Y_2)=\cdots=E(Y_{r+1})$. So $$(r+1)E(Y_1)=E(Y_1+Y_2+\cdots+Y_{r+1})=E(n+1)=n+1.$$ Therefore $$E(X_1)=E(Y_1)=\frac{n+1}{r+1}.$$

As a bonus, the expectation of the $k$-th smallest element of $A$ is $$E(X_k)=E(Y_1+\cdots+Y_k)=E(Y_1)+\cdots+E(Y_k) =kE(Y_1)=k\frac{n+1}{r+1}.$$