Stars and Bars partitioning argument

238 Views Asked by At

The stars and bars formula states that if your order $h$ hats from a store that sells $k$ kind of hats, then there are ${K+h-1\choose K}$ possibilities of hats that you order. Assuming $h>k$ use a partitioning argument to show that this quantity is equal to $\sum_{r=1}^k{k\choose r}{h+r-1\choose r-1}$.