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?


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}\;.$$

  • $\begingroup$ Sorry, disregard that. $\endgroup$ – user1038665 Oct 29 '12 at 7:58
  • $\begingroup$ @user1038665: Because I made a typo; it’s fixed now. $\endgroup$ – Brian M. Scott Oct 29 '12 at 8:00
  • $\begingroup$ Can you explain how adding a lower bound may change the problem? For example, if I said that you wanted at least one of each kind? $\endgroup$ – user1038665 Oct 29 '12 at 8:14
  • $\begingroup$ Or upper bounds, so if I said you wanted at most j donuts of type $T_b$ and at most z donuts of type $T_b$ for some j,k and b = 1,...,k $\endgroup$ – user1038665 Oct 29 '12 at 8:15
  • 1
    $\begingroup$ @user1038665: In that case imagine first putting one doughnut of each kind into the order; that uses $k$ doughnuts, so you still have to add $r-k$ doughnuts to the order, and they can be of any types. Thus, it’s the old problem but with only $r-k$ doughnuts instead of $r$ doughnuts, and the answer is therefore $\binom{(r-k)+k-1}{k-1}=\binom{r-1}{k-1}$. Upper bounds are a lot nastier; see this solution to such a problem. $\endgroup$ – Brian M. Scott Oct 29 '12 at 8:18

You need to recognise that the two questions are equivalent.

If there are 3 types of doughnut (A, B and C) and you ask for 4 then the solutions are

4 0 0 
3 1 0 
3 0 1
2 2 0
2 1 1
2 0 2
1 3 0 
1 2 1
1 1 2
1 0 3 
0 4 0 
0 3 1
0 2 2
0 1 3 
0 0 4

i.e. $15 = {6 \choose 4}= {3+4-1 \choose 4}$.

You can solve this using stars and bars with $r$ stars (doughnuts) and $k-1$ bars (divisions between types).


Each assortment of donuts in (1.) is described by a $k$-tuple $(x_1,\ldots,x_k)$ of nonnegative integers with sum $r$ hence the answers to (1.) and (2.) are the same number $N_r$. To compute $N_r$, one can use (2.) and consider the series $$ \left(\sum_{x\geqslant0}t^x\right)^k=\sum_{x_1,\ldots,x_k\geqslant0}t^{x_1+\cdots+x_k}. $$ Obviously, $N_r$ is the coefficient of $t^r$ in the RHS. The LHS is $$ (1-t)^{-k}=\sum_{r\geqslant0}(-1)^r{-k\choose r}t^r, $$ hence $$ N_r=(-1)^r{-k\choose r}=(-1)^r\frac{(-k)(-k-1)\cdots(-k-r+1)}{r!}, $$ that is, $$ N_r=\frac{(k+r-1)(k+r-2)\cdots k}{r!}= {k+r-1\choose r}. $$

  • $\begingroup$ In the donuts problems, what is represented by the k-tuple? Each donut of every type? $\endgroup$ – user1038665 Oct 29 '12 at 7:49
  • $\begingroup$ The numbers of donuts of each type. $\endgroup$ – Did Oct 29 '12 at 7:51
  • $\begingroup$ @did, is this an example of generating functions? $\endgroup$ – user43081 Oct 29 '12 at 11:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.