Part A

Can anyone explain how to show that $ n \left(\!\!\! \begin{array}{c} n-1 \\ k-1 \end{array} \!\!\!\right) $ counts the number of ways to select a subset with k elements from a set with n elements and then an element of the subset? The left hand side of the identity in the problem obviously counts this, but I can't see how they are counting the same thing.


This method has you select the element first, then form a subset containing k elements around it. Since you've already selected your element, you collect the rest of the subset by choosing k-1 from the n-1 remaining elements.

Alumni Liaison

Basic linear algebra uncovers and clarifies very important geometry and algebra.

Dr. Paul Garrett