1) There are k types of doughnuts on sale, and at least r of each type are available. You ask for r doughnuts, but you don’t specify how many of each type you want. In how many different ways can the baker fill your order? (Two ways are different if they differ in the number of doughnuts of some type.)
Why wouldn't the answer be $k+r \choose r$ instead of $k+r-1 \choose r$? If there are 3 types of donuts, and 4 of each type (12 total), doesn't the baker have $12 \choose 3$ options?
2) How many solutions in non-negative integers are there to the equation $x_1+…+x_k=r$?
I'm not sure how to think about this one. I know the solution can be written in the $k+r-1 \choose r$ form, but why? More specifically, how can this problem be seen as a "stars and bars" problem?
Best Answer
The first thing to realize is that the two problems are the same: each way of filling the doughnut order corresponds to a unique solution of $x_1+\ldots+k_k=r$ in non-negative integers, and each such solution corresponds to a unique way of filling the doughnut order. Specifically, if the doughnuts are of types $T_1,\dots,T_k$, and for $i=1,\dots,k$ we let $x_i$ be the number of doughnuts of type $T_i$ that you get, then the numbers $x_i$ are certainly non-negative integers, and they satisfy the equation $x_1+\ldots+x_k=r$. Conversely, if $x_1,\dots,x_k$ are non-negative integers whose sum is $r$, we can make up the doughnut order with $x_1$ doughnuts of type $T_1$, $x_2$ of type $T_2$, and so on.
Imagine that you lay out the doughnuts in an order in a line, first all those of type $T_1$, then all those of type $T_2$, and so on. To make sure that you keep the types straight, you put atoothpicks between the types. For instance, if $k=4$ and $r=10$, you might have $3$ doughnuts of type $T_1$, $2$ of type $T_2$, and $5$ of type $T_3$, and your string of doughnuts would look like this:
OOO|OO|OOOOO. You might have no doughnuts of type $T_1$, $4$ of type $T_2$, and $6$ of type $T_3$:|OOOO|OOOOOO. Or you might have $2$ doughnuts of type $T_1$, none of type $T_2$, and $8$ of type $T_3$:OO||OOOOOOOO. Every such string will contain $10$ doughnuts and $2$ toothpicks. More generally, if you have $k$ types of doughnuts and $r$ doughnuts altogether, each string will contain $r$ doughnuts and $k-1$ toothpicks, because there are only $k-1$ division points between adjacent types.Every doughnut order corresponds to one of these strings, and every string of $r$ doughnuts and $k-1$ toothpicks corresponds to a possible doughnut order, so to count the possible doughnut orders (and hence also the solutions in non-negative integers to the equation $x_1+\ldots+x_k=r$) we need only count the possible strings of $r$ doughnuts and $k-1$ toothpicks. Each is a string of $r+k-1$ objects. Once we know where the $r$ doughnuts go in the string, the $k-1$ toothpicks must occupy the other $k-1$ positions. There are $\binom{r+k-1}r$ ways to choose $r$ of the $r+k-1$ positions to be occupied by the $r$ doughnuts, so the number of possible strings is $\binom{r+k-1}r$. Alternatively, there are $\binom{r+k-1}{k-1}$ ways to choose $k-1$ positions for the toothpicks, after which the doughnuts will automaticall occupy the other $r$ positions, so there are $\binom{r+k-1}{k-1}$ possible strings. (Of course we know that $$\binom{r+k-1}r=\binom{r+k-1}{k-1}\;,$$ so there’s no conflict here.)
We’ve already seen that there are exactly as many strings of doughnuts and toothpicks as there are possible doughnut orders, and exactly as many doughnut orders as there are solutions in non-negative integers to the equation $x_1+\ldots+x_k=r$, so the answer to both problems is $$\binom{r+k-1}r=\binom{r+k-1}{k-1}\;.$$