Thursday, September 27, 2018

combinatorics - Combinatorial argument for the identity kbinomnk=nbinomn1k1


I am looking for the combinatorial argument for the identity:


k(nk)=n(n1k1)


This is easy to show algebraically as:



(nk)=n(n1)(n2)(nk+1)k(k1)!


  1. What is the combinatorial argument?

  2. 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 k1 other members from among the n1 other people.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...