Spring 2010 : Math 453 Combinatorics

Math 453: Combinatorics

Instructor: Hemanshu Kaul

Office: 234B, Engineering 1
Phone: (312) 567-3128
E-mail: kaul [at] math.iit.edu

Time: 3:15pm, Tuesday & Thursday.
Place: 124, Engineering 1 Bldg.

Office Hours: 12-1pm Tuesday and 1-2pm Thursday, walk-ins, and by appointment. Emailed questions are also encouraged.

Course Information:

The Course Information Handout has extensive description of the course - topics, textbook, student evaluation policy, as well as other relevant information. Read it carefully!

What is this course really about? Required reading.

The official course syllabi: MATH 453.

Advice for students:

Excellent advice by Doug West on how to write homework solutions for proof-based problems.

On a more abstract note, here is a discussion of Language and Grammar of Mathematics - which is what you are starting to learn in a course like this.

Excellent advice for math majors and graduate students, by Terry Tao, 2006 Fields medallist. Required reading.

Class Announcements:

Thursday, 4/8 : Exam #2 is two weeks away. See below for syllabus, etc.
Tuesday, 3/2 : HW # 7 has been uploaded.
Thursday, 2/18 : Exam #1 is two weeks away. See details below.
Friday, 1/29 : Updated HW#3 has been uploaded.
Friday, 1/14 : Corrected HW#2 has been uploaded. A minor typo in Supplementary problem #2 has been fixed.
Thursday, 1/14 : HW#1 has been uploaded.

Tuesday, 1/12 : Check this webpage regularly for homework assignments, announcements, etc.

Examinations:

Exam # 1 : Thursday, March 4th . Topics: Based on topics covered up to and including Thursday, February 18th [total 12 lectures].
Exam # 2 : Thursday, April 22nd . Topics: Based on topics covered from and including February 23th and up to and including Thursday, April 8th [total 11 lectures].
Final Exam : Wednesday, May 5, 8am - 10am. Topics: Everything done during the semester with slightly more emphasis on topics covered after April 8th.

Homework Assignments:

Reading HW : Be sure to read and understand all the examples not done in class from the sections discussed in class before attempting the HW.
Of course, feel free to consult with me on any of these examples that you have difficulty with.

Tuesday, 1/12 : Read Chapter 1.

Homework #1: Due Thursday, 1/21. .

Homework #2: Due Thursday, 1/28. .

Homework #3: Due Thursday, 2/4. .

Homework #4: Due Thursday, 2/11. .

Homework #5: Due Thursday, 2/18. .

Homework #6: Due Thursday, 2/25. .

Homework #7: Due Thursday, 3/18. .

Homework #8: Due Thursday, 3/25. .

Homework #9: Due Thursday, 4/1. .

Homework #10: Due Thursday, 4/8. .

Homework #11: Due Thursday, 4/15. .

Homework #12: Due Thursday, 4/29. .

Class Log :

