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}$$
Answer
Two possibilities:
write $r=\binom r1$ and apply a variation of the Vandermonde identity.
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$.
No comments:
Post a Comment