Jay Pantone

Assistant Professor
Marquette University

jay.pantone@marquette.edu


Math 4670 / 5670 – Combinatorics

Spring 2024, Marquette University

Bulletin description: Permutations and combinations, recurrence relations, inclusion and exclusion, Polya's theory of counting, graph theory, transport networks, matching theory. Prereq: MATH 2100 or MATH 2350.

  • Lectures:
    M, W, F 9:00am - 9:50am
    Cudahy Hall 120
  • Office Hours:
    Monday, 2:30pm - 3:30pm
    Wednesday, 2:00pm - 3:00pm
    Thursday, 10:30am - 11:30am
    Cudahy Hall 307 and by appointment

Course Information


 
Documents

Textbook
Homework

LaTeX Resources

I recommend using Overleaf (free) to write your assignments in LaTeX.

Resources
Outside Tutorials

I'm happy to help troubleshoot your LaTeX in office hours and over email!


Important Dates
Tues, Jan 16 Classes begin
Wed, Jan 24 Last day to add/drop classes or request CR/NC option
Mon, Mar 4 — Fri, Mar 8 Midterm exam period
Mon, Mar 11 — Fri, Mar 15 Spring break, no classes
Fri, Mar 29 and Mon, Apr 1 Easter break, no classes
Fri, Apr 12 Last day to withdraw from classes
Fri, May 3 Last day of classes
Thursday, May 9
1:00pm - 3:00pm
Math 4670 / 5670 final exam

Daily Calendar
# Date Topics Suggested HW
& Announcements
Week 1
1 Wed, Jan 17 Syllabus
Section 1.1: Principles of Combinatorics (started)
Before Friday: read syllabus
No suggested homework.
2 Fri, Jan 19 Section 1.1: Principles of Combinatorics (continued) Read pages 1-4
Section 1.1: 2a, 3, 4, 7
Week 2
3 Mon, Jan 22 Section 1.1: Principles of Combinatorics (continued) Read pages 5-7
Section 1.1: 9ab
4 Wed, Jan 24 Homework 1 Assigned (link at top of page, due Friday, Feb 9)
Section 1.1: Principles of Combinatorics (continued)
Read pages 8-9
Section 1.1: 1bc, 2b, 9c, 18
5 Fri, Jan 26 Quiz 1 — covers all 1.1 suggested homework so far
Section 1.1: Principles of Combinatorics (continued)
Read pages 9-13
No new suggested homework, keep practicing and reading.
Week 3
6 Mon, Jan 29 Section 1.1: Principles of Combinatorics (finished) Read pages 13-14.
Section 1.1: 1a, 5, 11, 15, 17
7 Wed, Jan 31 Section 1.2: Counting, overcounting, and the sum principle (started) Read pages 15-16.
Section 1.2: 1, 2, 4abc, 11
8 Fri, Feb 2 Section 1.2: Counting, overcounting, and the sum principle (continued) Read pages 16 to middle of 18.
Section 1.2: 4de, 6, 10, 16, 17
Week 4
9 Mon, Feb 5 Section 1.2: Counting, overcounting, and the sum principle (continued) Read pages 18-22.
10 Wed, Feb 7 Section 1.2: Counting, overcounting, and the sum principle (finished)
Section 1.3: Functions and the Bijection Principle (started)
Read pages 24-25.
Section 1.2: 3, 7, 9
Section 1.3: 1, 2
11 Fri, Feb 9 Homework 1 Due
Homework 2 Assigned
Quiz 2
Section 1.3: Functions and the Bijection Principle (continued)
Read pages 25-27.
Section 1.3: 3, 4
Week 5
12 Mon, Feb 12 Section 1.3: Functions and the Bijection Principle (continued) Read pages 27-30.
Section 1.3: 9, 12
13 Wed, Feb 14 Section 1.3: Functions and the Bijection Principle (finished) Read pages 28-31 (skipping "Inverse" section).
Section 1.3: Answer Question 34 on page 30.
14 Fri, Feb 16 Exam 1
Week 6
15 Mon, Feb 19 Section 1.4: Relations and the Equivalence Principle
(we are covering just some of the material)
Read from page 36 (starting at "The equivalence principle") up to 38 (stopping at "Are the equivalence relations?") and ignore parts about equivalence relations

Section 1.4: 8, 9, 10
16 Wed, Feb 21 Homework 2 Due
Homework 3 Assigned
Section 2.1: Counting Functions (started)
Read pages 49-53
Section 2.1: 1ab, 2, 4abcd, 5, 6
17 Fri, Feb 23 Quiz 3
Section 2.1: Counting Functions (continued)
Read pages 53-56
Section 2.1: 9, 10
Week 7
18 Mon, Feb 26 Section 2.1: Counting Functions (finished)
Section 2.2: Counting Subsets and Multisets (started)
Read pages 55-60.
Section 2.1: 1c, 14, 16
Section 2.2: 1, 2, 3

