odd trinomials: t(n) = (1+x+x^2)^n 1 111 10101 1101011 100010001 11101110111 1010001000101 110110111011011 10000000100000001 1110000011100000111 101010001010100010101 11010110110101101101011 1000100000001000000010001 111011100000111000001110111 10100010100010101000101000101 1101101101101101011011011011011 100000000000000010000000000000001 Number of ones in the nth line: 1,3,3,5,3,9,5,11,3,9,9,15,5,15,11,21, ... Let z(n) be the number of odd coefficients of (1+x+x^2)^n. n n_2 z(n) ---------------- 0 0 1 1 1 3 2 10 3 3 11 5 4 100 3 5 101 9 6 110 5 7 111 11 8 1000 3 9 1001 9 10 1010 9 11 1011 15 12 1100 5 13 1101 15 14 1110 11 15 1111 21 16 10000 3 17 10001 9 18 10010 9 19 10011 15 20 10100 9 21 10101 27 Structure Theorem: The structure of the triangle is of the form A+B A A+B B B A A and B are matrices of order 2^n. Proof by induction: n=0: A = 0 and B = 1. That is 1 0 1 1 1 0 n->n+1: As (1+x+x^2)^2 = 1 + x^2 + x^4 (modulo 2) we get by iteration (1+x+x^2)^(2^n) = 1 + x^(2^n) + x^(4^n) (modulo 2). This shows the block recursion equation C D E for blocks of size 2^n. C+D+E Apply this to A+B A A+B B B A gives the larger triangle A+B A A+B B B A A+B A A+B A A+B A A+B B A A+B A A+B B A with the new blocks A', B', and A'+B' A' = A 0 B' = A A+B and A'+B' = 0 A+B B A A A+B A+B B This induction step gives us a recursion for z(n). The number of ones in the n-th line of A+B A A+B A A+B A is 3 times the number of ones in the n-th line of A+B A. Further the number of ones in the n-th line of A+B B A A+B A A+B B A is 2 times the number of ones in the n-th line of A+B A plus the number of ones in the n-th line of A+B B B A. Note that you have to count the three blocks A, B, and A+B. Counting A and B only is not sufficient as some ones cancel in the sum. Using the binary number system we get a nice recurence. Recursion: (left) Let us write the number n in binary form as a list. Use the prolog notation [x,y|w] with x, y the two leading bits and w the rest. Then we have the recursion formular z([]) = 1, z([0|w]) = z(w), z([1]) = 3, z([1,x|w]) = 2 * z(w) + z([x|w]). Example: [1,1,0,1] = [x,y|w] with x=y=1 and w = [0,1]. There is the special case when n = 2^p - 1. Let a(p) = z(2^p - 1) then the recurence a(p) = a(p-1) + 2*a(p-2) for p>1 holds and a(0)=1, a(1)=3. This is a(p) = (4*2^p - (-1)^p)/3. There is a "multiplicative" formular of the function z. This can be shown by induction using the recursion. But the direct way is much better. Lemma 1: If the binary representation of n contains a zero at place k then z(n) = z(n1)*z(n2) where n = 2*n1*2^k + n2 with n2 < 2^k. Proof: So n1 contains the bits higher than the kth and n2 the bits lower than the kth. The polynomial t(2*n1*2^k) has a spacing of 2*2^k between their ones. The degree of t(n2) is 2*n2 and therefore lower than the spacing 2*2^k. Therefore the ones of the product t(n) = t(2*n1*2^k)*t(n2) do not interfere. Therefore z(n) = z(2*n1*2^k)*z(n2) = z(n1)*z(n2). Lemma 2: If the binary representation of n contains no zero then there is a p with n = 2^p - 1, further z(n) = (4*2^p - (-1)^p)/3 = floor( (4*n+5)/3 ). Proof: Calculating Backwards They are most easily recalculated from the lines with n = 2^p. More generally we calculate (x^m + 1 + x^-m) / (x+1+1/x). (x^(3n+1) + 1 + x^-(3n+1)) / (x+1+1/x) has 4n + 1 ones. (x^(3n+2) + 1 + x^-(3n+2)) / (x+1+1/x) has 4n + 3 ones. Note (x+1+1/x) does not divide x^(3n) + 1 + x^-(3n). You only have to notice the period 3 when you want going backwards 11011011011011011011 .. 1000000000000000000000 .. An induction on the number of one-blocks shows the following theorem. Theorem: z(n) = a(p1)*a(p2)*...*a(pN), where p1, p2, ..., pN are the length of 1-blocks in the binary notation of n. Example: z([1,1,0,0,1,0,1,1,1,1,0]) = z([1,1])*z([1])*z([1,1,1,1]) = a(2)*a(1)*a(4) = 5*3*21. Corollary: z([b1, b2, ..., bN]) = z([bN, ..., b2, b1]). Recursion: (right) z(2n) = z(n), z(4n+1) = 3*z(n), z(4n+3) = z(2n+1) + 2*z(n). This follows from recursion1 and the corollary. Density: Lines with n = 2^p - 1 have the highest density of ones (2/3 in the limit). A question of the USSR problem book ask for a proof that not all entries in line n are odd. But you can do much better. Lemma: There are no four ones in a row. Proof: case n even: Every second position is even. So there cannot be two odd numbers in a row. case n odd: Examine the cases coming from a line where every second number is even. You will see that no 3-block can get longer. Corollary: The number of zeroes is at least floor(linelength/4). References: - J. D. Bankier; Generalizations of Pascal's triangle, American Mathematical Monthly 64 (1957) 416-419 Zbl 0079.01006 - (1 + x + x^2)^k - Bollinger, Richard C. Extended Pascal triangles. Mathematics Magazine 66, No.2, 87-94 (1993). Zbl 0785.05006 - Bollinger, Richard C.; Burchard, Charles L. Lucas's theorem and some related results for extended Pascal triangles. American Mathematical Monthly 97, No.3, 198-204 (1990). Zbl 0741.11014 - Bondarenko, Boris A. Generalized Pascal triangles and pyramids, their fractals, graphs, and applications. Transl. from the Russian by Richard C. Bollinger. Santa Clara, CA: The Fibonacci Association, vii, 253 p. (1993). Zbl 0792.05001 - Granville, Andrew Zaphod Beeblebrox's brain and the fifty-ninth row of Pascal's triangle. American Mathematical Monthly 99, No.4, 318-331 (1992) Zbl 0757.05003 (self-similarity of Pascal's triangle modulo powers of 2) - Granville, Andrew Correction to: Zaphod Beeblebrox's brain and the fifty-ninth row of Pascal's triangle. American Mathematical Monthly 104, No.9, 848-851 (1997) Zbl 0889.05004 (self-similarity of Pascal's triangle modulo powers of 2) - Heinrich Hemme; Der Wettlauf mit der Schildkr\"ote, G\"ottingen, 2002, Vandenhoeck & Ruprecht, ISBN 3-525-40740-8 Problem 38: Das Zahlendreieck - D. O. Shklarsky, N. N. Chentzov, I. M. Yaglom; The USSR Olympiad Problem Book, San Francisco, 1962, p8-9, 96 - The On-Line Encyclopedia of Integer Sequences; ID Number: A071053 Sequence: 1,3,3,5,3,9,5,11,3,9,9,15,5,15,11,21,3,9,9,15,9,27,15,33,5, 15,15,25,11,33,21,43,3,9,9,15,9,27,15,33,9,27,27,45,15,45, 33,63,5,15,15,25,15,45,25,55,11,33,33,55,21,63,43,85,3,9,9, 15,9,27,15,33,9,27,27 Name: Number of 1's in n-th row of triangle in A071036. References S. Wolfram, A New Kind of Science, Wolfram Media, 2002; Chapter 3. - Stephen Wolfram; A New Kind of Science, Wolfram Media, Inc., 2002. Hardcover, 1197 pp., ISBN 1-57955-008-8 (MAA Online book review by Henry Cohn http://www.maa.org/reviews/wolfram.html) -- http://www.mathematik.uni-bielefeld.de/~sillke/ mailto:Torsten.Sillke@uni-bielefeld.de