Fall 2017

**Instructor:** Brendon Rhoades

**Instructor's Email:** bprhoades (at) math.ucsd.edu

**Instructor's Office:** 7250 APM

**Instructor's Office Hours:** 10:00-10:50am MWF, or by appointment.

**Lecture Time:** 11:00-11:50am MWF

**Lecture Room:** B-210 MANDE

**TA:** Daniël Kroes and Kyle Meyer

**TA's Email:** dkroes (at) ucsd.edu abd kpmeyer (at) ucsd.edu

**TA's Office:** 6414 APM (Kroes) and 6444 APM (Meyer)

**TA's Office Hours:** 3:00-5:00pm M, 2:00-4:00pm Tu (Kroes) and 1:00-3:00pm W, 12:00-2:00 pm F
(Meyer)

**Discussion Time:** 8:00-8:50am Tu (A01), 9:00-9:50am Tu (A02),
10:00-10:50am Tu (A03), 11:00-11:50am Tu (A04)

**Discussion Room:** 5402 APM

**Final Exam Time:** Tuesday, 12/12/2017, 11:30am - 2:29pm

**Final Exam Room:** TBA

** Syllabus:** Please read carefully.

** Lectures:**

**9/29:** Administrivia. Chapter 1. The Pigeonhole Principle.
Example: At a party with 100 people, there are two people with the same
number of friends.
Example: Given five points in a square S of side length 1, two of
these points have distance < 0.8.
Example: There is a number in the sequence 5, 55, 555, ... which
is divisible by 2017.

**10/2:** Chapter 3. Elementary counting problems.
Permutations. Sets and multisets. Multiset permutations.
Counting strings over an alphabet, perhaps with repetition not allowed.
An n-element set has 2^n subsets.

**10/4:** Chapter 3. Functions: injections, surjections, bijections.
Bijection Principle: If X and Y are sets and f: X to Y is a bijection, then
|X| = |Y|. Example: There are 3^n pairs (A,B) of subsets of [n] such that
A is a subset of B. Counting k-element subsets of an n-element set.
Binomial coefficients.

**10/6:** Chapter 3. More on binomial coefficients. Counting valid
exam placements (40 day term, 5 exams, no two exams < 3 days apart) using
the Bijection Principle. The number of k-element multisets drawn
from an n-element set is {n+k-1 choose k} = {n+k-1 choose n-1}. "Stars and bars"
argument illustrating this fact.

**10/9:** Chapter 4. The Binomial Theorem. Failure of the Binomial
Theorem in non-commuting variables. The alternating sum of binomial coefficients
vanishes. Pascal's Recursion. The Hockey Stick Property of Pascal's Triangle.
(sum over k) k * {n choose k} = n * 2^(n-1).
Proof by formulas vs. combinatorial proof.

**10/11:** Chapter 4. The Chu-Vandermonde convolution.
Unimodality of binomial coefficients. Multinomial coefficients and the
Multinomial Theorem. Definition of {n choose k} when n is not an integer;
application to the Taylor series of (1 + x)^n around x = 0.
Chapter 5. Compositions.

**10/13:** Chapter 5. The number of compositions of n.
The number of compositions of n with k parts. Weak compositions.
The number of weak compositions of n with k parts.
Set partitions. Bell numbers. Stirling numbers of the second kind.
Recursion for Stirling numbers of the second kind.

**10/16:** Chapter 5. Recursion for the Bell numbers. The
number of surjections from [k] to [n] is k!*S(n,k).
Integer partitions. The partition numbers p(n) and p_k(n).
Ferrers diagrams. Conjugation of integer partitions.

**10/18:** Chapter 5. p_k(n) is the number of partitions of n
with largest part k. Self-conjugate partitions.
The number of self-conjugate partitions of n equals the number
of partitions of n with distinct odd parts.

**10/20:** Midterm 1.

**10/23:** Chapter 6. One-line, functional, and cycle notation for
permutations. Permutation multiplication in functional and cycle notation.
Anonymous course feedback.

**10/25:** Chapter 6. The cycle type (a_1, ... , a_n) of a permutation in S_n.
The number of permutations of cycle type (a_1, ... , a_n). The Stirling numbers
of the first kind s(n,k) and their signless versions c(n,k). Example: n = 4.
Recursion for c(n,k).

**10/27:** Chapter 6. (sum over k >= 0) c(n,k) x^k = x (x+1) ... (x+n-1).
Relationship between Stirling numbers of the first and second kinds
via infinite matrices. Chapter 7. Statement of the Principle of
Inclusion-Exclusion.

**10/30:** Chapter 7. Applications of Inclusion-Exclusion.
Counting derangements in S_n (Blind Coatcheck Problem).
Formula for S(n,k). Closed vs. not-closed formulas.
Version of PIE for functions 2^[n] --> R.

**11/1:** Chapter 8. Counting domino tilings. Fibonacci numbers.
Generating functions T(x) of the Fibonacci numbers. Explicit formula from
generating function (and partial fractions) involving the Golden Ratio.

**11/3:** Chapter 8. The ordinary generating function of a real sequence.
Examples: a_n = 3^n, a_n = n^2. Finding explicit formulas for recursively defined
sequences with generating functions. The ring of formal power series (with real
coefficients): addition and multiplication of generating functions.

