Sunday, June 10, 2018

combinatorics - Proof through combinatorial argument



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



ni=1(i1)(ni)=(n3)




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 (ni)(i1)



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

analysis - Injection, making bijection

I have injection f:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...