Tuesday, 1/12 : Product rule, counting by defining a bijection, sum rule, permutation, factorial, r-permuation of an n-set, P(n,r), r-combination of an n-set, C(n,r), Relation between C(n,r) and P(n,r), formula for binomial coefficient, examples. (From Sections 2.1, 2.2, 2.3, 2.5, 2.6, 2.7, and elsewhere)
Thursday, 1/14 : A recursive formula for C(n,r) with a combinatorial proof, Pascal's Triangle and why its true, r-permuation of an n-set with replacement, P^R(n,r), r-combination of an n-set with replacement, C^R(n,r), Formula for C^R(n,r) with proof, Balls and urns models - 6 different possibilities based on distinct and non-distinct balls/ urns, empty/ non-empty urns, relations to the Stirling number of the second kind, Partitions of positive integers. (From Sections 2.7, 2.9, 2.10, and elsewhere)
Tuesday, 1/19 : Occupancy problems with specified distribution, multinomial coefficient and its formula, discrete probability - definition, properties, examples (why assumption of equal likelyhood is important), number of distinguishable permutations of n objects of k types and why its equal to the multinomial coefficient, Examples, Binomial theorem, Theorems proved using combinatorial arguments, Discussion of a HW problem using combinatorial argument. (From Sections 2.11, 2.8, 2.13, 2.14, and elsewhere)
Thursday, 1/21 : Quiz#1 and discussion of its solutions; Pigeonhole principle and its different versions, Examples based on PP and averaging principle, Strong form of PP, Sequences, Subsequences, Increasing and decreasing sequences, Erdos-Szekeres Theorem. (From Section 2.19, and elsewhere)
Tuesday, 1/26 : Completion of proof of Erdos-Szekeres Theorem, Modeling the R(3,3) puzzle as a graph-theoretic problem, Definitions and examples of graph, vertices, edges, degree, complete graph (K_n), (p,q) Ramsey property in graph-theoretic language, Definition and examples of R(p,q), How to determine R(3,3), R(2,n), etc., Ramsey's Theorem and the recursive bound on R(p,q). (From Section 2.19, and elsewhere)
Thursday, 1/28 : Quiz#2 and discussion of its solutions; Completion of the proof of Ramsey Theorem and the recursive bound on R(p,q), A binomial bound on R(p,q), Generalized Ramsey numbers for k-subsets colored with r colors R_r(p_1,...,p_r;k), Application to Erdos-Szekeres Theorem for convex m-gon in a large enough ensemble of points on the plane, Definition and examples of Convex sets, convex polygons, Convex Hull, Elementary convex properties of points on the plane. (From Section 2.19, and elsewhere)
Tuesday, 2/2 : Completion of proof of E-S theorem on finding convex m-gons in large enough arbitrary collections of points on the plane, Application to monochromatic solutions of x+y=z (Schur's Theorem), recurrence relations, simple examples and their solutions. (From Section 2.19, 6.1, and elsewhere)
Thursday, 1/28 : Quiz#3 and discussion of its solutions; Examples of Recurrence relations - Number of regions created by n lines in general position in the plane, Fibonacci recurrence and its variants, Number of ordered partitions of n with parts of size atmost 2, Lucas Numbers, Number of binary sequences of length n with no two consecutive 1s, Derangements and counting them. (From Section 6.1, and elsewhere)
Tuesday, 2/9 : An order two recurrence relationship for D_n and analysis of its solution, Substitution method applied to couple of examples including D_n, Characteristic Equation method, Characteristic equation and roots of a linear constant coefficient homogenous recurrence, Solving such a recurrence using its distinct roots, Examples including Fibonacci series, How to find solutions when the characteristic equation has repeated roots. (From Section 6.1, 6.2, and elsewhere)
Thursday, 2/11 : Quiz#4 and discussion of its and HW#4 solutions; [Missed: Example for solving a linear homogenous recurrence with repeated characteristic roots, see page 366]; General solution of a nonhomogenous linear recurrence, Proposition for finding a particular solution of a nonhomogenous linear recurrence with nonhomogenous terms of the form Polynomial(n)c^n where c is a characteristic root and applied to the regions among n lines example, Generating function for a sequence as a formal power series, Coefficient extractor of a formal power series. (From Sections 6.2, 6.3, and elsewhere)
Tuesday, 2/16 : Generating Function Method - Generating function and Exponential Generating Function for a sequence as a formal power series, Coefficient extractor of a formal power series, Regions among lines non-homogenous recurrence solved using GF, power series for (1-x)^(-k), Linear homogenous recurrence example solved using partial fractions, Catalan number recurrence using the number of ways to divide a convex polygon with n+2 sides into triangular regions with non-crossing diagonals, derivation of the recurrence and its solution using GF, Formula for product of two GFs. (From Section 6.3, and elsewhere)
Thursday, 2/18 : Quiz#5 and discussion of its and HW#5 solutions; Solving the Catalan number recurrence to get the formula, Extended Binomial Theorem, Catalan numbers as number of ballot paths of length 2n from (0,0) to (n,n). (From Sections 6.3, 6.4, 5.4, and elsewhere)
Tuesday, 2/23 : Solving the Derangement recurrence using generating functions - OGF leads to an differential equation, Exponential Generating function leads to a simple solution, Sum, Product, derivative and integral of Generating functions, How a generating function encodes all the values of a counting problem, Generating function for choosing out of n items, Generating function for placing n non-distinguishable balls into k distinguishable urns, Interpreting the counting problem underlying a given generating function. (From Sections 6.3, 6.4, 5.1, 5.2, and elsewhere)
Thursday, 2/25 : Quiz#6 and discussion of its solutions; Directly deriving a generating function for a counting problem - examples related to integral solutions of linear equations (ball in bins problems). (From Section 5.3, and elsewhere)
Tuesday, 3/2 : Theorem on enumerators for choosing indistinguishable items from different types and how that can be modified: exponents = number of items, coefficient = number of ways to choose those items, Example when the coefficient are not 1, Applying OGFs to find the Sicherman dice, 8 properties of combining OGFs including convolutions, examples of finding sums using OGF properties. (From Sections 5.1, 5.2, 5.3, and elsewhere)
Thursday, 3/4 : EXAM # 1. Exam #1 solutions discussed on 3/18, Thursday.
Tuesday, 3/16 : Review of how to formulate OGF using example of labeled graphs on n vertices, Using properties of OGF to evaluate combinatorial sums - examples using derivatives, even/ odd functions, convolution formula, Vandermonde convolution, Exponential Generating Functions - definition and examples of how to formulate them, EGFs of k-permutations, n-digit numbers with conditions on digits allowed, Theorem on exponential enumerators for distinguishable permutations from different types of objects with proof, How to use an EGF and exponential function to find formula for counting problem. (From Sections 5.4, 5.5, and elsewhere)
Thursday, 3/18 : Quiz#7 and discussion of its solutions; Distribution of Exam#1 and discussion of its solutions and student performance. Deriving a formula for S(n,k) using EGF, Binomial convolution and its relation to EGF, Binomial inversion formula. (From Section 5.5, and elsewhere)
Tuesday, 3/23 : Binomial inversion formula and its application to closed formula and EGF for derangements; p(n) Partitions of an integer - overview of OGFs under various restrictions, p_k(n) Partitions of n into parts of size at most k, partitions with largest part k, a formula for p_3(n), Statement of asymptotic formula for p_k(n) leading to a good lower bound on p(n), Ferrers Diagram of a partition of n, Using FD to get a bijection between partitions with largest part k and partitions into k parts, bijection between partitions into distinct parts and partitions into odd parts. (From elsewhere)
Thursday, 3/25 : Quiz#8 and discussion of its & HW#8 solutions; OGF for integer triangles using a Ferrers Diagram bijection with Partitions with parts of size 2. 3. or 4 with atleast one part of size 3, Euler's identity giving two OGFs for the self-conjugate partitions, Bijection between partitions into distinct odd parts and self-conjugate partitions. (From elsewhere)
Tuesday, 3/30 : Completion of the proof of Euler's Identity giving two OGFs for the self-conjugate partitions; Principle of Inclusion-Exclusion - underlying idea, statement, proof, application to number theory: Euler's function counting number of integers co-prime to n. (From Section 7.1 and elsewhere)
Thursday, 4/1 : Quiz#9 and discussion of its & HW#9 solutions; A more general framework for Principle of Inclusion and Exclusion using functions F(S) and G(S), Formula for number of elements satisfying exactly the given subset of properties, Simplification of the formula when G(S) takes the same value for all S with i elements, Application of PIE to find a formula for S(n,k). (From Sections 7.1, 7.2, and elsewhere)
Tuesday, 4/6 : How to use PIE to derive combinatorial proofs of identities with alternating sums, PIE applied to find the formula for number of derangements, and number of permutations with exactly one fixed point, Permutations with restricted positions: Permutation matrices (are equivalent to permutations), Forbidden boards, Applying PIE to find the number of permutation matrices that remain true to a given forbidden board, independent positions on a forbidden board and their relation to placing non-attacking rooks. (From Sections 7.1, 7.2, and elsewhere)
Thursday, 4/8 : Quiz#10 and discussion of its & HW#10 solutions; further discussion with examples of PIE applied to find permutations that are true to a forbidden board, A recursion for finding the number of ways to choose k indepenedent positions on a forbidden board, rook polynomial. (From Sections 7.1, 7.2, and elsewhere)
Tuesday, 4/13 : Polya counting - counting under symmetries, distinct 2-colorings of a 4-bead necklace under rotational symmetries, Binary relation, Equivalence relation, Equivalence classes, Permutations as bijections, compsitions of two permutations, properties of compositions of permutations - closure, associativity, Identity, Inverse, Group of permutations, the symmetric group, Dihedral group of 8 elements - symmetries of the square (4 rotational and 4 reflection), Expressing the symmetries as permutations. (From Sections 8.1, 8.2, and elsewhere)
Thursday, 4/15 : Quiz#11 and discussion of its & HW#11 solutions in detail - intricate applications of Principle of Inclusion-Exclusion.
Tuesday, 4/20 : Dihedral group of order 2n - n rotations and n reflections of corners of a regular n-gon, How to get an equivalence relation S on D induced by G= group of permutations of D, Burnside's lemma with example, C(D,R) and how to define permutations on it, Given a permutation of G how to dine a permutation in G* (group of permutations of C(D,R)), How to get an equivalence relation S* on C(D,R) induced by G* which is same as our original definition of equivalent colorings of D, Applying Burnside's lemma to count the number of equivalence classes of C(D,R) under S* that is the number of distinct colorings of D under symmetries, illustrated by the colorings of corner of a square. (From Sections 8.2, 8.3, 8.4, and elsewhere)
Thursday, 4/22 : EXAM # 2. Exam #2 solutions discussed on 4/27, Tuesday, and 4/29, Thursday.
Tuesday, 4/27 : Cycle decomposition of a permutation, Simplified Polya's Theorem for counting number of distinct colorings, Cycle index of a permutation group, Number of distinct colorings using the cycle index of G, Examples including cycle index of the group of symmetries of the tetrahedron and the number of its distinct colorings. Distribution of Exam#2 and discussion of its solutions and student performance. (From Sections 8.4, 8.5, and elsewhere)
Thursday, 4/29 : Quiz#12 and discussion of its & HW#12 solutions in detail. Continuation of discussion of Exam#2 solutions. A brief introduction to Orthogonal Latin squares. (From Chapter 9)