Combinatorics

# MAT 145 - Combinatorics

## Instructor - Kevin Lamb

Email - kmlamb[AT]math[DOT]ucdavis[DOT]edu

Class Syllabus
Changes:

• Extra office hours added.
• Section 6.4 has been added to the syllabus and Chapter 7 will not be covered.
• FIVE homeworks in total, not six anymore (still dropping one).
• Chapter 12 material has been dropped from the syllabus.

### Office Hours

MSB 2131: MWF 12-1p, with the possibility of going past 1p.
MSB 2131: TR 10a-12p.

If you can't make any of these times, you may ask for an appointment at another time.

### Additional Resources

• The simulation script (in MatLab) mentioned in class that shows the proportion of randomly generated permutations of {1,2,...,n} that are derangements. Parameters may be varied to change the sample sizes of each experiment and how many experiments are run in total.
• The research paper I will reference for Wednesday 9/13 that talks about how we are using directed graphs to study the brain's neural network. You can also check out The Blue Brain Project to read more about the team's work, research goals, and progress.

### Class Notes

 Date Sections Covered Kevin's Notes and Handouts Assignments Due Week 1 8/7 Chapter 1 Group Work 1 Group Work 1 Write-up 8/9 2.1 Counting Principles 8/11 2.2, 2.3 Permutations and Combinations of Sets Week 2 8/14 2.3, 2.4, 2.5 Permutations and Combinations of Multisets 8/16 5.1, 5.2, 5.4 The Binomial Coefficients 8/18 5.5, Chapter 3 Newton's Binomial Theorem, Group Work 2 *Homework 1 Week 3 8/21 6.1, 6.2 YouTube Lecture, Notes No class 8/23 6.3, 6.4 Derangements and Forbidden Positions Group Work 2 Write-up, *Homework 2 8/25 11.1 Graphs and Their Isomorphisms Week 4 8/28 Midterm Solutions *Homework 3/MIDTERM 8/30 11.1, 11.2 Connectedness and Eulerian Trails 9/1 11.2, 11.3 Eulerian Trails, Hamiltonian Paths and Cycles Week 5 9/4 None HOLIDAY - Labor Day 9/6 11.3, 11.5 The Ore Property and First Principles of Trees *Homework 4 9/8 11.5, 11.7 Group Work 3: Growing Trees Group Work 3 Write-up Week 6 9/11 11.5, 13.1 Characterization of Trees, Introduction to Digraphs 9/13 N/A Directed Simplicial Complexes and Your Brain 9/15 None Final Exam Solutions (the real ones) *Homework 5/FINAL

### Homework Sets

Hard deadlines are denoted with a '*' in the "Assignments Due" column.
• Homework 1
Chapter 2 - 1, 2, 4, 8-15 (not 11), 17-22, 25, 27, 28, 30, 32, 35, 37-39, 41, 42, 45, 47-49, 51-53

• Homework 2
Chapter 5 - 3, 4, 6, 7, 10, 11, 14, 18, 19, 24-26, 29, 36, 42, 45, 46
Chapter 3 - 4-6, 8, 11, 14, 22, 23, 27

• Homework 3
Chapter 6 - 2, 3, 5, 6, 9, 10, 14, 15, 16, 24, 25, 27-30, 32, 33 (33 is optional)

• Homework 4
Chapter 11 - 2, 6, 7, 12, 13-15, 20, 22-25, 28-30 (40 moved to HW 5)

• Homework 5
Chapter 11 - 40, 42 (optional), 54-56, 57a, 62, 66, 75ad, 76ad, 79, 81, 91bc, 92
Chapter 13 - 4-6, 11, 14