Fall 2023 : MATH 453 Combinatorics

MATH 453 Combinatorics

Instructor: Hemanshu Kaul
Office: 125C, Rettaliata Engg Center.
E-mail: kaul [at] iit.edu

Class Time: 11:25am-12:40pm, Tuesday and Thursday
Place: 124, Rettaliata Engg Center

Discussion Forums: Math 453 at Campuswire.

Office Hours: Tuesday and Thursday at 1:45-2:45pm. And by appointment in-person or through Zoom (send email to setup appointment).
Questions through Campuswire Discussion Forum are strongly encouraged.

TA Office Hours: Gunjan Sharma. Monday 9am-12pm at RE 129 or through Zoom link at Math Tutoring Center.

Course Information:

The primary aim of this proof-based course is to introduce elementary counting techniques in Combinatorics, such as Permutations and combinations, pigeonhole principle, principle of inclusion-exclusion, recurrence relations and generating functions, enumeration under group action, etc.

The Course Information Handout has extensive description of the course - topics, textbook, student evaluation policy, as well as other relevant information. Read it carefully!

What is this course really about? Required reading.

The end-of-semester letter for students: What Next?

The official course syllabi: MATH 453 (reference for topics only).

The course textbook, most of which can be previewed on Google Books, is: David Mazur - Combinatorics: A Guided Tour.
Here is the collected errata for the textbook.

Advice for students:

Excellent advice by Francis Su on good mathematical writing.

Why do we have to learn proofs?
Understanding Mathematics - a study guide
On a more abstract note, here is a discussion by Tim Gowers on Language and Grammar of Mathematics - which is what you are learning in a course like this.

Excellent advice for math majors, especially those planning to go on to graduate school, by Terry Tao, 2006 Fields medallist. Required reading.

Read this book on a variety of experiences in the journey to learn mathematics: Living Proof

Some of the primary sources of information/discussion for careers in Mathematical Sciences:
MAA - Careers
SIAM - Careers
INFORMS - Careers
AMS - Careers

Class Announcements:

Tuesday, 8/22 : Check this webpage regularly for weekly lecture topics, videos, and HW.

Examinations:

Exam # 1 : Tuesday, October 3rd. Syllabus: Based on topics corresponding to HWs #1 to #5.
Exam # 2 : Tuesday, November 14th. Syllabus: Based on topics corresponding to HWs #6 to #10.
Final Exam : Friday, December 8th, 2pm–4pm, in RE 124. Topics: All topics studied during the semester.

Weekly Class Log with Topics, Reading HW and Submission HW:

Week #1 : 2 lectures
- Topics: From Sections 1.1, 1.2, and elsewhere.
- Reading and Discussion HW: Tuesday: Preface, part I (pages vii,viii), Before you go (page xv), Section 1.1 (pages 1-14). Answer all reading questions (1-16). Thursday: Read Section 1.2. Answer all reading questions, note any questions of your own.
- Homework:
  Re-read and follow the "HW Discussion and Solution Rules" and " `Why and How' of Homework" sections of the course information sheet for some important advice on the HWs for this course.
  You are allowed to discuss the homework problems with no one except your classmates, the TA, and the instructor. However, the solutions should be written by you and you alone in your own words. If you discussed HW problems with a classmate or TA, you have to write their name at the top of the HW submission as a collaborator.
  Homework #1 : Due 10pm, August 31st. Submit a PDF file through Blackboard Assignment. Solutions distributed in class.
  Section 1.1: Submit: 2-6, 9, 11, 13, 15; Try but not Submit: 16, 17, 19. Section 1.2: Submit: 1-7, 11, 12, 15, 16; Try but not submit: 14, 19.
  Always remember that homework is NOT meant to be an examination, it is meant to assist in your learning and development. Ask for help through Campuswire Discussion Forums, during the instructor and TA office hours, or through email to the instructor.
Week #2 : 2 lectures
- Topics: From Sections 1.2, 1.3, 1.4, and elsewhere.
- Reading and Discussion HW: Tuesday: Read Section 1.3. Answer all reading questions, note any questions of your own. Thursday: Read Section 1.4. Answer all reading questions, note any questions of your own.
- Homework:
  Re-read and follow the "HW Discussion and Solution Rules" and " `Why and How' of Homework" sections of the course information sheet for some important advice on the HWs for this course.
  You are allowed to discuss the homework problems with no one except your classmates, the TA, and the instructor. However, the solutions should be written by you and you alone in your own words. If you discussed HW problems with a classmate or TA, you have to write their name at the top of the HW submission as a collaborator.
  Homework #2 : Due 10pm, September 7th. Submit a PDF file through Blackboard Assignment. Solutions distributed in class.
  Section 1.3: Submit: 1-4, 6, 8, 12. Try but not submit: 13. Section 1.4: Submit: 2, 4, 7, 8, 11, 15. Try but not Submit: 6, 10, 13.
  Always remember that homework is NOT meant to be an examination, it is meant to assist in your learning and development. Ask for help through Campuswire Discussion Forums, during the instructor and TA office hours, or through email to the instructor.
