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