“If you have arugula, basil, celery, dandelion, and endive leaves, how many different tossed salads can you make?” That question, or something like it, was asked in a Math Bowl that I participated in back in high school, during my halcyon days as a mathlete.1 Actually, “halcyon days” are supposed to be calm days, and quiz-show-style math-smackdowns aren’t known for being calm. It was certainly an un-halcyon moment when my Math Bowl teammates were urgently saying we should buzz in with the answer 32 to that salad question, and I was saying we needed to figure out whether the judges would think that a bowl containing no ingredients at all was a valid salad. While we were debating the issue, the other team buzzed in with the answer 32, only to be told “That is incorrect.” Our team immediately buzzed in with the answer 31, which seemed likely to be the answer the judges were looking for.
We got the points, but I liked the other team’s answer better. The idea of an empty salad might seem like a purely mathematical fancy, but half a dozen years later I saw a restaurant menu that offered the null salad, or rather “Nowt, served with a subtle hint of sod all” (for the unbeatable price of 0 pounds and 0 pence).2
Cartoon by Ben Orlin. Follow him on Twitter @benorlin! Read his blog at https://mathwithbaddrawings.com! Buy his books from your local independent bookseller!
Today I’ll tell you how to make null salad — not just the tossed kind, but also the kind that’s artfully composed of stacked leafy greens, except that there aren’t any greens in the stack. The trick to preparing it is knowing when to stop, namely, before you start, and the hardest part of all isn’t doing it, but correctly counting how many ways there are to do it. You might think the correct count is 0, but it’s not. Coming to understand why the answer isn’t 0 is tricky; it hinges on understanding the difference between a task that’s impossible to do and a task that’s impossible to start because it’s already finished.3 Or, putting it differently, it’s about the difference between doing the impossible and doing nothing. There are exactly 0 ways to do the impossible, but in many mathematical settings, there’s exactly 1 way to do nothing.
COUNTING TOSSED SALADS
Of course the original problem is a bit silly, since it assumes that a salad that’s 90% arugula and 10% basil is the same as a salad that’s 10% arugula and 90% basil (but if we didn’t make that assumption, there’d be too many different salads to count and no clear rules for counting them). The problem also ignores the fact that some combinations of greens might not be palatable (but if we didn’t make that assumption, once again there’d be no clear rules for counting the possibilities).
The inclusion of the word “tossed” might seem incidental, but it actually serves an important mathematical role; it tells us that the ingredients are mixed together higgledy-piggledy, so that their arrangement within the bowl isn’t what we’re interested in. All that we’re supposed to care about is which ingredients get used (no matter how little) and which ingredients get left out.
Let’s stick to just arugula and basil for a bit. We have a choice about whether to include arugula or not, and we have a choice about whether to include basil or not. If we disallow the empty salad, then these choices are linked, because deciding to omit arugula would force us to include basil (and deciding to omit basil would force us to include arugula). But if we allow the empty salad, then the choices can be made independently of each other. For each of the two possible ways of deciding about arugula (arugula or no arugula?), we get two possible ways of deciding about basil (basil or no basil?). So the situation becomes symmetrical with regard to inclusion versus exclusion: there are exactly as many salads that include arugula as there are salads that exclude arugula, and ditto for basil. And that’s a good thing, because by and large symmetrical definitions are easier to work with.
Once we’ve decided that it’s expedient to include the empty salad, we find that there are 4 different salads that can be made with arugula and basil as allowed ingredients: arugula-and-basil, arugula-only, basil-only, and the empty salad.
What happens when we include celery as an allowed ingredient? Each of the 4 salads that can be made with arugula and basil as allowed ingredients gives rise to 2 different salads according to whether we use celery or not; so there are twice 4, or 8, salads that can be made with arugula, basil, and celery as allowed ingredients.
I think you see where this is going: when we add a fourth allowed ingredient (dandelion), the number of possibilities becomes twice 8, or 16, and when we add a fifth allowed ingredient (endive), the number of possibilities becomes twice 16, or 32. Thinking about this pattern, we see that the number of different salads we can make with n allowed ingredients is 2 times 2 times 2 times … times 2, where the number of 2’s is n. We write this number as 2n for short.
In contrast, if we’d chosen to disallow the empty salad, we would have gotten the messier answer 2n−1.
BACK TO ZERO
Let’s pause and look at the expression 2n for a bit. It’s defined as the product 2 × 2 × 2 × … × 2, where the number of 2’s is n and the number of multiplication signs is n−1. This makes sense when n is bigger than 1, and it even makes sense, sort of, when n is 1: the number of 2’s is 1 and the number of multiplication signs is 0, so our “product” looks like just “2”, whose value is clearly 2 (even though “2” by itself isn’t a product in the ordinary sense).
But what if n is 0? Once upon a time, when nobody had yet defined 20, mathematicians had to make up their collective mind about what they wanted it to mean. They could have left it undefined, because it makes no sense to speak about a product of 2’s in which the number of 2’s is 0 and the number of multiplication signs is −1. But it became clear pretty quickly that there are contexts in which it’s useful to define 20 to be 1 (and few or no contexts in which it’s useful to define 20 to be some other value). One good feature of filling in the blank in “__, 2, 4, 8, 16, 32, …” with a 1 is that the resulting sequence 1, 2, 4, 8, 16, 32, … follows a uniform rule: each term is twice the term before (or, going backwards, each term is half of the term that follows).
For the practical-minded, here’s a financial application. Consider a bank that gives interest at the (unrealistic but simple-to-discuss) rate of 100% compounded annually. After n years, where n is any positive integer you like, an initial deposit of $100 will become $100 times 2n. What’s the situation after 0 years? If “after 0 years” means “right after you’ve deposited your money”, then you have $100 in your account and not a penny more or a penny less, so it makes sense that 20 should be taken to equal 1.
The permissive notion of salads that goes hand-in-hand with the conventional definition 20 = 1 gives us a new way to see the null salad shining on its own, and not suffering from invidious comparisons with its more filling fellow-salads: if there are 0 ingredients to choose from, then we can make exactly 1 tossed salad from them, namely the null salad.
COUNTING LAYERED SALADS
What if we have salads in which structure matters? Let’s throw culinary realism to the winds here and consider salads that contain a single arugula leaf, a single basil leaf, a single celery leaf, a single dandelion leaf, and a single endive leaf. (Never mind that a true composed salad should have a base, a body, and a garnish.) How many such salads are there? More generally, if there are n different kinds of leaf, how many ways are there to build a salad by stacking together one leaf of each kind? (Yes, I know, if you stack actual leaves they won’t stay stacked. But this is math, not cuisine.)
When n is 1, there’s only 1 way to go.
When n is 2, there are 2 choices of which leaf to put on the bottom, and then we’re forced to put the other leaf on the top, so there are 2 possible salads.
When n is 3, there are 3 choices of which leaf to put on the bottom, and then 2 remaining choices for what to put on top of that, and then only 1 remaining option for what to put on the top, so the total number of possibilities is 3 × 2 × 1 = 6.
Again, I think you see where this going: when n is 4, the total number of possibilities is 4 × 3 × 2 × 1 = 24, and when n is 5, the total number of possibilities is 5 × 4 × 3 × 2 × 1 = 120.
We have the symbol “n!” (pronounced “n factorial”) for the product of the counting numbers from 1 through n. So now we are ready to ask the question, how should 0! be defined?
Looking at the sequence __, 1, 2, 6, 24, 120, … in reverse, we see that starting from 120, we first divide by 5 (obtaining 24), then divide by 4 (obtaining 6), then divide by 3 (obtaining 2), then divide by 2 (obtaining 1). So if we want the pattern of divisions to continue, we should next divide by 1 (obtaining 1). By this reasoning, the right value for 0! is 1.
If you prefer a more practical reason for the convention 0! = 1, consider tossing a fair coin n times in some gambling game. What’s the probability of getting heads a times and tails b times? The binomial formula 
gives the right answer when a and b are both positive integers (let me know in the Comments if you know a well-written online reference for this formula that explains why it’s true!). It’s not important to understand where the formula comes from; what I want you to notice is that if you want it to give the right answer when a=0 or b=0, you’d better take 0! = 1. (If you take 0! = 0 then the expression has a 0 in the denominator and hence makes no sense; if you take 0! to be any nonzero number other than 1, the expression makes sense but gives the wrong answer; if you take 0! to be 1, you get the right answer.)
For those who prefer computer science to probability, the number of ways to form a bit-string consisting of a 0’s and b 1’s is
(Example: When a = b = 2, the expression evaluates to 24 / 4 = 6, and the 6 bit-strings consisting of two 0’s and two 1’s are the binary words 0011, 0101, 0110, 1001, 1010, and 1100. If you know a good online proof, I’d love to include a link to it.) In the case where a is positive and b is zero, you can check that the number of such bit-strings is 1, and that the above expression takes the value 1 only if 0! is defined to be 1.
It’s fun to contemplate the case where a and b are both 0. For people who study probability, this corresponds to a gambling game in which, just before you make your first toss, you remember what your parents told you about gambling, suddenly “need to use the bathroom”, and sneak out the back. If you do this, you’re 100% certain to toss 0 heads and 0 tails, so the probability of that event is 1. For computer scientists, a=b=0 corresponds to the bit-string consisting of no bits at all, often written as λ instead of as .4 The bit-string λ has length 0, but it’s a mathematical entity, and there’s 1 of it.
So now we can ask: are there 0! layered salads with 0 ingredients? One way to define a layered salad (in the somewhat strange way I’m using the term) is a collection of edible leaves such that (a) each type of leaf that occurs must occur only once, and (b) any two leaves that occur must occur in some definite order. In a persnickety mathematical sense, the empty salad satisfies both conditions vacuously, because (a) you can’t show me a leaf that occurs more than once, and (b) you can’t show me two leaves that don’t occur in some definite order. Therefore, there’s 1 (i.e., 0!) layered salad with 0 ingredients.
So if your fridge is empty, and you’re tired of tossed salad with 0 ingredients, you can vary your diet by having a layered salad with 0 ingredients instead.
THE TILING THAT HAS NO TILES AND THE PATH THAT HAS NO STEPS
Here’s another application of the one-way-to-do-nothing principle. How many ways are there to tile a 2-by-0 rectangle with identical 2-by-1 tiles? We’ll overcome our initial stupor vacui5 by broadening the question, replacing 0 by an unknown positive integer n; then, once we’ve seen what the governing pattern is, we’ll sneak up on 0 by counting backward from the positive integers, and then we’ll notice that the paradoxical answer we obtain actually makes a persnickety kind of sense.
The number of ways to tile a 2-by-1 rectangle with 2-by-1 tiles is 1:
The number of ways to tile a 2-by-2 rectangle with 2-by-1 tiles is 2:
The number of ways to tile a 2-by-3 rectangle with 2-by-1 tiles is 3:
The number of ways to tile a 2-by-4 rectangle with 2-by-1 tiles is 5:
Mathematician/dad/videographer Mike Lawler helped his child study this problem. For general values of n the answer is given by the Fibonacci sequence 1,2,3,5,8,13,…
Once you’ve understood why each term is equal to the sum of the two preceding terms (see Mike’s follow-up post on this topic, featuring both kids this time), you can turn the pattern around and say that each term is equal to the difference between the two succeeding terms. More precisely, the nth term in the sequence is equal to the n+2nd term minus the n+1st term. If we apply that formula in the case n=0, we see that the number of tilings of the 2-by-0 rectangle “should” be the number of tilings of the 2-by-2 rectangle minus the number of tilings of the 2-by-1 rectangle, which gives us 2 minus 1, or 1.
That is, the pattern suggests that there’s exactly 1 way to tile a 2-by-0 rectangle with 2-by-1 tiles, and if you think about it, that’s exactly right. The way to tile a 2-by-0 rectangle with 2-by-1 tiles is to say “There’s room for exactly 0 tiles, so I’m done” and then fold your arms. Or as Mike’s son puts it: the way to do it is not to do anything. And there’s exactly one way to do that.
As important in modern combinatorics as the Fibonacci numbers are the Catalan numbers 1,2,5,14,42,… (discussed in a video listed in the References). One thing Catalan numbers count is paths in a grid that stay in a triangle. For instance, 42 (the 5th Catalan number) counts the paths in the picture below that join the point A = (0,0) to the point B = (5,5) consisting of 10 steps that stay within the triangle bounded by dashed lines.
The red path shown is one of 42 grid-paths of length 10 from A to B staying within the dashed lines.
The nth Catalan number is equal to the number of paths from (0,0) to (n,n) consisting of 2n steps that stay within the triangle bounded by (0,0), (n,0), and (n,n). A formula for the nth Catalan number is
Plugging in n=0, we get the answer 1. This counts the number of paths from (0,0) to (0,0) consisting of 0 steps that stay within the triangle bounded by (0,0), (0,0), and (0,0). The three vertices of this triangle are the exact same point, so this region gives you no room to move; but since we’re looking at paths of length 0 within that region, there’s no need to move. Your journey is over as soon as it’s started.
MATH MINDFULLNESS
I’ve come about as close to talking about the null set as one can without actually talking about it. I’ll write about the null set some other time; in the meantime, you can read Evelyn Lamb’s fun essay on the topic, which will give you some insight into the body of mathematical work Ben Orlin is riffing on in his cartoon back at the beginning of this piece where he describes the null salad as “the basis of all salads” in the set-theoretic sense.
The null salad (tossed or layered), the empty binary word λ, the tiling with no tiles and the path with no steps inhabit the no-man’s-land between Nothingness and Somethingness, and in discussing them I’m trespassing onto territory claimed by mystics. So I’ll close by proposing, with tongue firmly in cheek, a mathematico-mystical morning meditation practice that will help novices come to deeply understand the mathematics of Doing By Not-Doing.
Your ritual is to prepare and consume null salad. Choose your ingredients, which you need not have on hand; lack of ingredients does not matter, since the recipe requires none of them. Perhaps your choice today is a simple null fruit salad, consisting of 0 apples. After preparing your salad, perform arithmetic operations on your salad that in no way mar its perfect null-ness. For instance, add 0 apples to your salad. Then subtract 0 apples. Then double your portion. Then halve it. It may seem impossible to cut your apple salad in half because there are no apples to cut nor any knife in hand to cut them with, but that does not make the task impossible; indeed, as soon as the task comes into your mind, the task is already completed.
As you carry out these operations, including the final step of consuming the salad in zero mouthfuls, repeat in your mind the mantra λ, The Empty Word, whose meaning is: “There is nothing to be done, and I have already done it.”
Feel enlightened?
Good. Now go eat something.
Next month: What Proof Is Best?
Thanks to Sandi Gubin, David Jacobi, Joe Malkevitch, Henri Picciotto, and Evan Romer.
ENDNOTES
#1. I would’ve written “salad days”, but that seemed too cheap a pun. Oops, I just wrote it anyway.
#2. The restaurant was Sweeney Todd’s Pizza in Cambridge, England, no longer in business. (Maybe some health inspectors heard disturbing rumors about what sort of meat went on their pizzas?) Incidentally, Silouan Winter has pointed out to me on Twitter that in southern Germany you can find restaurants that offer an empty plate for kids who partake of their parents’ food, called a “Räuberteller” (“robber’s plate”).
#3. I’m reminded of Salvador Dali’s speech in which he stood up, said “I shall be so brief I have already finished,” and then sat down. Or did he? Anyone who can find a source for this quote should post it in the Comments!
#4. See the StackExchange discussion of the origin of the symbol λ for the empty string.
#5. I’m coining the term “stupor vacui” in analogy with the existing phrase “horror vacui“. It’s intended to refer to the way the mind boggles when it confronts the vacuous, and in desperation clings to answers like “Zero!” or “Nonsense!” or “Impossible!” and rejects an incongruously non-vacuous answer like “Exactly one”.
REFERENCES
Alissa Crans, “A Surreptitious Sequence: The Catalan Numbers” (video), produced by the Mathematical Association of America.
Martin Gardner, Nothing; chapter 1 in “Mathematical Magic Show”.
Martin Gardner, More Ado About Nothing; chapter 2 in “Mathematical Magic Show”.
Martin Gardner, Fibonacci and Lucas Numbers; chapter 13 in “Mathematical Circus”.
Martin Gardner, Catalan Numbers; chapter 20 in “Time Travel and Other Mathematical Bewilderments”.
Evelyn Lamb, A Few of My Favorite Spaces: The Empty Set.
mathenchant.wordpress.com 
Pingback: Let Us Define Our Terms |
Pingback: Who Needs Zero? |
Pingback: Reckoning and Reasoning |