Let $A=\{1,2,3,\cdots,n\}$. If $a_i$ is the minimum element of set $A_i$ where $A_i\subset A$ such that $n(A_i)=3$, find the sum of all $a_i$ for all possible $A_i$

Number of subsets with least element $1$ is $\binom{n-1}{2}$

Number of subsets with least element $r$ is $\binom{n-r}{2}$

Sum of all $a_r$ is $r\binom{n-r}{2}$

How do I find $$\sum_{r=1}^{n-2}r\binom{n-r}{2}$$


Two possibilities:

  1. write $r=\binom r1$ and apply a variation of the Vandermonde identity.

  2. If you add an element $0$ to your set, then $a_i$ counts the number of ways a fourth element can be chosen, less than $a_i$, and therefore less than all elements of $A_i$. One easily checks this gives a bijective correspondence with $4$-element subsets of $\{0,1,\ldots,n\}$ (in whcih $a_i$ gives the second smallest element of the subset). The number of such subsets is $\binom{n+1}4$.


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.