Week #3 : 2 lectures
- Topics: From Sections 1.4, 1.5, and elsewhere.
- Reading and Discussion HW: Read Section 1.5. Answer all reading questions, and note any questions of your own.
- Homework:
  Re-read and follow the "HW Discussion and Solution Rules" and " `Why and How' of Homework" sections of the course information sheet for some important advice on the HWs for this course.
  You are allowed to discuss the homework problems with no one except your classmates, the TA, and the instructor. However, the solutions should be written by you and you alone in your own words. If you discussed HW problems with a classmate or TA, you have to write their name at the top of the HW submission as a collaborator.
  Homework #3 : Due 10pm, September 14th. Submit a PDF file through Blackboard Assignment. Solutions distributed in class.
  Section 1.5: Submit: 1, 2, 3, 4, 6, 10. Try but not submit: 5.
  Always remember that homework is NOT meant to be an examination, it is meant to assist in your learning and development. Ask for help through Campuswire Discussion Forums, during the instructor and TA office hours, or through email to the instructor.
Week #4 : 2 lectures
- Topics: From Sections 1.5, 2.1, and elsewhere.
- Reading and Discussion HW: Read Section 2.1. Answer all reading questions, and note any questions of your own.
- Homework:
  Re-read and follow the "HW Discussion and Solution Rules" and " `Why and How' of Homework" sections of the course information sheet for some important advice on the HWs for this course.
  You are allowed to discuss the homework problems with no one except your classmates, the TA, and the instructor. However, the solutions should be written by you and you alone in your own words. If you discussed HW problems with a classmate or TA, you have to write their name at the top of the HW submission as a collaborator.
  Homework #4 : Due 10pm, September 21st. Submit a PDF file through Blackboard Assignment. Solutions distributed in class.
  Section 1.5: Submit: 7, 8a; Try but not submit: 11, 12.
  Section 2.1: Submit (each of these problems has a short answer): 2, 3, 4abe, 6a; Try but not submit: 1, 6, 9, 10, 11, 12.
  Also SUBMIT 3 out of the following 4 problems:
  (1) Let n be a positive integer not divisible by 2 or 5. Prove that there is multiple of n consisting entirely of digits 1.
  (2) From any 52 positive integers, prove that we can always select two such that their sum or difference is divisible by 100. Is it possible to do so with only 51 numbers?
  (3) Each point in the plane is arbitrarily colored with either red or blue. Prove that there exists a rectangle with corner points of the same color.
  (4) Consider k distinct positive integers picked from the set [n] where k > (n+1)/2. Write them as a(1) < a(2) < .... < a(k). Prove that there is at least one pair a(i), a(r) such that a(i) +a(1) =a(r).
  Always remember that homework is NOT meant to be an examination, it is meant to assist in your learning and development. Ask for help through Campuswire Discussion Forums, during the instructor and TA office hours, or through email to the instructor.
Week #5 : 2 lectures
- Topics: From Sections 2.1, 2.2, and elsewhere.
- Reading and Discussion HW: Read Section 2.2. Answer all reading questions, and note any questions of your own.
- Homework:
  Re-read and follow the "HW Discussion and Solution Rules" and " `Why and How' of Homework" sections of the course information sheet for some important advice on the HWs for this course.
  You are allowed to discuss the homework problems with no one except your classmates, the TA, and the instructor. However, the solutions should be written by you and you alone in your own words. If you discussed HW problems with a classmate or TA, you have to write their name at the top of the HW submission as a collaborator.
  Homework 5 : Due 11:15am, September 28th. NOTE THE SPECIAL TIME - This is a strict deadline due to the Exam on Tuesday. Submit a PDF file through Blackboard Assignment. Solutions distributed in class.
  Section 2.1: Submit: 14, 16ab; Try but not submit: 1, 6, 9, 10, 12, 13, 15. Section 2.2: Submit: (submit three out of four parts of 4abde), 5, 6, 9; Try but not submit: 1, 2, 3, 11.
  Always remember that homework is NOT meant to be an examination, it is meant to assist in your learning and development. Ask for help through Campuswire Discussion Forums, during the instructor and TA office hours, or through email to the instructor.
