Fall 2003
taught by Prof. James Propp
This course, offered in conjunction with the NSF-funded Spatial Systems Laboratory (SSL), will bring students to the point of being able to conduct supervised 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 triangulations, tilings, Markoff numbers, and Somos sequences.
This course will not require much in the way of prior background in combinatorics (beyond the level of, say, the use of binomial coefficients in counting combinations), but students who take the course will find that a background in discrete mathematics or graph theory, and in the writing of proofs, will be helpful.
There will be an emphasis on discovery and the use of computers (specifically Maple). Prior knowledge of Maple is not required.
LOGISTICS ---------
Math 491 meets on Tuesdays and Thursdays from 9:30 to 10:45 a.m. in B321 Van Vleck (except when we go to B130 for software demonstrations).
My office hours are Tuesdays from 2:15 to 2:45 p.m. and Thursdays from 12:15 to 12:45 p.m.; I am also available by appointment.
There will be no required text for this course. One book I highly recommend is "Concrete Mathematics: A Foundation for Computer Science", by Ronald L. Graham, Donald E. Knuth, and Oren Patashnik (2nd edition). I will be putting a copy of this text on reserve at the Mathematics Library. But most of you will find the book so fun and informative that you may be tempted to buy 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 three different ways, using the weighting 40% 50% 10%, the weighting 50% 40% 10%, and the weighting 50% 50% 0%, and the grade that comes out highest will be used.) Being a class participant means attending lectures, asking good questions, and making intelligent attempts to answer questions raised by me or other students.
On most days there will be homework assigned, due one week later. 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). Homework will be graded on the basis of clarity of expression as well as mathematical correctness.
The two take-home exams (one due in the middle of the term, the other at the end) must be done individually.
In lieu of taking the final exam, you can opt to write a research paper; advance approval of topic is required.
A TASTE OF ALGEBRAIC COMBINATORICS ----------------------------------
To explain what Math 491 is about, let me give an example.
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 491, 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 the Spatial Systems Laboratory,
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 SSL, 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.wisc.edu.
Last updated September 2, 2003.
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?
---------------