Fall 2001
taught by Prof. James Propp
This course, offered in conjunction with the NSF-funded "Research Experiences in Algebraic Combinatorics at Harvard" (R.E.A.C.H.), will bring students to the point of being able to conduct original research in low-dimensional combinatorics, using algebraic and bijective techniques. Methods taught will include recurrence relations (linear and non-linear), transfer matrices, and generating functions; special topics will include frieze patterns, number walls, and tilings. There will be an emphasis on discovery and the use of computers (specifically Maple).
LOGISTICS ---------
You may take Math 192r even if you've already taken Math 192 (that's what the "r" means).
Math 192 was originally scheduled to meet 4:00-5:30 p.m. on Tuesdays and Thursdays in Science Center 216. HOWEVER, it will instead meet from 2:30 to 4:00 p.m. on Tuesdays and Thursdays in Sever 103.
The required text will be "Concrete Mathematics: A Foundation for Computer Science", by Ronald L. Graham, Donald E. Knuth, and Oren Patashnik (2nd edition). I will be putting a single copy of this text on reserve at Cabot Library, so in principle it is possible to avoid buying the book. But since I'll be assigning over 100 pages from Graham, Knuth, and Patashnik, and since the book is so fun and informative, I urge all Math 192 students to purchase it.
You might also benefit from looking at two books by Herbert S. Wilf which are available via the Web: generatingfunctionology (publisher: Academic Press/Harcourt Brace) and East Side, West Side (Lecture notes on combinatorial objects and Maple programs for generating them.)
Grading for the course will be based upon homework scores (50%), take-home exam scores (50%), and class participation (10%), with the lowest 10% being dropped. (That is: your grade will be calculated using the weighting 40% 50% 10%, 50% 40% 10%, or 50% 50% 0%, and the one that is highest will be used.)
On most days there will be homework. Cooperation on homework is allowed, indeed encouraged. Extensions will be granted only under unusual circumstances. The lowest 10% of a student's homework scores will be dropped (including 0's for assignment not turned in or not turned in on time).
The two take-home exams (one due in the middle of the term, the other at the end of Reading Period) must be done individually.
A TASTE OF ALGEBRAIC COMBINATORICS ----------------------------------
To explain what Math 192 and R.E.A.C.H. are about, let me give an example. Two good "stories" come to mind. One of them is about number partitions and lattice paths and binomial coefficients and plane partitions and tilings and MacMahon coefficients (and why the last three are analogues of the first three, in one higher dimension). The other story is about the Fibonacci numbers 1,2,3,5,8,13,...
I'll tell the second story, because the concepts may be more familiar.
Here are six things that are all equal to each other, for every positive integer n:
(1) The number F(n) that you get when define F(1) = 1 and F(2) = 2 as initial conditions and inductively define
for all k > 2.
(2) The number of ways to tile a 2-by-n rectangle with 1-by-2 and 2-by-1 rectangles, so that there are no overlaps or gaps.
(3) The coefficient of x^n in the Taylor expansion of the function
x + x^2
-----------
1 - x - x^2
around the point x=0.
(4) The upper-left entry in the nth power of the two-by-two matrix
(1 1)
(1 0)
(5) The number
n+1 n+1
([1+sqrt(5)]/2) - ([1-sqrt(5)]/2)
---------------------------------------
sqrt(5)
(6) The number of terms in the determinant of the n-by-n matrix
(a 1 0 0 0 ... 0 0)
(1 b 1 0 0 ... 0 0)
(0 1 c 1 0 ... 0 0)
(0 0 1 d 1 ... 0 0)
(0 0 0 1 e ... 0 0)
(. . . . . . . .)
(. . . . . . . .)
(. . . . . . . .)
(0 0 0 0 0 ... i 1)
(0 0 0 0 0 ... 1 j)
(7) The number of terms in the numerator of the ordinary fraction obtained
by simplifying the n-level continued fraction
a + 1
---------------------------
b + 1
-----------------------
c + 1
-------------------
d + 1
---------------
e + 1
-----------
...
+ 1
-----
i + 1
-
j
In Math 192, I will impart an understanding of the general techniques that allow us to see why these quantities are the same. These techniques can be applied to a wide variety of problems.
Near the end of the course, students will encounter more advanced facts
about the Fibonacci numbers (and the broader issues they raise). For
instance, continuing the above list, here are two more descriptions of
the nth Fibonacci number:
(8) The number (-1)^n F(-n-2), where F() is the same function as defined
in (1) but now defined for negative values of its argument by taking
the recurrence relation and running it _backwards_ (that is, put
F(2) = 2 and F(1) = 1, and inductively define F(k-2) = F(k) - F(k-1)
for all k < 3). If you do this, you'll get 0,1,-1,2,-3,5,-8,13,...
That is, the Fibonacci sequence, run backwards, give you the
Fibonacci numbers again, with some minus signs. Is this a coincidence
or does it mean something?
(9) The number G(n) that you get when set G(1) = 1 and G(2) = 2
as initial conditions and inductively define
Note that (8) is an instance of a surprising SYMMETRY. (A priori, we
expect F(0), F(-1), F(-2), ... to be integers, but we had no reason to
expect them to be Fibonacci numbers or their negatives.)
Also note that (9) is an instance of surprising INTEGRALITY. (A priori, we
might expect the numbers G(k) to be fractions, not integers, since the recursive
formula for G(k) involves division.)
In R.E.A.C.H., students will come to grips with other instances of
surprising symmetry and surprising integrality, and will try to
find proofs of things that have never been proved before (not because
the problems are necessarily hard, but because the questions are new).
For more about R.E.A.C.H., click here.
For a quickie write-up of the surprising symmetry property of the
Fibonacci numbers (property (8)),
click here.
For a quickie write-up of the surprising integrality property of the
Fibonacci numbers (property (9)),
click here.
If you have any questions, send email to
propp@math.harvard.ee-dee-you.
Last updated September 4, 2001.
G(k-1)^2 + (-1)^k
G(k) = ----------------- .
G(k-2)
Certainly we could prove that G(n) = F(n) by induction, either
using the formula for F(n) that involves sqrt(5) or using the
inductive definition of the Fibonacci numbers, but this is
unenlightening. Might the equation
F(k) F(k-2) = F(k-1)^2 + (-1)^k
be trying to tell us something about tilings of 2-by-n rectangles?
MORE QUESTIONS?
---------------