Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

How Many Different Dinners Can Be Ordered?

Date: 05/25/2007 at 14:58:32
From: Dave
Subject: Arby's 5 for $5.95

I was trying to calculate the number of different meals you can get 
for the 5 for $5.95 at Arby's and wasn't confident in the way I was 
calculating it.  Given 8 different choices, how many combinations of 
5 are there?  You do not need to choose different entrées.

I am confused about the fact that you are calculating a combination 
with replacement.  I thought that I would start this way...

8 C 1 for the possibility of choosing 5 entrées alike,
2*(8 C 2) for choosing 4 alike and 1 different entrée.  Multiplied 
by 2 because there are 2 ways to assign each pair of choices.
2*(8 C 2) for choosing 3 alike and 2 alike and multiply by 2 because 
there are 2 ways to assign each pair.
(8 C 3)*(3 C 1) for choosing 2 alike, 2 alike and 1 different entrée 
and once the three are chosen, choose the one that is single.
(8 C 3)*(3 C 1) for choosing 3 alike, 1 different, 1 different.
(8 C 4)*(4 C 1) for choosing 2 alike, and 3 different entrées plus 
choosing which one is doubled up.
(8 C 5) to choose all 5 entrées different.

Then add each of the above together.  Am I on the right track?




Date: 05/25/2007 at 23:54:31
From: Doctor Wilko
Subject: Re: Arby's 5 for $5.95

Hi Dave,

Thanks for writing to Ask Dr. Math!  Yes, your approach to the problem 
looks excellent.  

I like this problem a lot.  I think it's a good real-world problem.  
We often see many restaurants and pizza parlors trying to figure out
how many different combinations of meals or pizzas they offer.  The
difficulty with these problems is that it is easy to calculate the
number of combinations incorrectly.

I'll present two solutions below to answer, "How many combinations of
5 items for $5.95 can one order from Arby's 8-item menu?"  The first
uses the same logic you applied in your work, and the second 
approaches it slightly differently.  Then I'll also show some errors
that are commonly made on this sort of problem.

Recall, we are assuming:

  - There are 8 choices on this particular menu.  
  - 5 items can be ordered (for $5.95).  
  - Duplicate items can be ordered (the 5 items don't have to be
    distinct).  

The last point is important.  There are not 8 finite items to choose
from; there are 8 choices on the menu and you can order anywhere from
0-5 of each of those items.

===========================
Method 1
===========================

For this solution, I'll try to explicitly enumerate the different ways
I can order items from the menu and then apply the combinations
formulas respectively.  Last I'll add up all the answers to get the
final answer.  

I'm basically partitioning the sample space into smaller subproblems,
solving each subproblem, and then combining the results to answer the
big problem.

1.  I can order 5 of the same item.

There is only 1 choice.  Which of the 8 should I choose? 
Mathematically, this can be written as,

  8C1 = 8.  

There are 8 ways I can choose 1 item--once I pick it, then I can order 
a quantity of 5 of that 1 item.

2.  I can order 4 of one item and 1 other item.

Here, there are only 2 choices.  Out of the 8 menu items, which 2
should I choose?  Mathematically, this can be written as,

  8C2 = 28

But out of those two choices, I need to order 4 of one and 1 of the
other.  To figure out which of the items I order 4 of, I can multiply
by 2C1 or 2.  The final answer for this portion of the problem is,

  8C2 * 2C1 = 28 * 2 = 56.

Note, at this point, you could explicitly enumerate all the ways to
order 4 of one item and 1 other item from the menu of 8 items.  You'll
see that there are 56 combinations.

If I continue with the same reasoning as above, the problem continues
as follows:

3.  3 same items, 2 other same items

  8C2 * 2C1 = 56.

4.  3 same items, 1 other item, 1 other item

  8C3 * 3C1 = 168.

5.  2 same items, 2 other same items, 1 other item

  8C3 *3C1 = 168.

6.  2 same items, 1 other item, 1 other item, 1 other item

  8C4 * 4C1 = 280.

7.  5 different items

  8C5 = 56.

Total combinations of 5 items I can order from a menu of 8 items at
Arby's is,

  8 + 56 + 56 + 168 + 168 + 280 + 56 = 792.

