3
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Alex Wertheim May 7 '13 at 3:18
  • $\begingroup$ 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 $\endgroup$ – user1527227 May 7 '13 at 3:20
6
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user1527227 May 7 '13 at 3:36
  • $\begingroup$ 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$ $\endgroup$ – Ross Millikan May 7 '13 at 3:43
  • $\begingroup$ 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! $\endgroup$ – user1527227 May 7 '13 at 3:47
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user1527227 May 7 '13 at 3:48

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.