Math 365 (Combinatorics), Spring 2023
Syllabus

Lectures: M, W   2:00 - 3:40,  room NAC  5/109

Lecturer: Vladimir Shpilrain  Office: NAC 4118b  Phone: (212) 650-5158
e-mail: shpilrain@yahoo.com   web page:  http://shpilrain.ccny.cuny.edu/

Office hours: M, W 12:15-1:15 or by appointment

Homework: Homework problems will be assigned once a week.

Textbook: Kenneth H. Rosen, Discrete Mathematics and its applications, 8th edition, McGraw Hill 2018.

Material to be covered (tentative): Chapter 2, Sections 2.1--2.4; Chapter 5, Sections 5.1, 5.2;
Chapter 6, Sections 6.1--6.5; Chapter 8, Sections 8.1--8.3, 8.5; Chapter 10, Sections 10.1--10.8;
Chapter 11, Sections 11.1, 11.2, 11.4, 11.5.

Approximate grading weights:

3 exams: 30 % each
Quiz: 10 %

There will be no early or make-up exams.
 

Homework assignments

HW#1: Section 2.2 (Set Operations), Ex. 4, 29, 30, 31;   Section 2.3 (Functions), Ex. 3, 4, 5, 9, 12, 15, 16, 20.

HW#2: Section 5.1 (Mathematical Induction), Ex. 4, 29, 30, 31;   Section 5.1 (Strong Induction), Ex. 3, 7, 10.

HW#3: Section 6.1 (The basics of counting), Ex. 11, 16, 17, 22(a,b,c), 31, 32(a,b,c), 41, 49;   Section 6.2 (The pigeonhole principle), Ex. 4, 12, 15, 26.

HW#4: Section 6.5 (Generalized permutations and combinations), Ex. 5, 11, 15, 16, 20, 30, 31, 35, 42, 44(a), 45(a).

HW#5: Section 8.1 (Applications of recurrence relations), Ex. 7, 8, 11, 26, 28;   Section 8.2 (Solving linear recurrence relations), Ex. 3(c,e), 4(a,b,e,g), 7.

HW#6: Section 8.2 (Solving linear recurrence relations), Ex. 23, 24, 26(a,b,c,g), 27(a,c,g), 32.

HW#7: Section 10.2 (Graph terminology...), Ex. 18, 23-26, 35, 37, 41;   Section 10.3 (Representing graphs and graph isomorphism), Ex. 9, 11, 25, 35-42.

HW#8: Section 10.4 (Connectivity), Ex.3-6, 20-23, 31-33;   Section 10.5 (Euler and Hamilton paths), Ex.1-7, 30-36.

HW#9: Section 10.8 (Graph coloring), Ex. 5-11, 21, 23, 25, 32, 33.

HW#10: Section 11.1 (Introduction to trees), Ex. 2, 3, 11(a), 12(a), 15, 16, 39, 41;   Section 11.4 (Spanning trees), Ex. 7, 12(a,b), 14, 17(b,c), 18(b,c), 44, 45;   Section 11.5 (Minimum spanning trees), Ex. Ex. 3, 7, 11, 12.