Math Problem

July 3, 2007 8:05 PM

Arby's is better at math than me...

Arby's has this deal out now: 5 for $5.95. You can pick from 8 choices to fill 5 spots. What is the equation to figure out how many choices you have? I cannot figure out how to compensate for the fact that the order of the choices does not matter, as in 1 hot cake and 4 cokes is the same choice as 4 cokes and 1 hot cake. So there are many, many duplicate choices if you do the simple 8 to the 5th power calc.

The menu says "over 790 possible combinations," so I'm fairly sure the number is between 790-800.

posted by jjbb to Education (28 answers total)

Combinatorics. And they say you never use math after you graduate..
posted by kcm at 8:10 PM on July 3, 2007

Ok, I had a rather long explanation here, only to realised it was wrong. Let me go look at a text book and get back to ya.
posted by cholly at 8:14 PM on July 3, 2007

What you're looking for is the multiset coefficient <8 , 5>, which is equal to 792. (Definition is about halfway down that page.)
posted by equalpants at 8:14 PM on July 3, 2007

It's 8!/(5!*(8-5)! if you're not permitted duplicates.

If duplicates are permitted it's (5^8)/(5!).
posted by Steven C. Den Beste at 8:16 PM on July 3, 2007

Would Arby's say that an order consisting of onion rings, pepsi, pepsi, pepsi, pepsi is the same thing as pepsi, pepsi, pepsi, pepsi, onion rings, or are they treating them as two different combinations?
posted by iconomy at 8:23 PM on July 3, 2007

And surely, by accepting the individual variations between individual products, they could rightly claim that an infinite number of combinations are possible with pepsi alone.

I dare say over 790 sounds more, at a glance, than 792.
posted by oxford blue at 8:30 PM on July 3, 2007

Can someone explain the multiset coefficient math. I keep getting 56 using the equations.
posted by jjbb at 8:44 PM on July 3, 2007

equalpants has it.

Steven C. Den Beste, it would be 8!/(5!*(8-5)!) = 56, as you say, if duplicates were not allowed. But, (5^8)/(5!) is not even an integer, nor is (8^5)/(5!), which is what I think you had in mind.
posted by epimorph at 8:44 PM on July 3, 2007

Do they factor in all flavors of soda?
posted by Mach3avelli at 8:45 PM on July 3, 2007

One way to picture this is to imagine that you have 5 coins and 7 pencils that you want to lay out in a row: the coins represent the spots, and the pencils represent the boundaries between the different products. So, for example, you have 2 coins, then 6 pencils, then 3 coins, then the last pencil, that's 2 of product #1, none of products #2-6, one of product #7, and none of product #8.

There are 12 pencils + coins, so there are 12! ways to lay them all out. However, the 5 coins are indistinguishable, so the order in which they're chosen relative to each other doesn't matter, so we divide by 5!. Similarly, we divide by 7! to remove the pencil duplicates. The grand total is 12! / (5! * 7!) = 792.
posted by equalpants at 8:46 PM on July 3, 2007

where does the 7 come from? If the pencils represent boundaries, wouldn't there only be 6?
posted by jjbb at 8:51 PM on July 3, 2007

The 7 comes from the number of products, minus 1. Suppose your table is divided into 8 regions (all in a row), one for each product, and you're making your choices by placing your 5 coins into the regions. Now, having placed the coins, place a pencil along each of the borders between regions (7 pencils). The idea is that you didn't need the regions in the first place; you could've just laid the pencils out at the same time as the coins.
posted by equalpants at 8:57 PM on July 3, 2007

So, for example, you have 2 coins, then 6 pencils, then 3 coins, then the last pencil, that's 2 of product #1, none of products #2-6, one of product #7, and none of product #8.

Could someone explain this in another way? I'm not understanding it...Intuitively, 5^8 seems to be the answer to me..
posted by sk381 at 9:50 PM on July 3, 2007

..er.. I mean 8^5..which, apparently, is also wrong..
posted by sk381 at 9:58 PM on July 3, 2007

sk381, the problem is overcounting.

coke, coke, coke, burger, burger
...and...
burger, burger, coke, coke, coke

are different counts in 8^5 but they are actually the same. The raw calculation 8^5 contains a lot of duplication. My feeble attempt at solving that was to divide it by 5!, but that's wrong, too.
posted by Steven C. Den Beste at 10:58 PM on July 3, 2007

The raw calculation 8^5 contains a lot of duplication. My feeble attempt at solving that was to divide it by 5!, but that's wrong, too.

It's because you don't know up front how much duplication there's going to be. There could be five unique items with 5! ways of arranging them, or five of the same item with only one way of arranging them. So, dividing by 5! overcompensates for the different arrangements in the cases where you have duplicate items.

I like equalpants's explanation. It took me a moment to see what they were getting at, but yeah. I'm remembering that one.
posted by Many bubbles at 11:09 PM on July 3, 2007

Basically, we want to reduce this problem to an easier one. So let's say you have some number of balls. You throw these balls at 8 different boxes, which represent each menu item. If the ball lands in the first box, you buy the first thing on the menu, for the second box, you buy the second thing, and so forth. Then you throw another ball, and another, until you run out. Since you get 5 total choices, you get 5 balls to throw. Hopefully you can see that there are the same number of possibilities in this scenario as are in the original problem.

So let's represent this with a string of ASCII characters:

|xxxxx|xxxxx|xxxxx|xxxxx|xxxxx|xxxxx|xxxxx|xxxxx|

You can see the eight bins, each holding up to 5 possible balls. Let's throw some balls in there and see what happens.

|OOxxx|xxxxx|Oxxxx|xxxxx|xxxxx|xxxxx|OOxxx|xxxxx|

