## Pascal's Triangle using Clock Arithmetic - Part II

In order to better understand these triangles we will develop a faster method for deciding when a position is to be colored black or white. Of course we already know one way to do this, for instance, if we wanted to know what to color the (5,3) position in the mod 10 triangle, we could calculate the binomial coefficient C(5,3) and if it is divisible by 10 the position gets colored white, if not then it is colored black. Since C(5,3) = 10, we would color this position white. The difficulty with this approach is that the binomial coefficients get very large very quickly and it would be nice to have a method for determining the answer without having to calculate these large numbers.

As with building the triangles, we shall develop this method in stages.

#### Representing Numbers in Different Bases

The positional notation that we use to represent numbers is based on the number 10. The meaning of a digit in a number depends on its position in that number. So, the 4 in 2456 really means 400 since it is in the 100's position, while the 5 means 50 because it is in 10's position. Expanding the number so that this is clear, we have:

2456 = 2000 + 400 + 50 + 6

2456 = 2(1000) + 4(100) + 5(10) + 6(1)

2456 = 2(103) + 4(102) + 5(101) + 6(100).

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:

2031 = 2(53) + 0(52) + 3(51) + 1(50).
In our base 10 notation, this same number would be written as 2(125) + 0(25) + 3(5) + 1(1) = 250 + 15 + 1 = 266. To keep things from getting really confusing, when we represent a number with a base different from 10, we'll enclose it in parentheses and write the base as a subscript. So, we would write (2031)5 = 266.

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, 30 = 1, 31 = 3, 32 = 9, 33 = 81, 34 = 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.

##### Exercises
A. Find the base 10 representation for these numbers:
1. (234)5
2. (100111)2
3. (1201)3
4. (215)8
B. Find the representation of these decimal numbers in the given base:
1. 100 in base 2
2. 256 in base 8
3. 1257 in base 9
4. 35 in base 2

#### Binomial Coefficients Mod 2

To determine if the binomial coefficient C(n,k) is even (so that the (n,k) position of the mod 2 triangle will be colored white) or odd (the position gets colored black), we represent both n and k as base 2 numbers, and line them up with n on top. If one of the numbers is shorter than the other, you can fill out the shorter one by adding 0's on the left. So, for C(5,3) we would write:

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.

#### Exercises

C. Show that the rule works for these binomial coefficients:
1. C(4,1) = 4
2. C(5,2) = 10
3. C(6,3) = 20
4. C(7,3) = 35
5. C(4,4) = 1
6. C(8,0) = 1

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
These are the numbers whose base 2 representation consists of all 1's. Every number less than or equal to these will imply them (because they contain no 0's), so if n is one of these then C(n,k) will always be odd for all k. The rows that correspond to these numbers are all black. Next look at the powers of 2. Their base 2 representations all have the form of a 1 followed only by 0's : 2 = (10)2, 4 = (100)2, 8 = (1000)2. Now every number less than a power of 2 (other than 0) will have a 1 in some position other than the first position. That means that means that no number other than 0 which is less than a power of 2 can imply a power of 2. So, the binomial coefficients C(2i, k) are always even except for the first and last, and the row of the triangle corresponding to a power of 2 will be all white except for the first and last positions.

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

0000 = 0
0001 = 1
0100 = 4
0101 = 5
1000 = 8
1001 = 9
1100 = 12
1101 = 13.

#### Exercises

D. Find the number of black squares and their positions in the following rows of the Mod 2 Pascal's Triangle:
1. row 9
2. row 10
3. row 14
4. row 33
5. row 65
6. row 128

#### Binomial Coefficients Mod p, p a prime

The rule for dealing with prime moduli is essentially the same as the rule we used when the modulus was 2. Namely, C(n,k) is divisible by the prime p (i.e., is equal to 0 mod p) whenever k does not imply n, and is not divisible by p when k does imply n. The only difference is that now when we speak of implying or not implying, we are talking about representations in base p. For example, consider C(4,2) = 6. With respect to the prime 3, we write 4 = (11)3 and 2 = (02)3. Now we see that 2 does not imply 4 (in the last position a larger number is on the bottom), so 3 divides C(4,2). On the other hand, with respect to the prime 5, 4 = (4)5 and 2 = (2)5, so 2 does imply 4 and C(4,2) is not divisible by 5.

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:

000 = 0
010 = 3
020 = 6
100 = 9
110 = 12
120 = 15.
So, the 15th row of the mod 3 triangle should look like:

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.

#### Exercises

E. Determine what the rows of the following triangles look like and check your answer by looking at the examples in the previous web page.
1. row 7 of the mod 3 triangle.
2. row 10 of the mod 5 triangle.
3. row 14 of the mod 7 triangle.
4. row 33 of the mod 3 triangle.
5. row 25 of the mod 5 triangle.
6. row 28 of the mod 7 triangle.

#### Answers to Exercises

A. 1 (234)5 = 2(25) + 3(5) + 4(1) = 50 + 15 + 4 = 69.
A. 2 (100111)2 = 1(32) + 0(16) + 0(8) + 1(4) + 1(2) + 1(1) = 32 + 4 + 2 + 1 = 39.
A. 3 (1201)3 = 1(27) + 2(9) + 0(3) + 1(1) = 27 + 18 + 1 = 46.
A. 4 (215)8 = 2(64) + 1(8) + 5(1) = 128 + 8 + 5 = 141.

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.