Welcome to Math 3250: Combinatorics, this Spring 2019! Today is .

Actual Schedule

See also UConn Calendar for Spring 2019 for important deadlines and other dates.

Office hours

Final Exam (May 6-12)

3:30-5:30pm on Monday in the usual classroom

• The length and structure of the final exam is the same as Exam 1 and Exam 2. Topics:
  • Chapter 1: Pigeon-hole principle. Make sure you understand the logic behind the proof of Theorem 1.1 and Theorem 1.4, and you will be OK.
  • Chapter 2: Using induction to help prove problems mentioned in this list.
  • Chapter 4: Using the binomial theorem computation to help solve problems mentioned in this list.
  • Chapter 3 and 5: Counting problems with a focus on binomial coefficients, weak composition, composition, set partition, and integer partition (from Chapter 5).
  • Chapter 8: Generating function and recurrence relation with a focus on binomial coefficients, weak compositions, integer partitions, noncrossing set partitions (and other Catalan objects), and Fibonacci-like recurrences.
  • Chapter 16: Lattices with a focus on the posets of integer partitions, Boolean algebra, order filters, integers, set partitions, and noncrossing set partitions.
• Materials from Exam 2: Week 14 Problems (also extra problems for Exam 2), see KEY
• Lattices:Week 13 problem set, see KEY
• The rest: Week 15 Problems (not collected): problems, see KEY

CURRENT: Week 15 (Apr 29 – 3)

• Mon Presentations by Gabe, Tyler and Peter, and Alex; continue lecture Sec 16.2 mobius function part B
  • Be prepared to present your thoughts on Week 14 Problems (five problems) except no. 1
• Wed Start lecture Sec 16.3 (part b) mobius function for lattices
  • Be prepared to present your thoughts on Week 14 Problems (five problems) except no. 1
• Due on Friday If you lose any points on the exam, you can earn up to half points back by submitting problems from Week 14 Problems (also extra problems for Exam 2) and presenting (either in class or during office hours):

  1. My answers to the original problems 2 through 5 are in the sample exam answer key, so I have put new, related problems in place of the actual exam problems. Problem 1 and the first extra credit questions have not been changed.

  2. You may discuss problems with your other people, but please indicate your source if you get significant help. (It won’t affect your score.) Your rewrites should be perfect. You can receive up to half the points you missed on any problem. Ideally, I will look at your rewrite, note that it’s correct and complete, and give you half of all the points you missed.

  3. Present at least one of these problems during class. If you talk to me ahead of time, you can also make an appointment to present to me in my office.

Past: Week 14 (Apr 22 – 26)

• Mon Continue lecture on dominance order for integer partitions Sec 16.3 lattices
• Wed Start lecture on non-crossing set partitions Sec 16.3 lattices
• Fri Lecture Sec 16.2 mobius function part B

Past: Week 13 (Apr 15 – 19)

• Mon Continue Sec 16.2 lecture: incidence algebra, delta function, zeta function
• Wed Work on HW and lecture on Sec 16.3 lattices
  • Bring questions from homework
• Fri Lecture meet-semilattice and dominance order for integer partitions Sec 16.3 lattices
  • Due Submit (handwritten) Week 13 problem set taken from the last two problems from the previous problem set, see KEY

Past: Week 12 (Apr 8 – 12)

• Mon In class: Presentation by Alex and Peter, then Continue Sec 16.2 lecture: incidence algebra, delta function, zeta function
  • HW: Be prepared to present your thoughts on problem 2, 4, and 6 from Week 11 Problem Set and exam practice problems.
• Wed In-class: Review for exam
  • Due Submit (handwritten) problems 1,2,3,4abc,7 of Week 11 Problem Set, see KEY. Note: Problems 5,6 are moved to the next problem set, and problems 4de (correct version) will be optional problems on the next future problem set.
• Second Exam on Friday
  • Most problems are taken directly from Practice problems for Exam 2, see KEY

Past: Week 11 (Apr 1 – 5)

• Monday, April 1 In class: Continue Sec 16.2 lecture: incidence algebra, delta function, zeta function

• Wed In class: presentations problems 2, 3 by Alex, Peter; Continue Sec 16.2 lecture: incidence algebra, delta function, zeta function
  • HW: Be ready to present and discuss Week 11 problem set.
• Fri In class: Continue Sec 16.2 lecture: incidence algebra, delta function, zeta function

Past: Week 10 (Mar 25 – Mar 29)

