Math 413 (Introduction to Combinatorics): (Spring 2010)

Instructor: Alexander Yong ayong@math.uiuc.edu

Lectures: MWF 2:00-2:50pm 345 Altgeld

Office Hours: By appointment only, but in particular, I'm free MW 3:00-4:00pm (right after class, in my office 335 Illini Hall)

Textbook: Brualdi, "Introductory Combinatorics" (5th ed, although 4th ed should also be fine, I'll list the same problems from both editions).

Syllabus: Chapters 1-8 of Brualdi and special topics (time permitting)

Grading: Weekly assignments 30% (I will drop the lowest two assignment grades), Three Midterms 15%+15%+15%, Final Exam 25%. Grades 80%-100% guarantees an A- or above; 70%-80% guarantees B- or above; 60%-70% guarantees C- or above, 50%-60% guarantees D- or above etc. I will maintain grades online through the math department grading system:

Look under "Score reports"

Any missed midterm tests will be dropped and the final exam re-weighted accordingly, provided you have a doctor's note that indicates lack of fitness due to a medical issue (including flu-like symptoms). If a medical concern results in missed final exam, a make-up exam will be offered.

Test dates: All midterms are in class. Test 1: Monday February 15, 2010. Test 2: March 19, 2010. Test 3: April 23, 2010. Final exam: this is regulated by the Non combined guidelines . As our class meets Mondays at 2:00 pm, the final is May 13, 2010 (8:00-11:00AM). The location is AH345 (i.e., our usual classroom).

Miscellaneous: I ask that you attend each class. Exchange numbers with fellow classmates. In particular, collaboration on assignments is encouraged (although I request that you simply acknowledge those who you work with and write up your own solutions). Reading the relevant sections before class to help facilitate learning through discussion, both between you and I, and between other participants and yourself. [Although probably most of the above requests seem like boilerplate for _any_ course, as combinatorics emphasizes learning through problem solving, doing the above is especially important.]

Lecture notes and summaries: I'll post any web accessible materials below.

Lecture 1

Lecture 2

Lecture 3

Lecture 4

Lecture 5

-------------------------------------------------------------------

Here are possible project papers for those who wish to take the 4 hr version of this course (note: first come, first serve)

Total positivity: tests and parametrizations

The Laurent phenomenon

Determinants, paths, and plane partitions

Increasing and decreasing subsequences and their variants

A=B

Trailing the Dovetail Shuffle to its Lair

Walks on Generating Sets of Groups

Tropical mathematics

A direct bijective proof of the hook-length formula

Puzzles and (equivariant) cohomology of Grassmannians

A Combinatorial Formula for Macdonald Polynomials

On the Doubly Refined Enumeration of Alternating Sign Matrices and Totally Symmetric Self-Complementary Plane Partitions

Examples Comparing Importance Sampling and the Metropolis Algorithm (in particular self-avoiding walks)

------------------------------------------------------

Lecture 6

Lecture 7

Lecture 8

Lecture 9

Practice Midterm 1

Practice Midterm 1 with Solutions

Practice Midterm 1 with Solutions

Actual Midterm 1(v1) with Solutions

Actual Midterm 1(v2) with Solutions

Lecture 10

Lecture 11

Lecture 12

Lecture 13

Lecture 14

Chapter 5 in class exercises

Chapter 6 in class exercises

Some MAPLE code for the INTELLIGENT problem in the Chapter 6 in class exercise.

Lecture 15

Lecture 16

Lecture 17

Practice MT 2 and solutions

MT 2 and solutions

Lecture 18

Chapter 7 in class exercises

Maple code to check the Euler-Gauss identity

Lecture 19

Lecture 20

More Chapter 7 in class exercises

Lecture 21

Practice MT3 (for our MT3, look at Q1,2,5)

Practice MT3 with solutions (for our MT3, look at Q1,2,5)

Fall 2009 MT3 with solutions (for our MT3, look at Q1,2,4)

Practice FINAL (for our MT3, look at Q 1,3, 4, 8)

Practice FINAL with solutions (for our MT3, look at Q 1,3, 4, 8)

Fall 2009 FINAL with solutions (for our MT3, look at Q1, 3, 8, 11)

Spring 2010 MT3 with solutions

Lecture 22

HW 9 (chapter 7, due May 5, 7 problems total): Section 7.7 edition 5: Q23, Q25, Q33 ; edition 4: Q41, Q43, Q30(e) AND THE FOLLOWING FOUR EXTRA QUESTIONS:

Q: Find the exponential generating series, and identify the appropriate coefficient, for the number of ways to deal a sequence of 13 cards (from a standard 52 card deck) if the suits are ignored and only the values of the cards are noted.

Q: Show that ex/(1-x) n is the exponential generating function for the number of ways to choose some subset (possibly empty) of r distinct objects and distribute them into n different boxes with the order in each box counted.

Q. Give a bijection between Dyck paths of length 2n and rooted binary trees with n nodes. (6 points)

Q. Prove that the number of binary parenthesizations of a string of n + 1 letters is Catalan. (3 points)

Example: (In the first instance, for example, we use three ways to split the product ")", "." and "*")

(x*x . x)x, x(x*x . x), (x . x*x)x, x(x . x*x), x*x . x*x

More Chapter 7 in class exercises (inhomogeneous linear recurrences)

Lecture 23

Final with Solutions