Math 373 — Topics in Combinatorics — Spring ’13

Math 373 — Topics in Combinatorics — Spring ’13
MWF 11:45–12:35 in Votey 369
Professor
Office
Phone
Email
Web page
Office hours
Greg Warrington
Mansfield 107
802.656.2195
[email protected]
www.cems.uvm.edu/∼gwarring/math373
TBA
About this course: Most interesting problems can be approached in a multitude of
ways. Generating functions are a powerful technique that can often be used when sequences
of numbers are involved (implicitly or explicitly). These functions often lead to very elegant
solutions.
A few examples of questions that can be answered elegantly using generating functions:
• How many ways are there to partition an n-element set into blocks?
• How many labeled trees with n vertices are there?
• Fix a positive integer q and let f (n, q) be the number of permutations of {1, 2, . . . , n}
with all cycles of length greater than q. What is the asymptotic behavior of f (n, q)?
(That is, what fraction of n! is f (n, q) as n → ∞?)
We will cover the majority of Wilf’s textbook (see below). Most of the time we will
consider the generating functions as formal power series — i.e., as algebraic objects. But at
the end of the course we will explore some of the facts we can learn by considering generating
functions as analytic functions. This symbiosis between combinatorics and complex analysis
is a great example of how many of the divisions in mathematics we have created are truly
artificial.
Text: Generatingfunctionology, Wilf. 3rd edition. The online version (legal!) is the 2nd
edition. I haven’t checked the differences particularly closely, but I believe they are all minor.
The exception is the addition of sections 4.11 and 4.12. I’ll check to make sure the exercises
I assign have the same numbers in both versions. If not, I’ll warn you.
Hopefully we will also have time to cover some material out of Analytic combinatorics by
Flajolet & Sedgewick; I will not expect you to own this book.
Prerequisites: Mostly just mathematical sophistication. Some facility with counting (as
in Math 173) and, to a lesser extent, analysis (as in Math 241) will be useful but not strictly
necessary. Please talk to me if you are unsure whether you have appropriate preparation.
Office hours: You are welcome to stop by my office at any time. During scheduled office
hours I can always be found in my office, Mansfield 107; no appointment is necessary. I also
check my email frequently and am happy to try to answer questions and/or give hints on
homework that way. We can also schedule meetings at times convenient to you.
Grading:
• 40% — Homework due every week or two.
• 5% — Participation. As far as I’m concerned, each student in a class has a responsibility to his/her fellow students: To participate. This is especially true in small
classes. That said, asking a question and answering a question are equally valued.
• 25% — Midterm exam.
• 30% — Final exam.
Note that either the midterm or final may have a take-home component (or be entirely
take-home).
Homework assignments:
(1) A good proof is not only logically correct, but also convincing. If your proof looks
like a draft you will be asked to resubmit.
(2) Late assignments will only be accepted for good reasons (e.g. — family emergencies,
serious illness). If you know ahead of time that you will be absent, talk to me.
(3) You are welcome to work in groups on any of the homework assignments. However,
you must hand in your own written work. It is not necessary to list your collaborators
must
if they are members of the class. You
reference any books/references
(other than the course texts) you utilize in completing the assignments.
Student Learning Accommodations: If you have already developed a plan through
UVM’s ACCESS office or feel you need accomodations in order to succeed in this course,
please talk to me at the beginning of the semester.
Academic integrity: I expect you to follow the UVM Code of Academic Integrity:
http://www.uvm.edu/~uvmppg/ppg/student/acadintegrity.pdf and Code of Rights and
Responsibilities: http://www.uvm.edu/policies/student/studentcode.pdf. If you are
unsure at any time as to what is permissible, you are responsible for asking me for guidance.
Any suspected violations will be treated seriously and immediately forwarded to the Center
for Student Ethics & Standards for further investigation.
Religious Holidays: Please let me know in writing by the second week of classes any
days during which you will be missing class owing to a religious holiday. There will be no
penalty for such absences and I will make accomodations for you to make up any missed
work.
Remember: Math is fun!
2