• Mon In class: Presentations on this week’s problem set (problems 1 by Gabe, 2 by Alex and Peter, and 4 by Sharon); Lecture the rest of Chapter 8 (bell numbers EGF)
  • HW: Be prepared to present as many problems as possible from Week 10 Problem Set (See link under Wed).
  • Recommended HW: If you did not earn full credit on the first problem on the exam, you should read the first few examples in Examples of proofs by induction by K. Conrad and also come see me outside of class to confirm that you understand how to write a proof by induction.

• Wed In class: Star Sec 16.1: poset.

• Fri In class: Finish Sec 16.1. Start Sec 16.2: order filters, intervals, algebra of upper triangular matrices, incidence algebra.
  • Due (collected) Submit all except 4. Harmonic Numbers Week 10 Problem Set (Bona Sec 8.1.1-8.1.2, 8.2.1-8.2.2): PDF, tex. Please edit the source code. To submit, please put your modified .tex file to a new Overleaf project called ‘Combinatorics Week 10 Problem Set by YourName’ and share it with my UConn email.

Past: Week 9 (Mar 18 – 22) SPRING BREAK

Past: Week 8 (Mar 11 – 15)

Lecture notes on Sec 8.1.2.1 Catalan numbers (Week 7 Mon and Week 8 Mon, Wed)

• This week, if you earned less than 80% (4 points) on exam 1, you can earn up to half points back by submitting rewrites and scheduling an office hour meeting:

  1. Due the end of Friday Rewrite any problem on which you lost any point (handwritten or typed). Rewrite the entire answer to each part of problem where you want extra points, even if it means copying things you already did correctly. Double check your answers (with friends or however). You may discuss problems with your classmates or others, but please indicate your source if you get significant help. (It won’t affect your score.) Your rewrites should be perfect. You can receive up to half the points you missed on any problem. Ideally, I will look at your rewrite, note that it’s correct and complete, and give you half of all the points you missed.

  2. Present at least half of these problems to me during office hours this week. Make an appointment for Monday 2:15-5:30pm, Wednesday right after class or after 6:35pm, or Friday after 2:15pm. You can make an appointment to present a problem even if you are not done with your rewrite.

• Mon In class: Presentations on this week’s problem set (The product formula; No part divisible by three; Combinatorial proof); Continue Bona Sec 8.1.2.1 The Catalan numbers and its recurrence relation, using triangulations of polygons. Lecture notes on Sec 8.1.2.1 Catalan numbers (Week 7 Mon and Week 8 Mon, Wed)
  • HW: Be prepared to present as many problems as possible from Week 8 Problem Set (See link under Wed).
• Wed In class: Finish Bona Sec 8.1.2.1 The Catalan numbers, its generating function (using its recurrence relation), and explicit formula (using its generating function). Lecture notes on Sec 8.1.2.1 Catalan numbers (Week 7 Mon and Week 8 Mon, Wed)
  • Due (collected) All problems (except 2 and 5) from Week 8 Problem Set (Bona Sec 8.1.1 and 8.1.2): PDF, tex. See key for problem 4.
• Fri In class: Exponential generating functions (Bona 8.2) with the set partitions as motivation

Past: Week 7 (Mar 4 – 8)

• Mon In class: Bona Sec 8.1.2 Products of generating functions part I: The product formula
  • Recommended HW to complete by Mon:
    • Read the three examples in Section 8.1.1,
    • watch Lecture videos by TheTrevTutor: Generating Functions and Recurrence Relations and Generating Functions,
    • watch Lecture video by Jim Fowler for computing a formula for the Fibonacci numbers
• Wed In class: Bona Sec 8.1.2 part II: Generating functions for integer partitions
  • Recommended HW to complete by Wed: Read Example 8.6, 8.7, and 8.8.
• Fri In class: Introduce Bona Sec 8.1.2.1 The Catalan numbers via parentheses grouping, full binary trees, and triangulations. Over 200 interpretations available in CATALAN ADDENDUM and Exercises on Catalan and Related Numbers
  • Recommended HW to complete by Fri: Review Chapter 8 pages covered in the past week. Attempt Week 8 Problem Set

Past: Week 6 (Feb 25 – Mar 1)

First Exam (on Chapters 1-5, but not including Sec 5.2 set partitions and surjections)

• Study Guide:

  • Week 6 Sample Exam 1, see key
  • Do problems from Problem Sets (Week 2 through Week 5) that you did not submit. Review the ones you submit
    • You are welcome to see me during office hours to check your work
  • Practice the quick check questions from each section
  • Attempt examples given in each section then read the book’s solutions.

1. Mon In class: Finish Sec 5.2 Set Partitions and bell numbers; Students worked on Sample Exam 1 problems on the board;

2. Wed In class: Bona Sec 8.1.1 of Bona (recurrence relations and generating functions), see also generatingfunctionology 2nd edition by Herbert Wilf

3. Fri Exam

