# Combinatorics/Probability Distribution Example Question

At a local fast-food restaurant in Oregon (no sales tax), fries, soda, hamburgers, cherry pie, and sundaes cost \$1 each. Chicken sandwiches cost \$2 each. You have five dollars. How many different meals can you order?

Let's assign two groups A and B. Let A consist of \$1 items and B consist of \$2 items.

Group A: \$1 items: Fries, soda, hamburgers, cherry pie, sundaes = 5 items Group B: \$2 items: Chicken sandwich = 1 item

I'm assuming this is a combinatorics problem which is unordered and with replacement (meaning more than one of the same item can be selected). Hence there are 3 possible scenarios because of the \$5 constraint: (I) AAAAA: Here we have 5 objects for group A's n=5 obj + 4 dividers = 9, r=5 obj (II) BAAA: Since there is only one B item here, I thought I could leave it out and only calculate the placement of 3 objects in AAA. This is because I can have only one object in B, but am free to choose the distribution among the other A's. n= 3 obj + 2 dividers = 5, r = 3 obj (III) BBA: Again since B's have only one item, and A is only 5 values, this group is simply 5. So my approach is to find the combinations of (I)-(III) and add them together: (I)$\binom{9}{5}=126$(II)$\binom{5}{3}=10$(III)$\binom{5}{1}=5$This sums to 141 but the answer is 166. Can anyone see what I am doing wrong or suggest a better method? I am using the following proposition: The number of unordered samples of r objects, with replacement from, n distinguishable objects is:$C(n+r-1,r)= \binom{n+r-1}{r}$. This is equivalent to the number of ways to distribute r indistinguishable balls into n distinguishable urns without exclusion. Thank you! • Do you have to use all five dollars? I haven't computed it, but I'd guess the remaining meals come from those totaling less than five dollars. Edit: on second thought, that might produce far too many. Maybe I'm not thinking carefully enough. – Alex Wertheim May 7 '13 at 3:18 • That's a good point. I didn't think about that. It would explain the missing numbers. Is there a faster way than going through one by one decomposing as I am doing? It seems very tedious to do it that way, @AWertheim – user1527227 May 7 '13 at 3:20 ## 2 Answers For choice II,$5 \choose 3$assumes you cannot order two of the same. For sampling with replacement, it should be${7 \choose 3}=35$by the same logic you used to get$9 \choose 5$. That increases the count to$166$• Thanks. But when you do$\binom{7}{3}$, how can you guarantee that you will not include more than one B? That is why I excluded it in my binomial coefficient. Can you please elaborate? In other words B is a special urn compared to A urns. How do you know that those 3 objects will not get placed in 2 or 3 B urns when you include 7 in your binomial coefficient? – user1527227 May 7 '13 at 3:36 • No${5+3-1 \choose 3}={7 \choose 3}$is the number of ways to choose$3$items from group A with replacement. It is the same logic as${5+5-1 \choose 5}={9 \choose 5}$is the number of ways to choose$5$items from group A with replacement. It is the statement in your box with$n=5,r=3$– Ross Millikan May 7 '13 at 3:43 • Oh. I was looking at it the wrong way. I was trying to place objects from the point of BAAA. I get it now. Thank you Ross! – user1527227 May 7 '13 at 3:47 Generating functions are helpful here. You need to find the number of solutions to the equation $$x_1 + x_2 + x_3 + x_4 + x_5 + 2x_6 \leq 5$$ where all variables are nonnegative$(x_i \geq 0)$. For example, to find the number of solutions to $$x_1 + x_2 + x_3 + x_4 + x_5 + 2x_6 = 5,$$ you should find the coefficient of$x^5$in$(1 + x = x^2 + x^3 + x^4 + x^5)^5(1 + x^2 + x^4)$(use Wolfram alpha to compute the product). You can see that the first few terms of the product are $$1 + 5x + 16x^2 + 40x^3 + 86 x^4 + 166 x^5.$$ I think that the correct answer should actually be$1 + 5 + 16 + 40 + 86 + 166 = 314$meals, and so the$166\$ corresponds only to the number of meals possible when using all five dollars.

• That's some crazy stuff. I haven't got to generating functions yet but I'll have to check it out. I'm still on chapter 1! Thanks @Javaman. – user1527227 May 7 '13 at 3:48