As with building the triangles, we shall develop this method in stages.
2456 = 2(1000) + 4(100) + 5(10) + 6(1)
2456 = 2(10^{3}) + 4(10^{2}) + 5(10^{1}) + 6(10^{0}).
We call the number 10 the base of this system of representing numbers. There is really nothing special about 10, any other number can be used as the base of a positional number system. The reason we use 10 is probably related to the fact that we have 10 fingers and counting on the fingers was the earliest way to represent numbers. Had human beings developed with only one hand with 5 fingers on it, our number system would probably have been based on 5. In a system based on 5, the only digits would be 0, 1, 2, 3 and 4. With a base of 5, the number 2031 would represent:
Using other bases to represent our numbers is more common than you might think. In a computer, numbers are actually represented with base 2, while computer programmers often use base 8 and base 16. Numbers written with base 2 are called binary numbers, with base 8 they are called octal numbers and with base 16 they are called hexadecimal numbers. Our base 10 numbers are of course called decimal numbers.
We will need to be able to write numbers in different bases for the work we want to do. Given a number written in base "a" we can easily find out what it is in base 10, just follow the example above of (2031)_{5}, where a = 5. To convert the other way, that is, given a number written in base 10, to find what it is in base "a", is a little trickier. Here's an example. Suppose I wanted to know what 105 is when it is written in base 3. The first thing I do is to write out the powers of 3 until they are bigger than the number I want to convert (105 in this case). So, 3^{0} = 1, 3^{1} = 3, 3^{2} = 9, 3^{3} = 81, 3^{4} = 243. Now, take the largest power of 3 that is smaller than 105 and divide by it (105/81 = 1 + remainder). We then write 105 = 1(81) + 24. Now repeat the process with the 24 instead of the 105 and use the next smaller power of 3 (24/9 = 2 + remainder). We can then write, 105 = 1(81) + 2(9) + 6. Repeating with the 6 and the next smaller power of 3, we'll get 105 = 1(81) + 2(9) + 2(3). Finally, remembering that all the powers of 3 from 81 down must be present, we write 105 = 1(81) + 2(9) + 2(3) + 0(1). We can now read off the positional notation for base 3 and say that 105 = (1220)_{3}.
5 = (101)_{2}
3 = (011)_{2}.
Now we examine each position, and if it is always true that the digit on top is greater than or equal to the digit directly below it, we say that the bottom number implies the top number. But, if there is at least one position in which the top digit is smaller than the bottom digit, then the bottom number does not imply the top number. In our example, 3 does not imply 5 because in the 2nd position we have a 0 over a 1. (This terminology comes from computer science and I won't try to explain it.) Consider C(23,21), we would write:
23 = (10111)_{2}
21 = (10001)_{2},
and notice that 21 implies 23.
The rule that we are looking for is: C(n,k) is odd if k implies n and even if k does not imply n. Notice in our examples that C(5,3) = 10 (which is even and 3 does not imply 5) and C(23,21) = 253 (which is odd and 21 implies 23). You should try a number of examples to convince yourself that this always works.
Let's look at some special cases to see how we can use this relationship to understand the structure of the mod 2 Pascal Triangle. First of all, 0 implies any number, so C(n,0) is always odd. Also, any number implies itself, so C(n,n) is also odd for any n. In terms of the triangle, this means that any row will always start and end with a black square. Now consider the numbers 1, 3, 7, 15, 31, etc. (the numbers that are one less than a power of 2). When written base 2, these look like:
n | base 2 |
---|---|
1 | (1)_{2} |
3 | (11)_{2} |
7 | (111)_{2} |
15 | (1111)_{2} |
31 | (11111)_{2} |
In the diagram above, I've written the row numbers in base 2. For the rows where I have placed the row number on the right, the appearance of the row follows from what I have said above. Rows 5 and 6 (labelled on the left) have red squares in them (which will eventually be colored black). To see where the additional black squares are supposed to go in these rows we must consider the form of the base 2 representation of the row number. Now 5 = 101 and any number that implies 5 (i.e., a position where we will put a black square) must have a 0 in its middle position, that is, such a number must look like *0* (in its base 2 representation). The *'s can be either 0 or 1, it doesn't matter which. There are four ways to replace the *'s. We could replace both by 0 (and get the number 0) or replace them both by 1 (and get the number 5 back). The other two ways to replace them will give the positions of the remaining two "black" squares in this row, namely, 001 ( = 1) or 100 ( = 4). Thus, there will be black squares in positions 1 and 4 of row 5 (remember to start counting at 0), these are the ones I've colored red in the diagram. In row 6 = 110, we will get black squares in those positions whose base 2 representation looks like **0. Again, we get 0 and 6 if we fill the *'s with the same number, and the other two possibilities give 010 (= 2) and 100 ( = 4).
It should now be easy to see that we can tell how many black squares there will be in any row of the triangle. For instance, if we wanted to know how many black squares there were in row 13, we would first write 13 =(1101)_{2}, and then note that the positions where the black squares appear will have the base 2 form **0* (a * for each 1 in the row number). Since there are 2 ways to replace a *, we will get (2)(2)(2) = 8 positions (always including the first and last). To find the positions, we must write down the 8 numbers we get when we replace the *'s by numbers. In this case they are
We can describe the rows of Pascal's triangle mod p using the same ideas that we developed for the mod 2 triangle. For instance, consider row 15 of the mod 3 triangle. 15 = (120)_{3}. Those positions where the position number implies 15 will be colored black, and those where the position number does not imply 15 will be colored white. We must work out which numbers imply 15 and which ones don't. In order to imply 15, a number's base 3 representation must have either a 1 or 0 in the first position, a 2, 1 or 0 in the second and a 0 in the third position. Thus, there are (2)(3)(1) = 6 positions in the row that will get black squares. These are:
Check this with the mod 3 triangle that you constructed!
Let's continue to examine the mod 3 triangle. In the example above, notice that 0 implies 15 and 15 implies 15. These statements will be true for any row, namely 0 implies any number n for any modulus and n will always imply n for any modulus. This means that the first and last positions of any row will always be black (for any triangle, not just mod 3). In a manner similar to what occurred in the mod 2 case, any row number whose base 3 representation consists of all 2's (2 = (2)_{3}, 8 = (22)_{3}, 26 = (222)_{3}, etc.) will have a corresponding row consisting of all black squares because every number smaller than them implies them. But these are not the only rows with all black squares. Rows 1 = (1)_{3}, 5 = (12)_{3}, 17 = (122)_{3}, 53 = (1222)_{3}, etc. also consist of all black squares. The reason that these numbers (with base 3 representation being a 1 followed by all 2's) work as well is easy to see. If a number were not to imply one of these, it would have to start with a 2, but any number whose base 3 representation started with a 2 would be bigger than the number you started with, for instance, if we start with 17 = (122)_{3}, then any 3 digit number that does not imply 17 would have to look like 2**, but the smallest such number is 200 = 18 which is already larger than 17. So, all the numbers that are less than or equal to 17 will imply 17 and the 17th row will be all black. Rows that are powers of 3 (3 = (10)_{3}, 9 = (100)_{3}, 27 = (1000)_{3}, etc.) will again be all white except the first and last positions. Rows that are twice a power of three (6 = (20)_{3}, 18 = (200)_{3}, etc.) will have only three black squares (the first, the last and the one in the middle). For instance, in row 18 there are black squares only in positions 0, 18 and 9 = (100)_{3}.
In the mod 5 triangle, there are rows of all black squares when the row number has any of these forms: (44...44)_{5}, (344..44)_{5}, (244..44)_{5}, or (144..44)_{5}. Rows with numbers of the form (400..00)_{5} will have 5 black squares, those of the form (300..00)_{5} will have 4 black squres, those of the form (200..00)_{5} will have 3 and finally the powers of 5 (of the form (100..00)_{5}) will have only 2 black squares.
By examining many of the rows for each prime modulus, you will begin to see where the patterns are coming from.
B. 1 100 = 64 + 32 + 4 = 1(64) + 1(32) + 0(16) + 0(8) + 1(4) + 0(2) + 0(1) = (1100100)_{2}
B. 2 256 = 4(64) = 4(64) + 0(8) + 0(1) = (400)_{8}
B. 3 1257 = 1(729) + 6(81) + 4(9) + 6(1) = (1646)_{9}
B. 4 35 = 32 + 2 + 1 = 1(32) + 0(16) + 0(8) + 0(4) + 1(2) + 1(1) = (100011)_{2}
C. 1 C(4,1) = 4. 4= (100)_{2} ... 1 = (001)_{2} so 1 does not imply 4.
C. 2 C(5,2) = 10. 5 = (101)_{2} ... 2 = (010)_{2} so 2 does not imply 5.
C. 3 C(6,3) = 20. 6 = (110)_{2} ... 3 = (011)_{2} so 3 does not imply 6.
C. 4 C(7,3) = 35. 7 = (111)_{2} ... 3 = (011)_{2} so 3 does imply 7.
C. 5 C(4,4) = 1. 4 = (100)_{2} ... 4 = (100)_{2} so 4 does imply 4.
C. 6 C(8,0) = 1. 8 = (1000)_{2} ... 0 = (0000)_{2} so 0 does imply 8.
D.1 Since 9 = 1001, there will be 4 black squares. Positions 0, 1, 8 and 9.
D.2 Since 10 = 1010, there will be 4 black squares. Positions 0, 2, 8 and 10.
D.3 Since 14 = 1110, there will be 8 black squares. Positions 0, 2, 4, 6, 8, 10, 12, and 14.
D.4 Since 33 = 100001, there will be 4 black squares. Positions 0, 1, 32 and 33.
D.5 Since 65 = 1000001, there will be 4 black squares. Positions 0, 1, 64 and 65.
D.6 Since 128 = 10000000, there will be only two black squares. Positions 0 and 128.