Combinatorics

Fall 2010

TuTh 1:30-2:50, LART 122; 3 credit hours

Important note about the textbook and the UTEP bookstore

Due to a communication error, textbooks for the course were not ordered for the UTEP bookstore on time. (Thanks to Alex for catching this, and bringing it to my attention.) I placed a new order with the bookstore immediately, and they said the text should arrive by Tuesday or Wednesday, August 24 or 25 (first week of class).

Meanwhile, I have photocopies of the first chapter of the book (which should last us for at least 3 weeks) to give to each of you, free. I will bring these to class the first week of class, and you can also stop by my office if you would like to get it early.

You could, of course, order the book from some other source. You can find all the information you need about it from the publisher's website, and you may order it directly from there, though you could certainly also order it from other sites.

Other resources

Syllabus

Instructor: Dr. Art Duval

Please feel free to come by my office any time during scheduled office hours. You are welcome to come at other times, but in that case you might want to make an appointment, just to make sure that I will be there then. You can make an appointment simply by talking to me before or after class, by calling me at my office or at home, or by sending e-mail.

You may also ask any questions directly via phone or e-mail. If I'm not in when you call, please leave a message on the voice-mail or answering machine with your name, number, and a good time for me to call you back. I will try to respond to your phone or e-mail message as soon as possible.

Prerequisites:

There is no official prerequisite, but there will be some proofs, so some experience with proofs will be helpful, though not required.

COURSE OBJECTIVES:

Upon successful completion of this course, you will be able to discover and prove basic theorems in enumerative combinatorics. You will be moderately proficient applying the techniques of bijections and generating functions in a variety of settings. Some specific topics include: multiplication, addition, and division principles; permutations and combinations; partitions and compositions; inclusion-exclusion; and counting trees and graphs.

You may have seen some of the early topics in a previous course, such as Discrete Math. Here, we will go much further, and look at more elaborate or sophisticated structures (as described above). We will also apply more rigor than in Discrete Math, as you will need to prove some things, and not just compute them. If you have not seen proofs before, this may be a big difference from previous math courses.

On the other hand, there is more problem-solving here than in some other proof-based math courses. In some cases the proof will be easy, once you know what you are trying to prove.

Introduction to Enumerative Combinatorics, Miklos Bona, Chs. 1, 2, 3, 5. We may skip some sections, as announced in class. The textbook is required at all class meetings.

Required Reading: Read each section that we cover in class, both before and after class. Skim the section before class, even if you don't understand it fully, to have some idea of what we'll be doing in class. Read it more carefully after class to clarify and fill in details you missed in class.

Warning: Sometimes, we will not "cover" all the material from a section, but instead focus on a particular aspect of the section. In such cases, I will point out in class (and at this website) which other parts of the section I expect you to read on your own.

GRADES:

Participation (5%)

A significant portion of class time will be devoted to discussions and problem-solving. Your active engagement with the material is required at all times, whether you are presenting, participating in the audience, or working on a problem with a group.

Homework (35%)

Individual homework will be assigned weekly, and will be due Thursdays (with exceptions as announced in class). You are allowed to work together on homework (in fact, I encourage you to do so), but the paper you turn in you must write yourself. Homework is due at the beginning of class (1:30 sharp); if you cannot make it to class, arrange to either deliver the homework to me early, or have someone else bring it to class for you. Your lowest homework score will be dropped.

Exams (15% each)

There will be two in-class, closed-book exams on the following days:

Each exam will cover material from the beginning of the semester, though the second exam will focus more on material since the first exam. Makeup exams can be given only in extraordinary and unavoidable circumstances, and with advance notice.

Final (30%)

The final exam will be comprehensive over all material we discuss in class. The final will be on
Thu., 9 Dec., 4:00-6:45 p.m.

POLICIES:

Academic dishonesty:

It is UTEP's policy, and mine, for all suspected cases or acts of alleged scholastic dishonesty to be referred to the Dean of Students for investigation and appropriate disposition. See Section 1.3.1 of the Handbook for Operating Procedures.

Attendance:

Due to the course structure, attendance is mandatory. There is no particular penalty for missing a particular class, but you cannot get a good participation grade if you miss too many classes. I will usually "excuse" an absence if you tell me about it in advance, or, in cases of emergencies, as soon as possible afterwards.

Drop date:

The deadline for student-initiated drops with a W is Friday, October 29. After this date, you can only drop with the Dean's approval, which is granted only under extenuating circumstances.

I hope everyone will complete the course successfully, but if you are having doubts about your progress, I will be happy to discuss your standing in the course to help you decide whether or not to drop. You are only allowed three enrollments in this course, and students enrolled after Fall 2007 are only allowed six withdrawals in their entire academic career, so please exercise the drop option judiciously.

Courtesy:

We all have to show courtesy to each other, and the class as a whole, during class time. Please arrive to class on time (or let me know when you have to be late, and why); do not engage in side conversations when one person (me, or another student) is talking to the whole class; turn off your cell phone (or at least set it to not ring out loud), and do not engage in phone, email, or text conversations during class.

Disabilities:

If you have, or suspect you have, a disability and need an accommodation, you should contact the Disabled Student Services Office (DSSO) at 747-5148, dss@utep.edu, or Union East room 106. You are responsible for presenting to me any DSS accommodation letters and instructions.

Exceptional circumstances:

If you anticipate the possibility of missing large portions of class time, due to exceptional circumstances such as military service and/or training, or childbirth, please let me know as soon as possible.