The combinatorial proof is to prove that
n∑k=1k⋅(nk)=n⋅2n−1
The solution says to count the leader and committee in two ways.
The first way you choose the leader in n diff ways. Then choose the rest of the committee in 2n−1 ways to get the second side of the equation.
The second way you choose a committee with k people in (nk) ways, and then there are k ways to choose its leader.
So this is suppose to give you the left side of the equation
n∑k=1k⋅(nk)=n⋅2n−1
What I'm not understanding is why in the second part, you use a Riemann's sum to add all the ways. Because if you're just choosing k people, I'm not sure why the k value has to increase.
Thanks.
No comments:
Post a Comment