Did you know there are 9,278,100 different types of sandwiches one can order from Subway?
Yes, I took the liberty of counting them all after a conversation a few weeks ago with a mate of mine from Melbourne, who is also coincidentally an employee of Subway (they like to call themselves ‘Sandwich artists’).
But for those who are interested, it’s basically a simple combinatoric counting problem using the sums of binomial coefficients (I’ve always wanted to say that). Once you enter a subway restaurant, you are confronted by 5 types of breads, 5 cheeses, 13 meats, 10 salads, and 12 sauces.
Before we get on to the calculations, there are some assumptions we must make: 1. You can only have one type of bread, cheese, meat, and sauce. 2. You can only have 5 types of salads or less.
Of course, you may choose to have 6 salads or two types of meat etc, but that will only make the end result even larger. I didn’t want to include whether or not you salt and pepper either. That’s just stupid 😉 If you do want to include the salt pepper factor, just multiply the end result by 4 (4 combos of salt/pepper: salt, pepper, salt and pepper, or no salt or pepper). These assumptions sound reasonable enough.
Now it’s simply: the number breads times the number of cheeses times the number of meats times number of sauces times number of salad combinations.
So it’s 5 * 5 * 13 * 12 * (number of salad combinations)
To work out the number of different salad combinations, we use a branch of mathematics known as combinatorics, and in particular, the binomial coefficient.
Since we are using only 5 or less types of salads, the total number of salad combos can be worked out as choosing 5 from 13, plus 4 from 13, plus 3 from 13, and so on (13 types of salads).
The number of ways of choosing k salads out of n is found by using the binomial coefficient ‘nCk‘:
Where k is the number of elements in the set n. In our case of 5 salads from 13, we have 13C5 which equals 1287. That is, there are 1287 different ways of choosing 5 types of salads from a total of 13.
By doing with same for k = 4, 3, 2, 1, we have the total number of different salad combinations = 13C5 + 13C4 + 13C3 + 13C2 + 13C1 which equals 2379.
Putting this back into our original sandwich equation,
5 * 5 * 13 * 12 * 2379 = 9,278,100
Or if you feel fancy about it, total number different sandwich combinations =
where b, c, m, s = number of breads, cheeses, meats, sauces respectively. n = number of salads, i, j = min, max number of salads allowed respectively.
And who said statistics has no practical purpose!?