A recurring theme in mathematics, or at least a recurring object of my own interest in mathematics, is the way that the same core idea or structure shows up in different contexts, often unexpectedly.
Consider the following three problems.
- A certain club has seventeen members, and they wish to select a five-person executive committee. How many possible committees are there?
- You are running an errand which requires you to ride your bike from your office, which is at a major intersection, to the Important Building, which is twelve blocks north and five blocks west. You ride alongside the roads, and you only turn at major intersections (between blocks); because you don’t want to waste time and energy, you are always moving either east or north (never south or west). How many different routes are possible?
- You are at your favorite doughnut shop, where they sell six types of doughnuts that you like. (Insert your flavorites here.) How many different ways are there for you to buy a dozen doughnuts you like?
These are all combinatorial problems; more specifically, they are problems of enumeration, “how many?” questions. That much is evident; what is much less evident is that all three problems have the same answer! And it is more than a coincidence.
It turns out that these problems all involve multinomial coefficients. Written , where , these represent the number of ways to divide a set of things into a set of things, a set of things, etc. Actually, we will only be needing binomial coefficients . This counts the number of ways to divide a pile of things into a pile of and a pile of . Because we often think of this as selecting and leaving the rest behind, these are usually written more briefly as , with the other bottom number being implied. (In particular, .)
There is a nice formula for these multinomial numbers which we have seen before. In the case of binomial coefficients, it is simply .
The first problem is straightforward then. We want to divide the seventeen people into the 5 who are on the committee and the 12 who aren’t. There are possibilities.
At first the second problem seems unrelated, and perhaps a bit harder. At the first step we’ll have two choices (to go east or to go north). At the second step we’ll again have two choices. But on the sixth step it stops being so simple. Maybe we’ll have two choices, but if we’ve been going east the whole time so far we’ll only have one choice. If we try to count options in this way, thinking about how many options we have at each stage, it gets awkward. The trick is to look at the trip as a whole — the trip involves 17 blocks of travel. These 17 blocks must include 5 eastward moves and 12 northward moves. So choosing a path to the Important Building is the same as choosing 5 blocks out of 17. The answer is .
The third problem is, on first glance, the most inscrutable. (The least scrutable?) It doesn’t seem related to multinomials at all. True, if I had a sack of a dozen doughnuts (five chocolate, two maple, two boston creme, one glazed, one old-fashioned, and one jelly), then would count the number of different orders I could eat the doughnuts in (if two doughnuts of the same flavor count as the same), but that’s not the question here.
Sometimes the most natural way of looking at a problem is not the most useful. Instead of thinking of a doughnut order as a number of each kind of doughnut, think of it as a series of instructions. Imagine the flavors laid out from left to right, and the doughnut-salesman at the far left edge. You place your order by saying “Gimme one of those.” (or just “gimme”) and “Next flavor.” (or just “next”). So if the flavors are alphabetized Boston Creme, chocolate, glazed, jelly, maple, old-fashioned, the order mentioned above (five chocolate, two maple, two boston creme, one glazed, one old-fashioned, and one jelly) would be delivered as “gimme-gimme-next-gimme-gimme-gimme-gimme-gimme-next-gimme-next-gimme-next-gimme-gimme-next-gimme”. So what does a valid order look like? It starts when you have no doughnuts and the salesman is at the first flavor, it ends when you have twelve doughnuts and the salesman is at the sixth flavor. So you will say 12 gimme’s and 5 next’s. If you think about it, you’ll see that every ordering of 12 gimme’s and 5 next’s is a valid order, so we are in the same situation (!) as the previous problem. It’s just a question of which 12 of the 17 words should be “gimme”, or equivalents which 5 should be “next”. There are possibilities.
Parting questions (each answerable by a little tweak on what we’ve already said):
- How many ways are there to buy a dozen doughnuts, if you insist on getting at least one of each of the six doughnuts you like?
- How many ways are there to buy doughnuts if you have enough money for a dozen, but don’t necessarily spend it all? (So you could get twelve doughnuts, or eight, or two, or none at all.)