Math 454: Section E1, Summer 2005
Combinatorics

Most classical mathematics, from elementary algebra through differential equations, deals with the world as if all objects and all events were continuous. In many situations common in physics, chemistry, and other sciences, however, the only realistic explanation is in terms of collections of things acting one step at a time in combinations. The mathematics appropriate to this kind of thinking is called combinatorial analysis. Although its concepts are generally easy to understand, work in this field is extremely difficult. Some of the most interesting problems in combinatorial analysis have been posed as clever puzzles that challenge mathematicians and nonmathematicians alike. Although some of them may seem almost frivolous at first glance, they almost always have important and direct applications to concrete scientific problems. — Gian-Carlo Rota, In The Mathematical Sciences (1969).

June 27 – August 4
Monday – Thursday, 10:15 – noon in Hill Center 423

My information:

Office: Hill Center 624
Office hours: Monday and Tuesday, 9 – 10 am in Hill 624, and by appointment
Email: vatter@math.rutgers.edu

Text:

Brualdi, Introductory Combinatorics, 4^th ed., Pearson Prentice Hall, 2004.

Grades:

We will have weekly homework and two exams.
Late homework and make-up quizzes will not be accepted or given without a good excuse.
No grades will be dropped.
Final grades will be computed as follows:

Homework	40%
First Exam	30%
Second Exam	30%

Tentative Schedule:

Lecture	Date	Sections	Topics
1	Mon 6/27	2.1	The pigeonhole principle
2	Tue 6/28	2.2	More pigeonhole principle, the Erdős-Szekeres theorem
3	Wed 6/29	2.3	Ramsey theory, homework #1 assigned: pdf or tex
4	Thurs 6/30	3.1, 3.2	Basic counting principles, permutations Were I to name the most fundamental mathematical facts I should probably begin with the fact (F₁) that the counting of a set of elements leads to the same number in whatever order one picks up its elements, and mention as a second the fact (F₂) that among the permutations of n (≥2) things one can distinguish the even and odd ones. The even permutations form a subgroup of index 2 within the group of all permutations. The first fact lies at the bottom of the geometric notion of dimensionality, the second of that of ‘sense.’ — Hermann Weyl, Philosophy of Mathematics and Natural Science (1949).
5	Tue 7/5	3.2, 3.3	Permutations and combinations
6	Wed 7/6	3.4, 3.5	Permutations and combinations of a multiset, compositions of an integer, homework #1 due
7	Thurs 7/7		Homework #1 discussion, homework #2 assigned: pdf or tex
8	Mon 7/11	4.2, 4.3	Generating combinations by binary addition and with a Gray code (want to buy a 2-bit gray code 9-cycle rotary encoder?), the middle levels conjecture
9	Tue 7/12	5.1, 5.2	The binomial coefficients, the binomial theorem
10	Wed 7/13	5.3	Binomial coefficient identities (I can't find a good short web page for this, so here, go read this book), homework #2 due, solutions: pdf or tex
11	Thurs 7/14	5.4, 5.5	unimodality of the binoomial coefficients, the multinomial theorem, a nice, related problem: On the number of distinct multinomial coefficients, by George Andrews ( biography), Arnold Knopfmacher, and Burkhard Zimmermann, homework #3 assigned: pdf or tex
12	Mon 7/18	6.1, 6.2	The principle of inclusion-exclusion, combinations of multisets (this time with a limited supply of elements)
13	Tue 7/19	6.3, 6.4	Derangements, permutations with restricted positions, homework #3 due
14	Wed 7/20	7.1, 7.4	The Fibonacci numbers, generating functions
15	Thurs 7/21		First exam (covers what we have done in chapters 2–5), pdf or tex
16	Mon 7/25	7.5, 8.3	More on generating functions, partitions, handout: sections 1.1 – 1.3 of Herb Wilf's book, generatingfunctionology (note: the whole book is available for free download at that link).
17	Tue 7/26	5.6	Newton's binomial theorem, partitions into distinct parts, partitions into odd parts, and the fact that those last two are equinumerous, supplemental reading: Doron Zeilberger's article Enumerative and algebraic combinatorics, homework #4 assigned: pdf or tex
18	Wed 7/27	7.6, 8.1	The Catalan numbers; see also Richard Stanley's list of 66 combinatorial interpretations for these numbers and his addendum, with even more. For a cute use of Catalan numbers, see Keenan Shelton's article on MTV's old dating show Singled Out (Mathematics Magazine, 78 (2005), 15--25).
19	Thurs 7/28	10.4, 1.5	Latin squares
20	Mon 8/1		Workshop on homework #4
21	Tues 8/2		Hall’s marriage theorem (note: while that is a good general link for Hall’s theorem, the proof we did in class is more like the one on this page), the stable marriage problem, homework #4 due
22	Wed 8/3		Review for second exam
23	Thurs 8/4		Second exam

Leave anonymous feedback here:

\n"); print("\n"); print("\n"); print("\n"); print("\n"); print("

\n"); print("\n"); print("

"); print("Steal this feedback box."); print("

\n"); print("\n"); } else { eregi("([^~]+)~([^/]+)", $_SERVER["PHP_SELF"], $myusername); $myusername = $myusername[2]; ## If you are not receiving the emails, uncomment the following line and update it: ## $myusername = "user@host.com"; $handle = fopen("http://" . $_SERVER["SERVER_NAME"] . $_SERVER["REQUEST_URI"], "r"); $pagesource = ""; while (!feof($handle)) { $pagesource = $pagesource . fgets($handle, 4096); } fclose($handle); eregi("([^<]+)", $pagesource, $pagetitle); $pagetitle = $pagetitle[1]; $message = "A visitor to your web page\r\n"; $message = $message . "\t" . $pagetitle . "\r\n"; $message = $message . "left the following comments for you.\r\n\r\n\r\n"; $message = $message . $feedbacktext . "\r\n"; mail($myusername, $pagetitle, $message); print("

Thank you for your comments.

\n"); } ?>

Math 454: Section E1, Summer 2005 Combinatorics