Past: Week 5 (Feb 18 – 22)

• Mon In class: Presentations entire class
  • HW: Be prepared to present as many problems as possible from Week 5 Problem Set (See link under Wed).
• Wed In class: Start Sec 5.3 Integer Partitions
  • Due (collected) All problems from Group Week 5 Problem Set: PDF, tex. Please edit the source code. To submit, please put your modified .tex file to a new Overleaf project called ‘Combinatorics Week 5 Problem Set by Student1, Student2, Student3 and Student4’ and share it with my UConn email.
• Fri In class: Finish Sec 5.3 Integer partitions; Start Sec 5.2 Set Partitions

Past: Week 4 (Feb 11 – 15)

• Mon In class: presentation of problems 3,7, and 10 from Week 4 Problem Set. Finish Sec 4.1, all theorems except Thm 6.
  • HW: Be prepared to present as many problems as possible from Week 4 Problem Set (See link under Wed).
• Wed In class: Sec 4.2 Multinomial Theorem, 4.3 Generalized binomial coefficient and theorem
  • Due (collected) Problems 2 (Interns), 5 (Combinatorics class), 7 (Inequality), 11 (Write your own) and 12 (Miscellaneous) from Week 4 Problem Set: PDF, tex. Please edit the source code. To submit, please put your modified .tex file to a new Overleaf project called ‘Combinatorics Week 4 Problem Set by YourName’ and share it with my UConn email.
• Fri In class: Sec 5.1 Compositions
  • Recommended HW by Fri: Attempt Problems 1-4 from Week 5 Problem Set with your team. Read Chapter 4.

Past: Week 3 (Feb 4 – 8)

(Monday, Feb 4: Last Day to drop without a W, to place courses on Pass/Fail)

• Mon In class: presentations from Week 3 Problem Set, and Sec 3.2 (part A and half of part B)
  • HW: Be prepared to present as many problems as possible from Week 3 Problem Set (See link under Wed).
• Wed In class: Sec 3.2 part B and Sec 3.3
  • Due (collected) Problem 1. Recurrence Relation (please copy and the sample solution format for this one), Problem 2. Polygon, Problem 4. Divisible by three, Problem 8. Sandwich, Problem 9. Connecticut, 10. Alternating Parity, and Miscellaneous section from Week 3 Problem Set.
    • Note: for Problems 8. Sandwich and Problem 9. Connecticut, only a brief explanation (for example, referring to a theorem from Chapter 3) is expected.
• Fri In class: Finish Sec 3.3 Choice Problems and the first two theorems of Sec 4.1.
  • In-class Quiz Memorize the definition of injection and surjection, and be able to prove that a given map (similar to bijectios given in class) is a bijetion.
  • Recommended HW by Fri: Attempt Problems 1-5 (only) from Week 4 Problem Set. Do the examples and quick check in Chapter 3.

Past: Week 2 (Jan 28 – Feb 1)

• Mon In class: presentations from Week 2 Problem Set, lecture Sec 2.1
  • HW: Be prepared to present your (possibly incomplete) thought process from Week 2 Problem Set (see link under Wed)
  • Optional HW by Mon: read Sec 1.1 and 1.2 of the textbook.
• Wed In class: lecture Sec 2.1, Induction review activity version A, version B, and version C, lecture Sec 2.2 (strong induction).
  • Due (collected) Problems 2 (Wednesdays), 5 (Swimming), 6 (Polynomial degrees) , and 10 (Your own problem) from Week 2 Problem Set due via Overleaf.
  • Sample solution in Overleaf: Sample Problem Set Solution
  • Optional HW by Wed: read Sec 2.1 Weak Induction of the textbook
• Fri In class: lecture 3.1
  • Optional HW by Fri: Read Chapter 2, attempt Week 3 Problem Set

Past: Week 1 (Jan 23 – 25) short week

• Wed In class: Introduction, Sec 1.1 Pigeon-hole Principle, Thm 1.1, Exercise 1, Example 1.2.
• Fri In class: Sec 1.2 Pigeon-hole principle, general version
  • Due (collected) Week 1 HW: Survey and LaTeX practice, HW Overleaf template before the beginning of class.
    • First, create an account on Overleaf
    • Go to the above link
    • Click on the upper-left button called ‘menu’
    • Click on ‘Copy Project’ and rename the project so that your name is on the project’s name
    • Make all the requested edits
    • To submit, click on the share button and share your project with me by entering my UConn email. Please give me a Read and Edit permission (so that I can write a comment directly on your project)
    • You may continue to edit your project even after your share it with me.
  • Optional HW: Read Sec 1.1 and 1.2, attempt Week 2 Problem Set, read the syllabus