Teacher resources and professional development across the curriculum
Teacher professional development and classroom resources across the curriculum
The problem of keeping track of large numbers of possibilities is by no means a new one. The mathematicians of the middle kingdom in Egypt were quite aware of how quickly such problems can grow. An early piece of evidence of this comes from the Rhind Papyrus. This scroll, transcribed by Ahmes from Egyptian 12^{th} Dynasty mathematical texts, contains problems illustrating many different mathematical concepts, usually presented in applied form. One such problem, "Number 79," sometimes referred to as "the Inventory Problem," lays out a not-sostraightforward counting scenario:
There are seven houses; in each house there are seven cats; each cat kills seven mice; each mouse has eaten seven grains of barley; and each grain would have produced seven hekats (an old unit of measure equivalent to about 5 liters). What is the sum of all the enumerated things?
We can approach this problem, as the Egyptians did, in a so-called "brute force" fashion, by multiplying and adding four consecutive times. If there are seven houses, each of which has seven cats, then there is a total of forty-nine cats. The fact that there were seven mice munched by each cat means that a total of 343 mice met their demise. Continuing in this manner, we calculate that 2,401 grains of barley were eaten along with the mice, thereby keeping 16,807 hekats of barley out of production. Adding together all the quantities involved (i.e., houses, cats, mice, barley grains, and hekats of barley), we find that there were 19,607 things in total.
Notice that this problem involves finding the sum of a sequence of terms that increase geometrically—that is, each term is a constant multiple of the previous one. Starting with seven, and multiplying by seven each time, we get to almost 17,000 in four steps. This is an example of a geometric series, and it shows how quickly such a series can grow. We can find the desired sum in this case by adding the first five powers of seven:
7^{1} + 7^{2} + 7^{3} + 7^{4} + 7^{5} = 7 + 49 + 343 + 2,401 + 16,807 = 19,607
More generally, a geometric series is the sum of a sequence of terms in which each new term is generated by multiplying the preceding term by some fixed common factor. For example, the finite geometric series 1 + 2 + 4 + 8 +...+2^{n} (for some value of n) is such that each term is two times the term that precedes it. A famous illustration of the speed at which such a series grows is the one that asks how much money it would take to place one penny in the first square of a chessboard, two pennies in the second square, four in the third square, eight in the fourth square, and so on until there is a stack of pennies in each of the board's sixty-four squares. Fortunately, we do not have to use brute force, as the Egyptians would have, to solve this. The clever solution goes like this: In general, we can express a geometric series in this form:
a + ar + ar^{2} + ar^{3} + ar^{4} + … + ar^{n}
where a is some initial value and r is the constant factor or ratio. The general solution, then, of the sum of this geometric series is .
In the case of the pennies piling up on the chessboard, a = 1 and r = 2. Because there are sixty-four squares on a chessboard, n = 63 (the first square has one penny, represented by 2^{0}). The sum is, therefore,, which is equal to about 10^{19} pennies, or 10^{17} dollars (in non-scientific language, that's 100 million billion dollars)! This powerful example of how quickly a geometric series expands gives us a glimpse of the magnitude of combinatorial explosions.
Using a formula to find the sum of the geometric series underlying the Egyptian "inventory problem" and the pennies on the chessboard example demonstrates an important idea underlying combinatorial mathematics—problems in which the work grows very rapidly can often be reduced in clever ways to problems that are more easily controlled. This idea popped up again in India in the 7^{th} century AD, this time having to do with combinations of flavors.
The Indian medical text, Sushruta Samhita, written by Sushruta in the 6^{th} century BC, examines the ways in which six fundamental flavors, bitter, sour, salty, sweet, astringent, and hot, could be combined. (Note: It is important to realize that for the purposes of this discussion, by "combinations," we mean subsets of a larger set in which order doesn't matter; salty-sweet is the same as sweet-salty.) This ancient text showed that there were sixty-three such combinations, categorized as follows: six single tastes, fifteen pairs, twenty triples, fifteen quadruples, six quintuples, and, of course, one combination of all six tastes. There is, incidentally, one way to have zero flavors, generally called the "empty set," but we will disregard this because "flavorless" doesn't count as a flavor. Adding all of these possible groupings together, we can easily see that their sum is sixty-three, but is there a more clever and basic way to look at this?
One way to approach this problem would be to make an organized list. We could represent the six flavors with the letters A, B, C, D, E, and F and begin by listing the possible "combinations" of one: A, B, C, D, E, F. Then we can list the possible pairs: AB, AC, AD, AE, AF, BC, BD, BE, BF, CD, and so on. There seems to be a more general idea at work here. Can we get to it?
To help us reach an efficient solution to "the problem of the flavors," we can look for some function that will enable us to count the number of subsets of a given set of size n quickly and conveniently. Generally, we think of functions as math machines into which we put numbers and which spit out correlated numbers, but we can also think of a function as a way to describe how one set relates to another. In this set-based concept, a function is a rule that assigns to each member of a set of input values one, and only one, output value. For example, the absolute value function, |n|, takes all real numbers as inputs and maps each of them to their distance from the origin. Because distance is measured as a non-negative value, the function |n| maps the set of all real numbers to the set of non-negative real numbers. The inputs "5" and "-5" get assigned the same output of "5."
The concept that no single input gives more than one output is common to all simple functions. Some functions, however, are more restrictive. In addition to restricting each input to only one output, these functions require that each output is matched with exactly one input. Such functions, which are called "bijections" or "one-to-one correspondences," can be quite useful to us as we attempt to find clever solutions to combinatorial problems. To do so, we seek to show that two sets (the one that we are trying to find and another that we can directly relate to it to form the bijection) can be put into one-to-one correspondence with each other.
Imagine two sets, one containing a number of right shoes and the other containing a number of left shoes. Would there be a way to determine whether or not both sets are the same size (i.e., contain the same number of shoes) without counting them? We could pair up each right shoe with a left shoe and see if there are any leftovers in either set. If every right shoe pairs up with a left shoe, with no leftovers in either set, then we are guaranteed that the two sets are the same size. Given that assurance, we could simply count the right shoes and know that the number of left shoes is the same. In math, it is often possible to quantify a set of things that may be difficult to count using a set that is easier to count and then showing that there is a one-to-one correspondence between the two sets.
Armed with the power of bijection, we can efficiently tackle the flavors problem. Remember that we want to determine how many combinations, or subsets, of six flavors there are if order doesn't matter. We know that any given flavor will be either present in a subset or not. This means that we can represent each possible combination as a six-digit binary string, using only the digits 0 and 1. The first digit in the string indicates the status of flavor A; a 1 means "present" and a 0 means "absent." Likewise for the second digit, representing flavor B, and so on. In this system, the set of all flavors, {A,B,C,D,E,F}, would be written as 111111. The subset {A,B,D} would be indicated by the binary code 110100, whereas the subset {C,F} would be 001001. We can see that because each flavor can be only present or absent, each subset will be uniquely represented by a binary string. This defines a bijection between all subsets of six flavors and binary strings of length six.
Fortunately, figuring out how many six-digit binary strings there are is fairly straightforward and much easier than counting subsets of flavors. Each digit has only two options; it must be a 0 or a 1. We can simply multiply the number of options for each digit to figure out how many possible strings there can be.
2 × 2 × 2 × 2 × 2 × 2 = 2^{6} = 64 strings
One of those strings, 000000, corresponds to "no flavor," however, and we have already decided to disregard that option, so we end up with a grand total of sixty-three subsets. In general, we have found that the number of non-empty subsets of n elements is 2^{n}-1. This method is significantly faster than listing all the possible combinations. The drawback of this method is that it does not tell us how many subsets of a given size there are.
Recall that, according to the Indian text, there are six single flavors, fifteen pairs, twenty triples, fifteen quadruples, six quintuples, and one way to combine all six flavors. Is there a way to find these numbers—to enumerate subsets according to their size—without listing and sorting all possible combinations? Our method of finding a bijection between the total number of subsets and binary strings doesn't immediately give us this level of detail. In the next section we will see how to count subsets of a particular size by using a function that has many uses in both combinatorics and beyond, C(n,k).
Next: 2.3 Flavors Revisited