Weeks #6 and #7 : 3 lectures and 1 Mid-term Exam
- Topics: From Sections 2.3, 2.4, 4.4(Ferrers Diagrams), and elsewhere.
- Reading and Discussion HW: Read Sections 2.3 and 2.4. Answer all reading questions, and note any questions of your own.
- Homework:
  Re-read and follow the "HW Discussion and Solution Rules" and " `Why and How' of Homework" sections of the course information sheet for some important advice on the HWs for this course.
  You are allowed to discuss the homework problems with no one except your classmates, the TA, and the instructor. However, the solutions should be written by you and you alone in your own words. If you discussed HW problems with a classmate or TA, you have to write their name at the top of the HW submission as a collaborator.
  Homework #6 : Based on 3 lectures. Submit any 10 out of the 11 problems listed below. Due 10pm, October 12th. Submit a PDF file through Blackboard Assignment. Solutions distributed in class.
  Section 2.3: Submit: 2, 6, 8, 12, 13, 14; Try but not submit: 4, 5, 9, 11, 15, 18. Section 2.4: Submit: 3, 5, 8, 11with12; Try but not submit: 1, 2, 6, 13a. Section 4.4: Submit: 3; Try but not submit: 1.
  Always remember that homework is NOT meant to be an examination, it is meant to assist in your learning and development. Ask for help through Campuswire Discussion Forums, during the instructor and TA office hours, or through email to the instructor.
Week #8 : 2 lectures
- Topics: From Sections 3.1, 3.2, and elsewhere. Discussion of Exam#1.
- Reading and Discussion HW: Read Sections 3.1 and 3.2. Answer all reading questions, and note any questions of your own.
- Homework:
  Re-read and follow the "HW Discussion and Solution Rules" and " `Why and How' of Homework" sections of the course information sheet for some important advice on the HWs for this course.
  You are allowed to discuss the homework problems with no one except your classmates, the TA, and the instructor. However, the solutions should be written by you and you alone in your own words. If you discussed HW problems with a classmate or TA, you have to write their name at the top of the HW submission as a collaborator.
  Homework #7 : Due 10pm, October 19th. Submit a PDF file through Blackboard Assignment. Solutions distributed in class.
  Section 3.1: Submit: 2, 5, 6 with 7a, 9 (try 8 first), 14, 17a; Try but not submit: 1, 3, 4, 8, 10, 13, 16. Section 3.2: Submit: 4, 5, 8, One of (9 or 10), 14; Try but not submit: 1, 6, 11.
  Always remember that homework is NOT meant to be an examination, it is meant to assist in your learning and development. Ask for help through Campuswire Discussion Forums, during the instructor and TA office hours, or through email to the instructor.
Week #9 : 2 lectures
- Topics: From Sections 3.3, 3.4, and elsewhere. Discussion of Exam#1.
- Reading and Discussion HW: Read Sections 3.3 and 3.4. Answer all reading questions, and note any questions of your own.
- Homework:
  Re-read and follow the "HW Discussion and Solution Rules" and " `Why and How' of Homework" sections of the course information sheet for some important advice on the HWs for this course.
  You are allowed to discuss the homework problems with no one except your classmates, the TA, and the instructor. However, the solutions should be written by you and you alone in your own words. If you discussed HW problems with a classmate or TA, you have to write their name at the top of the HW submission as a collaborator.
  Homework #8 : Due 10pm, October 26th. Submit a PDF file through Blackboard Assignment. Solutions distributed in class.
  Section 3.3: Submit: 2bef, 3bde, 5, 7, 9b; Try but not submit: 1, 2, 3, 4, 8, 9. Section 3.4: Submit: 1.
  Always remember that homework is NOT meant to be an examination, it is meant to assist in your learning and development. Ask for help through Campuswire Discussion Forums, during the instructor and TA office hours, or through email to the instructor.
Week #10 : 2 lectures
- Topics: From Sections 3.4, 3.5, and elsewhere.
- Reading and Discussion HW: Read Sections 3.4 and 3.5. Answer all reading questions, and note any questions of your own.
- Homework:
  Re-read and follow the "HW Discussion and Solution Rules" and " `Why and How' of Homework" sections of the course information sheet for some important advice on the HWs for this course.
  You are allowed to discuss the homework problems with no one except your classmates, the TA, and the instructor. However, the solutions should be written by you and you alone in your own words. If you discussed HW problems with a classmate or TA, you have to write their name at the top of the HW submission as a collaborator.
  Homework #9 : Due 10pm, November 2nd. Submit a PDF file through Blackboard Assignment. Solutions distributed in class.
  Section 3.4: Submit: 2, 9, 11; Try but not submit: 3, 6, 7, 8. Section 3.5: Submit: 1ce, 2, 3bc, 5; Try but not submit: 4, 6.
  Always remember that homework is NOT meant to be an examination, it is meant to assist in your learning and development. Ask for help through Campuswire Discussion Forums, during the instructor and TA office hours, or through email to the instructor.
