(New page: == Part A == Can anyone explain how to show that <math> n \left(\!\!\! \begin{array}{c} n-1 \\ k-1 \end{array} \!\!\!\right) </math> counts the number of ways to select a subset with ''k'...) |
|||
| Line 12: | Line 12: | ||
</math> | </math> | ||
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. | 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. | ||
Latest revision as of 06:59, 17 September 2008
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.
