# A.M of smallest elements of $r$ subsets of set 1,2,3,…,n

All possible subsets containing $$r$$ elements from the set$$\{1,2,3,...,n\}$$ are formed where $$(1\leq r\leq n)$$. What is the arithmetic mean of the smallest elements of these subsets.

My Attempt

The number of such subsets is clearly $$\binom{n}{r}$$. The number of subsets with $$k$$ as its smallest element is $$\binom{n-k}{r-1}$$. So sum of all the smallest elements$$\sum_{k=1}^{n-r+1}k\binom{n-k}{r-1}$$

=Coefficient of $$x^{r-1}$$in expansion$$\sum_{k=1}^{n-r+1}k(1+x)^{n-k}$$ =coefficient of $$x^{r-1}$$ in expansion $$\left\{\frac{(1+x)^{n+1}-(1+x)^r}{x^2}-\frac{(n-r+1)(1+x)^{r-1}}{x}\right\}=\binom{n+1}{r+1}$$

So required AM$$=\frac{n+1}{r+1}$$

Is there a combinatorical argument to this.

## 1 Answer

We count the number of $$r+1$$ element subsets of $$\{0,1,...,n\}$$. On one hand, this is $$\binom{n+1}{r+1}$$. On the other hand, for each $$1 \leq k \leq n$$, consider the number of $$r+1$$ element subsets of $$\{0,1,...,n\}$$ with second smallest element $$k$$. This can be counted by first taking a $$r$$ element subset of $$\{1,...,n\}$$ with smallest element $$k$$, then having $$k$$ ways to choose the last element from $$\{0,...,k-1\}$$. Therefore the number is equal to the sum of the smallest element of $$r$$ element subsets of $$\{1,...,n\}$$ with smallest element $$k$$. Summing over $$k$$, the sum of smallest elements of $$r$$ element subsets of $$\{1,...,n\}$$ is the number of $$r+1$$ element subsets of $$\{0,1,...,n\}$$, i.e. $$\binom{n+1}{r+1}$$. We then get the A.M. to be $$\frac{n+1}{r+1}$$ upon dividing by $$\binom{n}{r}$$.