James Tanton treats counting problems over here. He argues that we never need ask “Is order important? Is this a combination problem or a permutation problem?” He suggests that these questions merely lead to confusion, and that drawing a distinction between the two “types” in the first place is a distraction. Instead, he offers a unifying concept that allows us to treat all sorts of counting problems in the same manner, with clarity and simplicity. Just ask: “How shall I label things in this problem?”
Here is my contribution to the labeling project. For a more detailed treatment, pop over to gdaymath.com.
10 athletes are competing in the slope style event.
- Medals will be awarded to the 3 highest scorers. How many outcomes are possible with respect to this condition?
- The medals are gold, silver, and bronze. How many outcomes?
- If the organizers decided to issue 1 gold medal, 3 silver medals, and 4 bronze medals, how many outcomes would be possible?
- First observation: if one were to write out the name-space of the athletes in every possible order, one would get a giant table with 10*9*8… = 10! entries. We can count the outcomes for each of the three seemingly different scenarios above just by selecting appropriate groupings from this table.
- In the first scenario, 3 athletes will be called “medalists” and 7 will be called “participants.”
- Let’s take the first three athletes: Al, Bill, and Cal. In the name-space, we would deem ABC, ACB, BAC, BCA, CAB, and CBA “equivalent with respect to condition #1.” That is because we have simply called them “medalists.” So the total number of entries — 10! — is too large by a factor of 6. That is, with 3 names, there are 3*2*1 = 6 ways to organize them, all of which are “the same” in this scenario. So our revised estimate is 10! / 3!.
- But we haven’t gone far enough: each entry in our giant table has 10 names, and we’ve only considered how to shuffle A, B, and C about. But how many entries start ABC…? We still have those remaining 7 athletes to deal with. So we’ll have ABC | DEFGH(IJ), and then ABC | DEFGH(JI), etc. In total, there are 7*6*5… = 7! ways to shuffle the remaining athletes, and that is just for the entry that begins ABC! We can make the same observation about entries that start ACB, BAC, etc. So we would again deem all of these grouping “equal WRT condition #1,” and so we further revise our estimate to 10! / 3! / 7! — and that is in fact our final answer!
- In the second scenario, we want to call 1 athlete a “gold medalist,” 1 a “silver medalist,” 1 a “bronze medalist,” and 7 “non-medalists.” Once we choose, say, Al to be our gold medalist, there is only one way to “re-shuffle” the list of entries that start with A! We continue reasoning as above to conclude that there are now 10! / 1! / 1! / 1! / 7! outcomes.
- In the third scenario, we have 1 “gold medalist,” 3 “silver medalists,” 4 “bronze medalists,” and 2 “non-medalists.” As above, we get 10! / 1! / 3! / 4! / 2! outcomes.
Final observation: in all three cases, each of the 10 athletes is accounted for in the computation.
- 1st situation: 10! / (3! 7!), and 3+7 = 10.
- 2nd situation: 10! / (1! 1! 1! 7!), and 1+1+1+7 = 10.
- 3rd situation: 10! / (1! 3! 4! 2!), and 1+3+4+2 = 10.
So we don’t ask about “order,” we don’t bother labeling one problem as a “combination” and another as a “permutation,” we just let common sense prevail as we ask, “how should I label each of the 10 athletes to conform to the conditions of the problem?” Once we do this, the problem solves itself!