7
$\begingroup$

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!

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ flipping is not needed. See my answer. $\endgroup$ – Henno Brandsma Feb 21 '16 at 8:41
  • $\begingroup$ "flipping" is not needed. But the flipped form certainly has more visual appeal. i spends its time between n and 1 so why not put it between n and 1? $\endgroup$ – candied_orange Feb 23 '16 at 3:36
9
$\begingroup$

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.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Can you explain further ? $\endgroup$ – user230452 Feb 21 '16 at 8:47
  • $\begingroup$ So basically what you're saying is for example we take n people or n objects and line them up and pick someone in the middle (i) and then there are i-1 choices for whatever was on the left of said object and n-i choices for whatever was on the right of said object? $\endgroup$ – King Tut Feb 21 '16 at 8:56
  • $\begingroup$ Then, doesn't $i$ go from $2&-$n-1$ ?. If $i$ is either of the end points, then only one other number can be chosen. $\endgroup$ – user230452 Feb 21 '16 at 9:07
  • 4
    $\begingroup$ We split the three person committees in disjoint sets $M_i$, which consists of all committees $a < b < c$ ($a,b,c \in \{1,\ldots,n\}$) with $b = i$. This is a partition of all committees, and so we have the sum. If we want to pick a committee in $M_i$, we are forced to take $b=i$ but we need exactly one member form $\{1,\ldots i-1\}$ and one from $\{i+1,\ldots,n\}$. Hence the product (2 independent choices). $\endgroup$ – Henno Brandsma Feb 21 '16 at 9:49
  • 2
    $\begingroup$ @HennoBrandsma Thank you so much! I understand it now! :) $\endgroup$ – King Tut Feb 21 '16 at 16:55

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.