Thursday, 5 September 2013

combinatorics - Proof through combinatorial argument



I am attempting to solve this counting problem through combinatorial argument. The following is the equation I am given:



$$\sum_{i=1}^n (i-1)(n-i) = \binom{n}{3}$$




I understand that the right-hand side of this equation represents a set of $n$-elements out of which we choose 3. For example I believe we can say suppose we have a group of $n$ people and we want to choose 3 out of $n$ to be in a committee. However I'm not sure how to express the left-hand side in words. If forming a committee is an appropriate way to tackle this problem then I know the left-hand side must utilize the addition and multiplication principles, but I don't know how to put it into words. Also my intuition tells me that in solving this we should first flip $$(n-i)(i-1)$$



Thanks!


Answer



Hint: split on the fact that the middle member (in sorted numerical order, the members are numbered $1$ to $n$) is $i$. Then we pick one from before and one from after.


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...