I am looking for the combinatorial argument for the identity:
k(nk)=n(n−1k−1)
This is easy to show algebraically as:
(nk)=n(n−1)(n−2)(n−k+1)k(k−1)!
- What is the combinatorial argument?
- What are some general ideas to get started?
Here is a clarification of 2. From what I have seen so far, proving (combinatorially) an identity with an addition sign usually implies that we need to partition a set (this makes sense because of the addition rule and provides a nice visual). On the contrary, the previous observation leads me to believe that multiplication in identities can be resolved with the multiplication principle, but what is the "visual/interpretation" for this? Could someone provide such an interpretation for the example identity given above?
Answer
The number of ways of choosing a committee of k members from a group of n people, then selecting one of the k members to be chair, is equal to the number of ways of choosing the chair from out of the whole group of n first, then selecting the k−1 other members from among the n−1 other people.
No comments:
Post a Comment