NOTE: Problems 2.1.14 and 2.1.16c are extra challenging, and will not be on the quiz, but they are still good practice. Questions 2.1.1c and 2.1.16ab are eligible quiz questions.
19 Wed, Feb 28 Section 2.2: Counting Subsets and Multisets (continued) Read pages 59-61.
Section 2.2: 4a, 4b, 7abcd, 8
20 Fri, Mar 1 Quiz 4
Section 2.2: Counting Subsets and Multisets (continued)
Read pages 61-64.
Section 2.2: 4ef
Week 8
21 Mon, Mar 4 Section 2.2: Counting Subsets and Multisets (finished) Section 2.2: 6
Plus the group work problems from lecture about the Binomial Theorem.
22 Wed, Mar 6 Homework 3 Due
Homework 4 Assigned
Section 2.3: Counting Set Partitions (started)
Read pages 67-69.
Section 2.3: 1, 8, 9
23 Fri, Mar 8 Exam 2
Spring Break
Mon, Mar 11 Spring Break — no class
Wed, Mar 13 Spring Break — no class
Fri, Mar 15 Spring Break — no class
Week 9
24 Mon, Mar 18 Section 2.3: Counting Set Partitions (continued) Read pages 69-72.
Section 2.3: 6, 11
25 Wed, Mar 20 Section 2.3: Counting Set Partitions (finished)
Section 2.4: Counting Integer Partitions (started)
Read pages 73-76.
Section 2.3: 2, 3, 4, 5
Section 2.4: 1
26 Fri, Mar 22 Quiz 5
Section 2.4: Counting Integer Partitions (continued)
Read pages 76-78.
Section 2.4: 5, 6
Week 10
27 Mon, Mar 25 Section 2.4: Counting Integer Partitions (continued) Read pages 78-80.
Section 2.4: 2, 3
28 Wed, Mar 27 Homework 4 Due
Section 2.4: Counting Integer Partitions (finished-ish)
Read pages 79-81.
Section 2.4: 8
Fri, Mar 29 Easter Break — no class
Week 11
Mon, Apr 1 Easter Break — no class
29 Wed, Apr 3 Homework 5 Assigned
Section 3.1: Inclusion-Exclusion (started)
Read pages 83-88.
Section 3.1: Questions 90-94, and 96 on pages 84-86
30 Fri, Apr 5 Quiz 6
Section 3.1: Inclusion-Exclusion (nearly finished)
Week 12
31 Mon, Apr 8 No in-person lecture today.
Video Lecture — GT1 - Intro to Graph Theory
32 Wed, Apr 10 Section 3.1: Inclusion-Exclusion (finish)
GT2 - Trees (started)
Read pages 88-92 of main textbook.
Section 3.1: 1, 2, 4a, 5a, 8
Lecture GT 1 and GT2: Review definitions for Quiz 7.
33 Fri, Apr 12 Quiz 7 — One question from 3.1 and one definition from GT1 or GT2.
GT2 - Trees (continued)
Read pages 65-68 of Applied Combinatorics.
Chapter 5, exercises 1-4, 7 in Applied Combinatorics.
Week 13
34 Mon, Apr 15 GT2 - Trees (continued) Read pages 68-70 of Applied Combinatorics.
Suggested Homework
35 Wed, Apr 17 Homework 5 Due
Homework 6 Assigned
GT2 - Trees (finished)
GT3 - Walks on Graphs (barely started)
Same reading and suggested homework as 4/15.
36 Fri, Apr 19 Exam 3
Week 14
37 Mon, Apr 22 GT3 - Walks on Graphs (continued) Read pages 70-71 of Applied Combinatorics.
Chapter 5, exercises 8, 9 (ignore Hamiltonian), 10 in Applied Combinatorics.
38 Wed, Apr 24 GT3 - Walks on Graphs (continued) Read pages 71-73 of Applied Combinatorics.
For the graphs in exercises 8 and 9 of Chapter 5 in Applied Combinatorics, apply the algorithm we discussed in class today to compute an Eulerian circuit.
39 Fri, Apr 26
Lecture replaced by a pre-recorded video lecture
GT3 - Walks on Graphs (finished)
GT4 - Graph Coloring (started)
See Monday, April 29
Week 15
40 Mon, Apr 29 Quiz 8
GT4 - Graph Coloring (continued)
Read pages 73-76 of Applied Combinatorics.
Chapter 5, exercises 9 (the Hamiltonian part), 12, 13, 14, 15, 25 in Applied Combinatorics.
41 Wed, May 1 Homework 6 Due
GT4 - Graph Coloring (continued)
Read Section 5.4.1 in this other version of the book.
Suggested Homework:
  1. Find an example of a graph that is not an interval graph.
  2. Come up with an interesting example of a graph WITH odd cycles and a graph WITHOUT odd cycles, and run the 2-coloring algorithm on both of them.
42 Fri, May 3 GT4 - Graph Coloring (finished)
GT5 - Planar Graphs (brief overview)
Read end of page 85 (last paragraph) to middle of page 88 in Applied Combinatorics.
Chapter 5, exercises 28, 29, 30, 31 in Applied Combinatorics.
Thurs, May 9 Final Exam, 1:00pm - 3:00pm