I get obsessive about math puzzles. Not crazy ones that will take some sort of Aryabhata to figure out but little interesting ones that require intuition and a little obsession to crack. Probability and its puzzles fall right in this zone and most often, books and courses will teach people the formulae but not really instill an understanding of why things work the way they do. So… I decided to put some information down in a post. It is mostly in the form of definitions of basic concepts and clarifications of what those basics really mean.
So here goes…
Universe
This is the set of things you have available to you, to choose from. So if you have a bag with 2 red balls and 3 green balls, then those 5 balls are your universe. If you have 10 kinds of candy bars from which you can choose, say 4, that set of 10 candy bars is your universe.
Events and Outcomes
Events are something you are trying to achieve at a higher level, and outcomes are the different ways in which you can achieve that higher level objective or event.
For example if a problem asks you to choose 3 vegetables out of a bag of 10 vegetables, the event is the picking of any 3 vegetables. The outcomes that go to make that event are however many more,
10C3 = 10!/(3! * 7!) = 120
to be precise.
Similarly if you are trying to pick out 2 Aces from a pack of 52 cards, your event is exactly that, picking out of any 2 Aces, where as the outcomes that enable that event are 6 in number,
4C2 = 4!/(2! * 2!) = 6
“With Replacement” Vs. “Without Replacement”
If you have a universe of things to choose from (letters, numbers, balls, whatever…), and after you choose one of the things in the universe, you do not put it back into that universe, it’s called “Without Replacement”. If you do put it back, it’s called “With Replacement”. Another way to look at it is that you modify the universe every time you pick one thing in the “Without Replacement” case, and do reset the universe to what it was originally in the “With Replacement” case.
“Order Matters” or “Order Does not Matter”
In some problems, the order in which you extract things out of your universe is significant (think about a lottery number, the order of numbers picked is important). In some other cases, the order in which you extract things may not be important (think about the case where you need to pick 3 toys from a basket of toys – usually what order those toys will be picked out is not important).
Whether order is important or not is critical in determining how many ways (or more formally outcomes), there are to satisfy a certain event. To clarify this, lets say I have to figure out how I can extract the letters ‘A’ and ‘D’ from a universe, (‘A’, ‘B’, ‘C’, ‘D’). In other words, my event is the case where ‘A’ and ‘D’ have been extracted out from the universe. If order is important, the number of outcomes is 2 – (‘A’, ‘D’) and (‘D’, ‘A’). If order is not important, the number of outcomes is one, because we are not differentiating between the case where ‘A’ was picked first and ‘D’ last from the case where ‘D’ was picked first and ‘A’ last.
As a rule of intuition, when order is not important you have much fewer outcomes to satisfy the same event.
The Math
There really is not much math involved in this kind of problems; it’s really about understanding the question, and then imagining and categorizing the solution. Once you have done that, to save time you can just use one of the existing formulae to give you an answer and save some time.
Factorial
n! = n * (n-1) * (n-2) * … 3 * 2 * 1
Permutations
If there is no replacement, and you care about the order in which you extract items out of your universe, then the number of ways, or outcomes, you have to extract `r` items from a universe containing `n` items is represented by the expression
nPr,
and can be computed as
nPr = n!/(n-r)!
Combinations
If there is no replacement, and you do not care about the order in which you extract items out of your universe, then the number of ways, or outcomes, you have to extract `r` items from a universe containing `n` items is represented by the expression
nCr,
and can be computed as
nCr = n!/(r! * (n-r)!)
As mentioned above, intuitively it should be clear that if you don’t care about the order of extraction, you will have much fewer outcomes. And this formula confirms that intuition.
Bringing it Together
Ok, with those basics under your belt, lets try an example that brings together many of these concepts.
Question
If a menu has 10 different dishes available, and any customer is allowed to choose 4 of them, how many combinations of dishes must the chef be prepared to make, in each of the following scenarios.
- If the customer can choose a dish only once, and the order they pick the dishes in is relevant (meaning “Wonton soup, Lomein, Pot Sticklers, and General Tso’s Chicken” and “Lomein, Pot Sticklers, Genral Tso’s Chicken and Wonton Soup” are to be regarded as 2 separate combinations).
- If the customer can choose a dish only once, and the order they pick the dishes in is irrelevant (meaning “Wonton soup, Lomein, Pot Sticklers, and General Tso’s Chicken” is the same as “Lomein, Pot Sticklers, Genral Tso’s Chicken and Wonton Soup”; the order is irrelevant).
- If the customer can choose a dish multiple times, and the order they pick the dishes in is relevant (meaning “Wonton soup, Lomein, Pot Sticklers, and General Tso’s Chicken” and “Lomein, Pot Sticklers, Genral Tso’s Chicken and Wonton Soup” are to be regarded as 2 separate combinations).
- If the customer can choose a dish multiple times, and the order they pick the dishes in is irrelevant (meaning “Wonton soup, Lomein, Pot Sticklers, and General Tso’s Chicken” is the same as “Lomein, Pot Sticklers, Genral Tso’s Chicken and Wonton Soup”; the order is irrelevant).
Answer
Before getting into each case, lets look at the question as a whole. The following is a break up of what’s supplied as a part of the question:
Universe: The set of 10 dishes
Event: The picking of 4 dishes
When the customer can pick one dish only once, it’s really a way to say there is no replacement. When the customer can pick the same dish multiple times, its a way of saying that there is replacement.
Ok, now lets look at each case
- This is simply the number of permutations in which 4 things can be picked from 10.
10P4 = 10!/(10-4)! = 5040
- This is simply the number of combinations in which 4 things can be picked from 10.
10C4 = 10!/(4! * (10-4)!) = 210
- Since there is replacement here, or in other words the customer can pick the same dish one, two, three or four times, we have many more ways in which 4 dishes can be picked. Also order is relevant, meaning every different combination is valid. So the total number of ways that 4 dishes can be picked out of 10 is
10 * 10 * 10 * 10 = 10,000
Basically at every point you have the option of picking any of the 10 dishes and you have 4 of these opportunities.
- This is the most interesting of the 4 scenarios. Like in (c) you have 10 dishes to choose from all 4 times. However order is not relevant and hence those outcomes where the same things were picked have to be eliminated. Lets start with the answer we have in (c), 10,000. If from those you delete all outcomes that included a dish only once treating order as relevant (a) and then add back the outcomes that included a dish only once treating order as irrelevant (b) you get the following:
10,000 – 10P4 + 10C4 => 10,000 – 10!/6! + 10!/(4! * 6!) => 5170
However, in that total you still have the outcomes are the same (though their order of dishes is different) that included 1 repeat, 2 repeats and 3 repeats, and they need to be removed from that total. If you figure that one out, post the solution in a comment!
Here’s a bonus question, and something I will probably ask you if I ever interview you for a software engineering position. (Don’t worry, i’ll be able to figure out whether you knew it before hand 🙂 )
A spider eats at most 3 flies a day, and stops trying to catch more flies once he has eaten 3 for the day. Until he fills his quota, he has a 50% chance of catching any fly that pass by his web. What are a fly’s chances of survival, given that five 5 have passed by the spider’s web today?
Code On A Boat 