Here we've thrown two balls into bin 1, one into bin 3, and two into bin 7 — in other words, bought two #1 meals, one #3 meal, and two #7 meals. But in order to actually count these possibilities, we need a better representation. There's a lot of redundancy. If you naively count the possible strings of x's and O's ((5*8)²), there are a lot of duplicates:

|xxOOx|xxxxx|xxxxO|xxxxx|xxxxx|xxxxx|OxxOx|xxxxx|

And even totally nonsensical results, with way too many balls:

|xxOOx|xxOOx|xxxxO|xOOOO|xOOOx|xxxxx|OOxOx|xxxxx|

So let's try something. Let's try removing all the x's — the "empty spaces" — from our string. Here's our result in that form:

|OO||O||||OO||

Now each character can be either a ball or a "barrier" between the boxes. Notice that as long as you have the same number of balls and barriers, you can move them around as much as you want and still end up with a valid result. Well, almost:

OOO|||||||||OO

Hmm, we missed the boxes completely! There's one more bit of redundancy left: every valid string has one "barrier" at each end. So let's remove them. Our result now becomes:

OO||O||||OO|

And now every permutation of these characters is a valid result. The problem is now exactly like "how many distinct words can be formed by rearranging the letters in MISSISSIPPI?" First we count all the possible words; since the string is 5 (balls) + 7 (barriers) = 13 characters long, there are 13! possible permutations of it. Now we have to account for any times we over-counted. So let's take an example string — our result — and see how many times we actually count it. Let's number the O's, since they're being counted as distinct:

O1O2||O3||||O4O5|
O1O3||O4||||O2O5|
O5O2||O3||||O1O4|
...

As you can see, for every possible permutation of the 5 balls, we count our result again. And it's the same for any string, not just the example we picked. So to eliminate these possibilities, we divide our total count by the number of ways to permute 5 balls, or 5!. We can go through a similar process for the barriers to find that we must divide again by 7!.

So that's how you get the answer, 13!/7!5! = 792. Counting is hard!
posted by panic at 1:23 AM on July 4, 2007

Wow, I can't add. 7+5 is, in fact, 12. Which is why the answer is 12!/7!5! = 792.
posted by panic at 1:26 AM on July 4, 2007

equalpants just taught it the same way I do, except I use a cash register drawer rather than pencils.
Incidentally, don't let the pizza guys fool you. There are 2^n ways to get a pizza from a pool of n different toppings. Start including things like "double pepperoni" and they can make the numbers huge. This kind of math in advertising is like a padded bra. It may get you into the store but you'll be disapointed by how little is actually there.
posted by monkeymadness at 4:35 AM on July 4, 2007

I just want to say good timing for this. A friend just went through the xkcd archives and was trying to figure out this graph, and this is nearly the same problem. So yay for everyone who reexplained it.
posted by cobaltnine at 8:22 AM on July 4, 2007

OK I'm finding this really interesting but I'm far removed from my left-brained taxing days of math. Can someone explain the "!" principle to me again? My google-fu isn't finding a simple definition, and when I plug any integer (i.e. 2!) into google's calculator, it gives me that integer as the value.

panic's formula 12!/7!5! = 792 doesn't make sense? Could someone break it down for me?
posted by allkindsoftime at 9:31 AM on July 5, 2007

Google-fu came through after all. So If I follow the math right, its:

12! = 12*11*10*9*8*7*6*5*4*3*2*1 = 479001600

7! = 7*6*5*4*3*2*1 = 5040

5! = 5*4*3*2*1 = 120

Hence,

479001600 / (5040*120) = 792

right?
posted by allkindsoftime at 9:41 AM on July 5, 2007

I liked the example from the wiki page of the number of five-card hands possible from a standard fifty-two card deck:

n! / k!(n-k)!

Where n = 52 (cards in deck), and k=5 (five card hands).

52! / 5!(52-5)! = 2598960

Makes sense. What I'm not getting is why the same math doesn't work for our 8 menu items (n) and 5 possible choices (k).

8! / 5!(8-5)! = 56, by my math.

Am I applying the wrong math to the problem or something?
posted by allkindsoftime at 10:03 AM on July 5, 2007

Yes, your understanding of ! is right, although normally you'd cancel out a bit (if you don't have a ! function on your calculator):
(12*11*10*9*8*7*6*5*4*3*2*1)/(7*6*5*4*3*2*1) = (12*11*10*9*8)

(12*11*10*9*8)/(5*4*3*2*1) = (11*9*8) = 792

Yes, you're applying the wrong math to the problem. With the deck of cards, every card is distinct. A hand with A-5, all hearts, isn't the same as a hand with A-4, all hearts, plus the five of clubs. There are no true duplicates.

With the menu, there are true duplicates, as you can get two or more of the exact same item. That's why math is different.
posted by Many bubbles at 11:52 AM on July 5, 2007

If you allow the Soda to be changed and they have 6 types of drink. ..I can't do this math.
posted by Megafly at 12:24 PM on July 5, 2007

thanks bubbles.
posted by allkindsoftime at 1:40 PM on July 5, 2007

If you allow the Soda to be changed and they have 6 types of drink. ..I can't do this math.

This is essentially just adding more products. Before, there were 7 plus "soda", now there are 7 plus "coke", "sprite", etc., for a total of 13 products. You can just use the same formula as before (P = number of products, S = number of slots):

(P + S - 1)! / S!*(P - 1)!

17! / 5!*12! = 6188
posted by equalpants at 2:31 PM on July 5, 2007

For future reference, here is a good explanation of combinations and permutations, easier to read than the Wikipedia article. And here is an online calculator for permutations and combinations.
posted by euphotic at 12:05 AM on July 21, 2007