Week #11 : 2 lectures
- Topics: From Sections 3.5, 3.6, 4.1, and elsewhere.
- Reading and Discussion HW: Read Sections 3.5 and 3.6. Answer all reading questions, and note any questions of your own.
- Homework:
  Re-read and follow the "HW Discussion and Solution Rules" and " `Why and How' of Homework" sections of the course information sheet for some important advice on the HWs for this course.
  You are allowed to discuss the homework problems with no one except your classmates, the TA, and the instructor. However, the solutions should be written by you and you alone in your own words. If you discussed HW problems with a classmate or TA, you have to write their name at the top of the HW submission as a collaborator.
  Homework #10 : Due 11am, November 9th. NOTE THE SPECIAL TIME - This is a strict deadline due to the Exam on Tuesday. Submit a PDF file through Blackboard Assignment. Solutions distributed in class.
  Section 3.6: Submit: 2bd, 4, 6; Try but not submit: 1, 2, 5, 7. Section 4.1: Submit: 1, 5, 10, 12 (Hint: Review multiset counting using binary sequences on page 10); Try but not submit: 2, 3, 4, 7, 8, 13.
  Always remember that homework is NOT meant to be an examination, it is meant to assist in your learning and development. Ask for help through Campuswire Discussion Forums, during the instructor and TA office hours, or through email to the instructor.
Weeks #12 & #13 : 3 lectures and 1 Mid-term Exam
- Topics: From Sections 4.1, 4.2, 4.3, 5.1, 5.2, and elsewhere.
- Reading and Discussion HW: Read Sections 4.1, 4.2, and 4.3. Answer all reading questions, and note any questions of your own.
- Homework:
  Re-read and follow the "HW Discussion and Solution Rules" and " `Why and How' of Homework" sections of the course information sheet for some important advice on the HWs for this course.
  You are allowed to discuss the homework problems with no one except your classmates, the TA, and the instructor. However, the solutions should be written by you and you alone in your own words. If you discussed HW problems with a classmate or TA, you have to write their name at the top of the HW submission as a collaborator.
  Homework #11 : Due 10pm, November 22nd (Wednesday). Submit a PDF file through Blackboard Assignment.
  Section 4.2: Submit: 1a, 2, 5, 12a (Hint: Go through the values for n=1,2,3,4, and compare them to Fibonacci numbers); Try but not submit: 4, 6, 7, 9. Section 5.2: Submit: 2, 4, one of (8 OR 9); Try but not submit: 1, 3, 7.
  Always remember that homework is NOT meant to be an examination, it is meant to assist in your learning and development. Ask for help through Campuswire Discussion Forums, during the instructor and TA office hours, or through email to the instructor.
Weeks #14 & #15 : 3 lectures and 1 holiday
- Topics: From Sections 5.3, 5.4, and 5.5 & 5.6.
- Reading and Discussion HW: Read Sections 5.3, 5.4, and 5.5 & 5.6. Answer all reading questions, and note any questions of your own.
- Homework:
  Re-read and follow the "HW Discussion and Solution Rules" and " `Why and How' of Homework" sections of the course information sheet for some important advice on the HWs for this course.
  You are allowed to discuss the homework problems with no one except your classmates, the TA, and the instructor. However, the solutions should be written by you and you alone in your own words. If you discussed HW problems with a classmate or TA, you have to write their name at the top of the HW submission as a collaborator.
  Homework #12 : Due 10am, December 1st (Friday). NOTE THE SPECIAL TIME. Submit a PDF file through Blackboard Assignment.
  Section 5.3: Submit: one of (2 OR 3); Try but not submit: 1, 5. Section 5.4: Submit: four out of (2, 4, 8, 9, 14); Try but not submit: 1, 5, 7, 10, 11, 12. Section 5.6: Submit: None; Try but not submit: 1, 2, 6, 8, 10.
  Always remember that homework is NOT meant to be an examination, it is meant to assist in your learning and development. Ask for help through Campuswire Discussion Forums, during the instructor and TA office hours, or through email to the instructor.

Links for Additional Information:

HOME