Apparently, Arby's boasts "Over 790 combinations!".  Arby's claim
gives me confidence in this answer.

Let's look at the problem in a different way and see if we can confirm
this answer.

===========================================
Method 2
===========================================

This solution is a little more elegant, but perhaps not as initially
intuitive as trying explicit enumeration.  I credit another one of our
volunteers, Dr. Anthony, for reminding me of this technique.

Let's label the menu items as A-H.  You are ordering from the menu
of 8 items.  You may tally up your order like this:

Item   A  *  B  *  C  *  D  *  E  *  F  *  G  *  H
---------------------------------------------------
      ||  *     *  |  *     *  |  *     *     *  |

Meaning 2 of item A, 1 of item C, 1 of item E, and 1 of item H.

There are other possibilities, too.  For instance,

Item   A  *  B  *  C  *  D  *  E  *  F  *  G  *  H
---------------------------------------------------
      ||| *     *  || *     *     *     *     *   

Meaning 3 of item A and 2 of item C.

You could do this for many different combinations, but should soon
realize that every possible order can be made by placing 5 tally marks
under the 8 items in any manner you choose.

The "leap" with this method is to now see this as a permutations
problem where you are arranging 5 bars and 7 stars, where 5 bars are
identical and the 7 stars are identical.

From probability, the permutations formula for this is,

    12!
  ------- = 792.
   5! 7!

You can also think of it as you have 12 spaces and you can choose a
place for the 5 *'s in 12C5 ways.  Likewise, you have 12 spaces and
you can choose a place for the 7 |'s in 12C7 ways.

  Note, 12C5 = 12C7 = 792.

This confirms our answer from above!

My favorite technique with combinations/permutations problems is to
find more than one way to solve the problem.  If I get confirmation
from two different approaches, I usually feel more confident in my answer!

============================
Incorrect Solutions
============================

Below are a couple of incorrect solutions and reasons why they are
incorrect.

1.  8^5 = 32,768

It seems logical at first, you have 8 choices for your first choice, 8
choices for your second choice, etc...

I was actually guilty of thinking this was the answer at first!  But
then it hit me that this is a PERMUTATIONS solution.  For instance,
you would have ABBCC and BBACC.  These are just two different
permutations of the same combination of 5 items.

In our problem, we want to buy a sack of 5 items from the 8-item menu.
Order is irrelevant in purchasing the 5 items.

==================
In general, when order matters, and objects can be chosen more than
once, the number of permutations is

  n^r (Permutations with Repetition)

where n is the number of total objects and r is the number chosen.
==================

2.  8P5 = 6,720

This assumes 8 finite, distinct items, and you want all the different
arrangements of 5 of them.  ABCDE would be a different permutation
than EDCBA.  Remember, for the problem, we want the number of possible
combinations a person could physically order from the menu.  Order
doesn't have anything to do with this.

==================
In general, when order matters, and each object can only be chosen
once, the number of permutations is

  nPr = n!/(n-r)!  (Permutations without Repetition)

where n is the number of total objects and r is the number chosen.
==================

3.  8C5 = 56

This assumes 8 finite, distinct items, and you are choosing 5 of them.
This is not representative of the problem.  This solution wouldn't let
you order 5 roast beefs, for example.

==================
In general, when order doesn't matter, and each object can only be
chosen once, the number of combinations is

  nPr = n!/[r!*(n-r)!]  (Combinations without Repetition)

where n is the number of total objects and r is the number chosen.
==================


So, finally, that leads us back to our solution, which really is a
"combinations with repetition" problem.

==================
In general, when order doesn't matter, and each object can be chosen
more than once, the number of combinations is

  nPr = (n+r-1)!/[r!*(n-1)!]  (Combinations with Repetition)

where n is the number of total objects and r is the number chosen.
==================

- Doctor Wilko, The Math Forum
  http://mathforum.org/dr.math/ 




Date: 05/30/2007 at 08:44:20
From: Dave
Subject: Thank you (Arby's 5 for $5.95)

Thank you for your solutions and comments.  I'm glad to hear that I
was on the right track.  I can't believe that I didn't think of the
partitioning method, how elegant!
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/