# 380: Introduction to Discrete Mathematics

## Textbook

Combinatorics Through Guided Discovery (November 6, 2004 edition) by Kenneth Bogart

## Office hours/Problem Solving Sessions/Homework Assistance

• Monday 2-3 in PDL C-416
• Tuesday 4:30-6:00 in PDL C-401

## Exams

• Midterm (Friday, February 9)
• Final (Monday, March 12, 8:30am-10:20am)

## Schedule/Assignments (all problems are from this set)

• 1/3/18:
• Topic: Introduction to counting
• Practice Problems (for today): #1, 3, 5
• Practice Problems (for next class): #7, 8, 13, 10a
• Homework Problems (due Wednesday, January 10): #2, 4, 6
• Book reading: read 1.1, start reading 1.2
• 1/5/18:
• Topic: Sums, products and functions
• Practice Problems (for today): #7, 8
• Practice Problems (for next class): #13, 10a, 16
• Homework Problems (due Wednesday, January 10): #9, 11, 12
• Book reading: 1.1 and 1.2.1
• 1/8/18:
• Topic: General Product Principle and its applications
• Practice Problems (for today): #13, 10a, 16
• Practice Problems (for next class): #18, 20; 21, 22, 25, 26
• Homework Problems (due Wednesday, January 17): #14, 15, 17
• Extra-credit HW Problem: 10b
• Book reading: 1.1 and 1.2.1
• 1/10/18:
• Topic: Applications of General Product Principle; Functions and Digraphs
• Practice Problems (for today): #18, 20; 21, 22, 25
• Practice Problems (for next class): #26; 28, 31, 32
• Homework Problems (due Wednesday, January 17): #19, 23, 24
• Book reading: 1.2.2 and 1.2.3; start reading 1.2.4 and 1.2.5
• 1/12/18:
• Topic: Bijection Principle; Binomial coefficients
• Practice Problems (for today): #26, 28a
• Practice Problems (for next class): #28bcd, 31, 32
• Homework Problems (due Wednesday, January 17): #27
• Book reading: 1.2.4 and 1.2.5
• 1/17/18:
• Topic: Bijection Principle; Binomial coefficients
• Practice Problems (for today): #28bcd, 31, 32
• Practice Problems (for next class): #37, 39, 36+38
• Homework Problems (due Wednesday, January 24): #29, 33, 34, 35ab
• Extra-credit HW Problem: 35c
• Book reading: 1.2.4 and 1.2.5; start reading 1.2.6
• 1/19/18:
• Topic: Binomial coefficients; Quotient Principle
• Practice Problems (for today): #37, 39, 36+38
• Practice Problems (for next class): #41, 43, 50
• Homework Problems (due Wednesday, January 24): #40, 42
• Book reading: 1.2.6
• 1/22/18:
• Topic: Applications of binomial coefficients
• Practice Problems (for today): #41, 43a
• Practice Problems (for next class): #43b, 50, 51, 54b
• Book reading 1.3.1; start reading 1.3.2
• 1/24/18:
• Topic: Binomial Theorem
• Practice Problems (for today): #43b; 50, 51
• Practice Problems (for next class): #54b; 56, 59
• Homework Problems (due Wednesday, January 31): #44; 52, 53
• Book reading: 1.3.2; start reading 1.3.3
• 1/26/18:
• Topic: Binomial Theorem and its applications; Pigeonhole Principle
• Practice Problems (for today): #54b; 56; B and C from this handout; 59
• Homework Problems (due Wednesday, January 31): #55; A from this handout; #58abc, and 57 (use the pigeonhole principle to solve it)
• Extra-credit HW Problem: #54a
• Book reading: 1.3.2, 1.3.3
• Practice Problems (for next class): #D, 61
• 1/29/18:
• Topic: Pigeonhole Principle
• Practice Problems: #D, 61
• Homework Problems (due Wednesday, February 7): #E, 61, 62
• Extra-credit HW Problem: Use the Pigeonhole Principle to solve #60
• Book reading: 1.3.3; start reading 2.1
• 1/31/18:
• Topic: Applications of Induction to Combinatorics
• Practice Problems (for today): #65, 67 (70, 63)
• Practice Problems (for next class): #70, 63; 71, 72
• Homework Problems (due Wdenesday, February 7): #66, 68, 69
• Book reading: 2.1.1, 2.1.2, 2.1.3
• 2/2/18:
• Topic: Applications of Induction to Combinatorics; Recurrence relations
• Practice Problems (for today): #70, 63 (71, 72)
• Practice Problems (for next class): #71, 72, 75
• Homework Problems (Wdenesday, February 7): #64
• Book reading: 2.1.1, 2.1.2, 2.1.3, 2.2
• 2/5/18:
• Topic: Recurrence relations
• Practice Problems (for today): #71,72,75
• Homework Problems (due Wednesday, February 21): #73, 74
• Extra-credit HW Problem: #76 (due Feb 14)
• Book reading: 2.1.3, 2.2
• 2/12/18:
• Topic: Graphs
• Practice Problems (for today): #80, 81ab, and I.3 from this handout
• Practice Problems (for next class): #I.3, II.1
• Homework Problems (due Wednesday, February 21): #82, 83, and I.1, I.2 from this handout
• Book reading: 2.3.1, 2.3.2; also please review strong induction (p.35 in the book)
• 2/14/18:
• Topic: Graphs and strong induction
• Practice Problems (for today): #I.3, II.1 from this handout
• Practice Problems (for next class): #I.4, 84, 85
• Homework Problems (due Wednesday, February 21): #II.2 from this handout
• Book reading: 2.3.1, 2.3.2, and p.35
• 2/16/18:
• Topic: Trees
• Practice Problems (for today): I.4 from this handout, #84; start thinking about #85
• Homework Problems (due Wednesday, February 21): #I.5 (feel free to use the conclusion of #84), 86, 91a
• Extra-credit HW Problem: #I.6 (due Feb 28)
• Book reading: 2.3.4
• 2/21/18:
• Topic: A bit more on trees; Distribution problems
• Practice Problems (for today): #85; 93, 95
• Practice Problems (for next class): 98, 99, 101, 104
• Homework Problems (due Wednesday, February 28): #94, 96
• Book reading: 3.1.1-3.1.3
• 2/23/18:
• Topic: Distribution problems
• Practice Problems (for today): #98, 99, 101; #2 and 4 from this handout
• Practice Problems (for next class): #4 from this handout; 105, 106, 109
• Homework Problems (due Wednesday, February 28): #100, 103; #1 and 3 from this handout
• Book reading: 3.1.3-3.1.4
• 2/26/18:
• Topic: Distribution problems
• Practice Problems (for today): #4 from this handout; 105, 106abc
• Practice Problems (for next class): 106def, 109, 112, 114
• Homework Problems (due Wednesday, March 7): #107, 108, 116
• Book reading: 3.2.1
• 2/28/18:
• Topic: Distribution problems
• Practice Problems (for today): #106def, 109, 112, 114
• Practice Problems (for next class): #114; 175, 177, 178, 179
• Homework Problems (due Wednesday, March 7): #115
• Extra-credit HW Problem: 111ab
• Book reading: 3.2.2
• 3/2/18:
• Topic: Stirling numbers; Inclusion-Exclusion
• Practice Problems (for today): #114; 175, 177, 178
• Practice Problems (for next class): #179 and #11-13 from Review handout
• Homework Problems (due Wednesday, March 7): #174, 176
• Book reading: 5.1
• 3/5/18:
• Topic: Inclusion-Exclusion
• Practice Problems (for today): #11-13 from Review handout
• Next time: finish discussing #13 from Review handout and #179; start reviewing
• 3/7/18:
• Topic: Inclusion-Exclusion; Review
• Practice Problems (for today): #13 from Review handout
• Extra-credit HW Problem: #179 (due Friday, March 9)
• Bring questions for Friday's lecture!