Instructor: Brendon Rhoades
Instructor's Email: bprhoades (at) math.ucsd.edu
Instructor's Office: 7250 APM
Instructor's Office Hours: 10:00-10:50am MF and 9:00-9:50am W, or by appointment.
Lecture Time: 2:00-2:50pm MWF
Lecture Room: 216 CENTR
TA: Daniël Kroes and Sittipong `Kuang' Thamrongpairoj
TA's Email: dkroes (at) ucsd.edu abd sithamro (at) ucsd.edu
TA's Office: 6434 APM (Kroes) and 6434 APM (Thamrongpairoj)
TA's Office Hours: 11:00am-1:00pm M and 3:00-5:00pm Th (Kroes) and 4:00-6:00pm Tu and 3:00-5:00pm W (Thamrongpairoj)
Discussion Time: 6:00-6:50pm W (B01), 7:00-7:50pm W (B02), 8:00-8:50pm W (B03), 9:00-9:50pm W (B04)
Discussion Room: 2154 HSS
Final Exam Time: Wednesday, 12/12/2018, 3:00-5:59pm
Final Exam Room: TBA

Syllabus: Available on TritonEd.

Lectures:

9/28: Administrivia. Pigeonhole Principle. Two people have the same number of friends on Facebook. Given 5 points on a sphere, 4 lie on a closed hemisphere. Some number in the sequence 4, 44, 444, ... is divisible by 13.
10/1: Permutations. Multisets and multiset permutations. Strings (words). Sets and subsets. Binomial coefficients: combinatorial definition and formula. Counting words without repeated letters
10/3: Multisets and multiset enumeration. Injections, surjections, bijections. The Bijection Method. The number of nested subsets (A,B) of [n] is 3^n.
10/5: Pascal recursion. Algebraic and combinatorial proofs. Counting valid party placements. Chapter 4. The Binomial Theorem. Some binomial coefficient identities.
10/8: Alternating sums of binomial coefficients. Hockey stick identity. Chu-Vandermonde identity. Formula vs. combinatorial proofs.
10/10: The unimodality of the rows of Pascal's Triangle. Multinomial coefficients and the Multinomial Theorem. Definition of {n choose k} when n is not an integer. Application to Taylor series. Chapter 5. Strong and weak compositions. The number of strong compositions of n with k parts. The number of weak compositions of n with k parts.
10/12: Set partitions. Stirling numbers of the second kind. Bell numbers. Recursion for S(n,k). Function counting; S(n,k) and counting surjections.
10/15: Polynomial identity for S(n,k). Recursion for the Bell numbers B(n). Integer partitions. Ferrers (Young) diagrams.
10/17: Conjugation of Ferrers diagrams. Self-conjugate = (distinct + odd parts). The type of a set partition. Enumeration of set partitions according to type. The Twelvefold Way.
10/19: Chapter 6. Notation for permutations in S_n: functional, two-line, one-line, and cycle. Multiplication (composition) of permutations in functional and cycle notation.
10/22: More on cycle notation. The cycle type of a permutation in S_n. Formula counting permutations with a fixed cycle type.
10/24: Midterm 1.
10/26: Duality between Stirling numbers of the first and second kinds.
10/29: Chapter 7. Principle of Inclusion-Exclusion. Example with avoiding consecutive letters in words. Counting derangements.
10/31: Counting n x n matrices with at least one row or column of zeroes. Formula for S(n,k).
11/2: Introduction to Generating Functions. Counting domino tilings of a 2 x n strip. Domino tilings and the Fibonnaci numbers. Connection to the Golden Ratio.
11/5: Chapter 8. Ordinary generating functions. Formal power series. Ogf's from recursions.
11/7: The Product Rule for ordinary generating functions. Examples. Generating function vs bijective proofs.
11/9: The combinatorial interpretation of 1/(1-A(x)), where A(x) is an ogf. The combinatorial interpretation of B(A(x)) for ogfs B and A. Examples.
11/12: More on ordinary generating function composition B(A(x)).
11/14: Partition identities. Euler's Formula. Odd = distinct.
11/16: Introduction to exponential generating functions. Recursions and egfs. Some examples of egfs of sequences.
11/19: Midterm 2.
11/26: Combinatorial interpretation of multiplication of exponential generating functions. Examples.
11/28: The Exponential Formula. Example. Exponential generating function of the Bell numbers. Graphs and connected graphs.
11/30: Exponential Formula and permutation generating functions. The Compositional Formula. Examples. Ordered Bell numbers and ordered set partitions.



Lecture Notes:

Available on TrionEd. Since TritonEd is not available to some waitlisted students here are the notes to Lectures 1-2.

Homework Assignments:

Available on TritonEd.
Since TritonEd is not available to some waitlisted students here is Homework 1, due 10/5/18.

Midterms:

None Yet!