Suppose that you have n objects, and you line them up. You need to pick r objects. If you take r objects from the first r objects, then you need to take 0 objects from the rest of the objects, which you have n—r. Thus, you have O(r,r)- C(n—r,0) ways of doing this.

Similarly, if you pick k objects from the first r objects, you need to take r —k objects from the rest of the objects. You have O(r, k)-C(n—r,r—k) ways of doing this.

Since you can take Q, 1, ..., r objects from the first r objects, we have that 0

ways. Thus we have proven that PSKr C(n,r)=∑ C(r,k)*C(n-r,r-k) k=0ZSK

which we needed to prove.

Similarly, if you pick k objects from the first r objects, you need to take r —k objects from the rest of the objects. You have O(r, k)-C(n—r,r—k) ways of doing this.

Since you can take Q, 1, ..., r objects from the first r objects, we have that 0

ways. Thus we have proven that PSKr C(n,r)=∑ C(r,k)*C(n-r,r-k) k=0ZSK

which we needed to prove.