Consider $\sum k(k-1)(k-2)$ $n\choose k$ = $n(n-1)(n-2)$ $n-3 \choose 3$ for k >= 0 n >=3

I had initially thought the right side counted the ways to select three distinct objects from n and then choose an additional three arbitrarily from the remaining objects but I was unsure on how the LHS summation fit into the picture. Does it make sense to choose distinguished objects for all k? I feel like there is another identity that ties into this, where the sum $\sum$ $n \choose k$ over all k is just the same as choosing from the largest element. Does anyone recall whether something like that exists?

  • $\begingroup$ The RHS should be $2^{n-3}n(n-1)(n-2)$. $\endgroup$ – user17762 Apr 21 '13 at 0:26
  • $\begingroup$ Unfortunately this book disagrees with you. $\endgroup$ – 114 Apr 21 '13 at 0:27
  • $\begingroup$ Then it is incorrect. $\endgroup$ – user17762 Apr 21 '13 at 0:28
  • $\begingroup$ Is it possible that there are two such identities that happen to be very similar? $\endgroup$ – 114 Apr 21 '13 at 0:29
  • $\begingroup$ @user17762 You probably mean that $2^{n-3}$ should replace the binomial coefficient on the RHS. The other factors $n(n-1)(n-2)$ should stay as they are. $\endgroup$ – Andreas Blass Apr 21 '13 at 0:29

I assume the right hand side is $2^{n-3}$ instead of $\dbinom{n}3$. Say we want to form a baseball team from $n$ people. There can be any number of people in the team. However, the team must have a captain, vice-captain and a cheer leader (The cheer leader can be of any gender and is also a part of the team). Then there are two ways to do this.

First method

First choose a captain: this can be done in $n$ ways. Next choose the vice-captain: this can be done in $n-1$ ways. Then, choose the cheer leader: this can be done in $n-2$ ways. The rest of the team from the remaining $n-3$ people can be formed in $2^{n-3}$ ways. Hence, the total number of ways is $n(n-1)(n-2) \cdot 2^{n-3}$ ways.

Second method

First choose a team with $k$ people. Now the captain can be selected in $k$ ways, the vice-captain can be selected in $k-1$ ways and the cheer leader can be selected in $k-2$ ways. Hence, the total number of ways of forming a team with $k$ people is $$\dbinom{n}k k(k-1)(k-2)$$ Now sum this over $k$ from $3$ to $n$ to get all possible teams.

Since both the methods count the same thing, they need to be equal and hence $$\sum_k \dbinom{n}k k(k-1)(k-2) = n(n-1)(n-2) \cdot 2^{n-3}$$

  • $\begingroup$ That does make perfect sense when $2^{n-3}$ replaces $n-3 \choose k$, thanks! $\endgroup$ – 114 Apr 21 '13 at 0:36

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.