1
$\begingroup$

I'm in a second year discrete mathematics course, and we have identities like this $$\binom{n}{k}(n-k) = \binom{n-1}{k}n$$ and Pascal's Triangle law.

Our professor said that algebraic proofs are fine (and I have them) but is encouraging us to learn combinatorial arguments. I have them for most the rest of the questions; however, this one is stumping me. I'm looking over my notes, and it looks most like $A_k^n$, but that hasn't really gotten my anywhere. I'm not sure how to parse the LHS and RHS into any meaningful counting argument. Any help would be much appreciated!

|cite|improve this question
$\endgroup$
2
$\begingroup$

By combinatorial argument I would understand the challenge to be proving an identity as two ways of counting the same quantity.

Sometimes a bit of lateral thinking can help to spot such an argument. The binomial $\binom{n}{k}$ is a way of counting the $k$-subsets of an $n$-set. Multiplying by $(n-k)$ is how many ways one could single out an element of the remaining $(n-k)$ items left after picking that $k$-subset.

So this is a bit like the "bonus ball" being chosen as the final draw in a lottery. The order of the first $k$ items doesn't matter; they are treated as a $k$-set. But the final ball drawn has a special significance, making it harder to earn the top prize by correctly identifying that number.

If you think of the left hand side in that fashion, it should be easy to find a similar explanation of how the right hand side represents counting the same possible outcomes in a different way. First pick (what), and then pick (the rest of the outcome)?

|cite|improve this answer
$\endgroup$
  • 3
    $\begingroup$ Oh that makes a lot of sense. Here's a stab at the RHS: A random ball is removed from the draw to be used as the bonus later, and k are drawn from the remaining (n-1) balls. Since there were n choices to remove at the start, the 'bonus ball' could be any from the original n. Also, thank you kindly I knew that the (n-k) being the leftover balls was significant but I couldn't quite put it together. $\endgroup$ – user211992 Jan 31 '15 at 17:27
  • $\begingroup$ This probably gives you an idea about proving some additional expressions are equal to these two. For example, suppose we start by picking $k+1$ balls, and then choose one of them to be the "bonus" ball? $\endgroup$ – hardmath Jan 31 '15 at 17:33
  • $\begingroup$ You would have k+1 choices for the bonus, and thus multiply the C(n,k+1) by (k+1). I tested it algebraically just to be sure and it worked out. I'm going to experiment with other possibilities as well. It's not needed for the assignment, but practice never hurts! Thanks again $\endgroup$ – user211992 Jan 31 '15 at 17:43

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.