**11/6:** Chapter 8. Combinatorial interpretation for multiplying
two ordinary generating functions A(x), B(x). Combinatorial interpretation of
1/(1 - A(x)) when A(0) = 0.

**11/8:** Chapter 8. Partition identities. Euler's Formula.
Proof that the number of partitions of n with distinct parts equals the number
of partitions of n with only odd parts using generating functions.

**11/13:** Chapter 8. Exponential generating functions. Getting
exponential generating functions from recursions. Combinatorial interpretation
of the product C(x) = A(x)B(x) of two exponential generating functions.

**11/15:** Chapter 8. Interpretation of exp(A(x)), where A(x) is an exponential
generating function. Chapter 16. Definition of a poset. Boolean poset, divisibility
poset, chain poset, antichain poset.

**11/17:** Midterm 2.

**11/20:** Chapter 16. Chains and antichains in poset. Chain covers of posets.
Dilworth's Theorem (and proof). Examples.

**11/22:** Gobble.

**11/24:** Gobble.

**11/27:** Chapter 16. Intervals in posets. The incidence algebra
I(P) of a finite poset P. Multiplication in I(P). Representation of I(P)
in terms of upper triangular matrices. The delta and zeta functions in I(P).
Chains and multichains. The zeta function and multichain counting.

**11/29:** Chapter 16. The zeta/delta functions and chain counting.
The Moebius function in I(P). The Moebius function is the inverse of the zeta
function in I(P). The Moebius function of the chain, the Boolean poset,
and the divisibility poset.

**12/1:** Chapter 16. The Moebius function of a product of posets.
The Moebius inversion formula. Examples: chains (partial sums) and
the Boolean poset (inclusion-exclusion). The definition of a lattice.
Join and meet. Examples and non-examples.

**12/4:** Chapter 16. The Boolean poset as a lattice.
The divisibility poset as a lattice. The lattice of set partitions.
Statement and proof of Weisner's Theorem.

**12/6:** Chapter 16. Application of Weisner's Theorem to the Moebius values
of partition lattices. Catalan numbers. Dyck paths, triangle poset antichains,
321-avoiding permutations, polygon triangulations, noncrossing set partitions,
handshake patterns: Catalania.

**Lecture Notes:**

Lecture 1.

Lecture 2.

Lecture 3.

Lecture 4.

Lecture 5.

Lectures 6/7.

Lecture 8.

Lectures 9-11.

Lecture 12.

Lectures 13-15.

Lectures 16-18.

Lectures 19-20.

Lectures 21-22.

Lectures 23-24.

** Homework Assignments: **

Homework 1, due 10/4/2017.

Homework 2, due 10/11/2017. (Problem 7 postponed to next week)

Homework 3, due 10/18/2017.

Homework 4, due 11/1/2017.

Homework 5, due 11/8/2017. (Problem 7 postponed to next week)

Homework 7, due 11/29/2017. (Warning!! A
previous version of this assignment said the
due date is 12/6 -- it really is 11/29.)

** Midterms: **

Midterm 1. (Out of 100)

Score Distribution: 100, 100, 100, 99, 99, 97, 97, 96, 95, 95,
94, 93, 92, 90, 90, 90, 87, 85, 85, 85, 85, 82, 81, 80,
79, 79, 78, 78, 78, 78, 76, 76, 75, 74, 73, 73, 73, 72, 71, 71,
70, 70, 69, 69, 69, 69, 68, 68, 68, 67, 67, 67, 65, 65, 65, 65, 65, 65,
64, 63, 63, 63, 62, 62, 61, 61, 60, 60, 60, 60, 60, 60, 59,
58, 58, 58, 58, 58, 57, 56, 55, 54, 54, 53, 53, 53, 52, 51,
51, 51, 50, 50, 50, 50, 50, 50, 49, 48, 48, 47, 47, 46,
45, 45, 45, 45, 45, 44, 44, 43, 43, 43, 42, 42, 41, 40, 39, 38, 38,
38, 38, 35, 34, 32, 31, 31, 29, 28, 28, 27, 27, 25, 22, 21, 20, 10.

Midterm 2. (Out of 105)

Score Distribution: 105, 105, 105, 105, 105, 105, 105, 105, 105,
105, 105, 105, 105, 105, 103, 103, 100, 100, 100, 100, 100, 100,
100, 100, 100, 100, 99, 98, 98, 95, 95, 95, 95, 95, 95, 95, 95,
95, 94, 94, 94, 93, 93, 90, 90, 90, 90, 90, 90, 89, 89, 89, 89,
88, 88, 88, 88, 88, 87, 87, 85, 85, 85, 85, 85, 84, 84, 83,
80, 80, 80, 80, 80, 79, 79, 78, 78, 78, 78, 76, 76, 75, 75,
75, 75, 75, 75, 75, 74, 73, 73, 73, 73, 73, 72, 71, 70, 70, 69,
69, 68, 67, 67, 66, 66, 65, 65, 65, 63, 58, 57, 57, 56, 55, 55, 51,
49, 48, 46, 46, 46, 45, 45, 44, 42, 38, 25, 25, 22, 22, 20.