BIJECTIONS The Abstractness of Number Ask the average person to tell you, in just a word, the main concern of mathematics, and most likely you'll get the response ``numbers.'' For nearly everyone, the first exposure to mathematics consists of learning to count, followed up by years of primary school training in arithmetic. So this response seems reasonable. But ask a mathematician instead, and more likely you'll get a response like ``structure.'' For a mathematician, the concept of number seems too abstract to form the core of the subject. Number abstract? Certainly. To illustrate, let's get specific. Suppose we want to talk about ``twelve,'' say. Then the immediate question becomes twelve what? Months in a year? Apostles? Steps to recovery? Days of Christmas? That the concept ``twelve'' can help us think and talk about all these things, and many more, indicates how far it lies, and all other numbers too, from the beginning of our thinking. Indeed, the ability to encompass such diverse situation constitutes the very mark of a high level abstraction. One imagines that people had strategies for dealing with the issue of quantity long before the invention of number. For example, early farmers letting their cattle out to graze in the morning would have had an interest in getting them all back at the end of the day. Nowadays, one would just count heads letting them out of the pen and again bringing them back. But without the ability to count, a herder could still do something like the following: Associate a particular pebble to each specific animal. Add that animal's pebble to a pile as it goes out and remove it when the animal returns. If any pebbles remain at the end of the day, that means missing cattle. This strategy, as stated, requires the herder to learn to tell apart all the animals and all the pebbles, to memorize the association between animal and pebble and to quickly sort out the pebble that matches a particular animal from, potentially, a large pile. One guesses that things may have started this way, but eventually the herds grew too large and so came the discovery that one need not associate a particular animal to a particular pebble. Just add a pebble for each animal that leaves and take one away for each that returns and the remaining pile will tell you if you don't have all your animals, though not in this case which particular animal you missed. With this step one has come come halfway to the invention of number, since the pile now functions solely as a record of the number of cattle out. Still, one has no way to formulate the quantity in one's mind except by referring to some thing, in this case the pile, which has that many parts. Some Counting Problems In certain branches of mathematics, pictures of the following sort, usually called Young diagrams, arise: ************** ******** ***** ***** *** ** * * The rules for a Young diagram say that (1) all the rows of *'s (or any other symbol) should line up on the left; and (2) the size of a row should never exceed the size of the row above it. Each Young diagram represents a certain addition fact. In the case of the one pictured above, it reminds us that the total number of *'s 39 = 14 + 8 + 5 + 5 + 3 + 2 + 1 + 1 the sum of all the row lengths. (Since a Young diagram may have but a single row, we don't rule out the possibility of having just a single summand.) One calls such an equation an INTEGER PARTITION. (One may either ask for the summands on the right to come in decreasing order, or just declare that order doesn't matter at all.) Since Young diagrams and integer partitions represent the same information, which to use in a given situation fall mainly to matter of taste. Mostly we'll find integer partitions more compact, but certain ideas come across more clearly with the diagrams. Integer partitions of various special types arise in many branches of mathematics. Special types arise, for example, when we restrict the sizes or relative sizes of the rows or columns. Example 1. Integer partitions with distinct odd summands. Distinct means that no number occurs as a summand more than once. Odd means all the summands come from the set of odd numbers. We tabulate the small examples: 1 = 1 2 = none 3 = 3 4 = 3+1 5 = 5 6 = 5+1 7 = 7 8 = 7+1 = 5+3 9 = 9 = 5+3+1 10 = 9+1 = 7+3 11 = 11 = 7+3+1 12 = 11+1 = 9+3 = 7+5 13 = 13 = 9+3+1 = 7+5+1 Example 2. Self-conjugate Young diagrams Self-conjugate means symmetrical about the the diagonal which extends down the the right from the upper right-hand corner. A glance at the tabulation below certainly makes this idea clear: 1:* 6:*** 9: ***** *** 12:****** ***** **** ** * , *** ** , *** , **** 2: none * * *** * ** ** * * * ** 3:** 7:**** * * * * * * * 10:***** **** 4:** * ** , *** 13:******* ***** **** ** * ** * , *** , **** 8:**** *** * * * *** *** 5:*** ** , *** * * * ** * * ** * * * * 11:****** **** * * , *** * * *** * * * * Relating the two examples Now an interest fact emerges: for each n , the number of integer partitions of n into distinct odd parts seems to equal the number of self-conjuagate Young diagrams with n *'s. So far we've only seen small numbers of possibilities for either type of structure, so we might wonder if this observation only registers a meaningless coincidence. Using a computer program we can quickly calculate the number of possibilities for each n for either type of structure. Either way we get the sequence 1, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8, 8, 9, 11, 12, 12, 14, 16, 17, 18, 20, 23, 25, 26, 29, 33, 35, 37, 41, 46, 49, 52, 57, 63, 68, 72, 78, 87, 93, 98, 107, 117, 125, 133, 144, 157, 168, 178, 192, 209, 223, 236, 255, 276, 294, 312, 335, 361, 385, 408, 437, 471, 501, 530, 568, 609, 647, 686, 732, 784, 833, 881, 939, 1004, 1065, 1126, 1199, 1279, 1355, 1433, 1523, 1621, 1717, 1814, 1925, 2048, 2166, 2286, 2425, ... That seems too much for mere coincidence. The numbers grow quickly from there. The number of self-conjugate Young diagrams with 229 *'s equals the number of odd distinct integer partitions of 229 equals 1008633, already more than a million. So we have something to prove, namely that these equalities persist indefinitely. One way to go about this involves finding an algebraic formula for the number of distinct, odd integer partitions and another for the number of self-conjugate Young diagrams and then using algebra to prove the two formulas equal. While possible, find such formulas and showing them equal poses much greater difficulties than just doing the job directly (in this case). Consider, for example, the self-conjugate Young diagram: ***** *** *** * * Pull it apart into upside-down L shapes, as follows: ***** * * ** * * * * Now straighten out all the pieces ********* *** * and a Young diagram with odd distinct rows emerges. You can reverse the process too: just bend the odd rows in half to make upside-down L shapes and then nest them. Neither the process nor its reverse changes the number of *'s. Thus, for each n, we've matched up all the strutures of one type with structures of the other. That means we must have equality between the numbers of structures of the two types. Now go back the preamble. For each n, we've learned the equality of a pair of numbers. For any particular n, we can compute both numbers and observe that they equal one another, but the general argument doesn't involve counting at all, rather it works directly with the structures, just like the herder who matches up pebbles and cows. Working directly with the structures, that mean less abstraction! The process of separating self-conjugate Young diagrams into upside-down L's and then straightening them, that process determines a FUNCTION from the set of self-conjugate Young diagrams with n *'s to the set of odd distinct integer partitions of n. Since we can reverse the process, we have an INVERSE the function it determines. We call a function which possesses an INVERSE a BIJECTION. When we prove two numbers (or two sequences of numbers) equal by means of a process such as this, we call that a bijective proof. Another bijective proofs concerning integer partitions Euler discovered that the number of odd integer partitions of n always equals the number of integer partitions of n with distinct parts. The following brief table begins to illustrates this: 1: 1 | 1 2: 1+1 | 2 3: 3 1+1+1 | 3 2+1 4: 3+1 1+1+1+1 | 4 3+1 5: 5 3+1+1 1+1+1+1+1 | 5 4+1 3+2 6: 5+1 3+3 3+1+1+1 1+1+1+1+1+1 | 6 5+1 4+2 3+2+1 Observe that all the summands in the partitions to the left of the line come from the odd numbers, but now we allow them to repeat. To the right of the line we never use a summand twice. In this case the computer shows the numbers of structures of both types (always equal) growing even faster: 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 38, 46, 54, 64, 76, 89, 104, 122, 142, 165, 192, 222, 256, 296, 340, 390, 448, 512, 585, 668, 760, 864, 982, 1113, 1260, 1426, 1610, 1816, 2048, 2304, 2590, 2910, 3264, 3658, 4097, 4582, 5120, 5718, 6378, 7108, 7917, 8808, 9792, 10880, 12076, 13394, 14848, 16444, 18200, 20132, 22250, 24576, 27130, 29927, 32992, 36352, 40026, 44046, 48446, 53250, 58499, 64234, 70488, 77312, 84756, 92864, 101698, 111322, 121792, 133184, 145578, 159046, 173682, 189586, 206848, 225585, 245920, 267968, 291874, 317788, 345856, 376256, 409174, 444793, ... Again, an explicit bijection removes the mystery. Given an integer partition into parts of different sizes, split all the even parts in half repeatedly until only odd numbers remain. For example, given 31 = 12 + 10 + 5 + 4 break the 12 down to 6 + 6 down to 3 + 3 + 3 + 3, the 10 down to 5 + 5, leave the odd number 5 alone and break the 4 down to 2 + 2 down to 1 + 1 + 1 + 1. This gives you 31 = 3 + 3 + 3 + 3 + 5 + 5 + 5 + 1 + 1 + 1 + 1 or 31 = 5 + 5 + 5 + 3 + 3 + 3 + 3 + 1 + 1 + 1 + 1 if you write the parts in descending order. By design, the process always produces a partition into odd parts. How do you go backwards? If you have a partition into odd parts, repeated add together equal parts until you can't do it anymore. For example, with 31=5+5+5+3+3+3+3+1+1+1+1 --- --- --- --- --- we would start by combining the underlined pairs which gives 31 = 10 + 5 + 6 + 6 + 2 + 2 ----- ----- and then again to get 31 = 10 + 5 + 12 + 4 a rearrangement of our original partition. A little thought should convince you that combining these two processes always brings you back to the partition you started with. A Vista: The Rogers-Ramanujan identity The number of integer partitions of n into parts either 1 more or 1 less than a multiple of 5 (i.e., parts from the sequence 1,4,6,9,11,14,16,19, ...) always equals the number of integer partions of n where the parts differ by AT LEAST 2. Try tabulating the possibilities for each type of structure up to n=20. Unfortunately the explanation in this case doesn't have a simple form. One can use tools from higher mathematics (calculus with complex variables) to get the result. Mathematicians Adriano Garsia and Stephen Milne gave an explicit bijection a few years back, but their bijection takes 50 pages to describe! Perhaps someday someone will find a simple reason for this simple fact. In any case, mathematicians place a special premium on facts so easily observed, even by a child, yet so hard to verify. The bijection behind Pascal triangle The formula C(m,n) = C(m-1,n-1) + C(m,n-1) plays a basic role when when wishes to compute rapidly a table of combination numbers (also called binomial coefficients). Now, by definition, C(m,n) counts the number of m-element subsets S of the set {1 , 2 , ... , n }. Given such an S, either it contains the last number n or it doesn't. If it does, then throwing away the n leaves an m-1-element subset of {1 , 2 , ... , n-1 } ( C(m-1,n-1) counts the number of these); otherwise S itself already constitutes an m-element subset of {1 , 2 , ... , n-1 } ( C(m,n-1) counts the number of these). One reverses the process as follows: given a subset T of {1 , 2 , ... , n-1 } with either m-1 or m elements ( C(m-1,n-1) + C(m,n-1) counts the number of these) throw in the number n in case T has just m-1 elements. Either way an m-element subset of {1 , 2 , ... , n } results. Another bijection related to combinations You can check by calculation (for small values of n) that 2 2 2 C(n,2n)= C(0,n) + C(1,n) + ... + C(n,n) As you might expect, a bijection lies behind this beautiful and unexpected formula. To select a n-element subset of {1 , 2 , ... , 2n} you could proceed as follows: (1) choose a number m between 0 and n ; (2) select m elements from {1 , 2, ... , n} ( C(m,n) possibilities); (3) select all but m elements from {n+1, n+2, ..., 2n} ( C(m,n) possibilities). 2 For EACH m you have C(m,n) choices. So the left side gives the total number of possibilities.