Combinatorial Mathematics - MATH F421
Elective Course: Semester I 2023- 2024
Instructor: Dr. Yasmeen Akhtar
Audience: 3rd - 4th-year B.E. students and graduate students at BITS Pilani K K Birla Goa Campus
Schedule: M, W, F 5:00-5:50 PM, A604
Course Handout: Here.
Lecture:
14/08/23 - Introduction, Basic Counting Principles, Permutation and Combination
16/08/23 - The Pigeonhole Principle, Examples
18/08/23 - The Pigeonhole Principle-Strong Form, Examples, Ramsey Number r(3, 3)
21/08/23 - The Ramsey Number r(m, n), Generalization
23/08/23 - Generating Permutations
25/08/23 - Generating Combinations and r-sets
28/08/23 - Permutations of Multiset, Examples
30/08/23 - Holiday
01/09/23 - Generalized Principle of Inclusion-Exclusion, Combinations of Multiset, Examples
04/09/23 - Derangement, Examples
06/09/23 - Permutations with Absolute Forbidden Positions (Disjoint sub-boards)
08/09/23 - Permutations with Absolute Forbidden Positions (Non disjoint sub-boards), Examples, Permutations with Relative Forbidden Positions (Disjoint sub-boards)
11/09/23 - Relation and its Properties, Poset
13/09/23 - Chain, Equivalence Relation
15/09/23 - Quiz 1
18/09/23 - Mobius function
20/09/23 - Mobius Inversion
22/09/23 - Counting the number of ways of placing n non-attacking rooks on an n by n board with forbidden positions using the Mobius Inversion, Classical Mobius Inversion
25/09/23 - Catalan Numbers
27/09/23 - Difference Sequences
29/09/23 - Difference Sequences, Stirling Number of the second kind
02/10/23 - Holiday
04/10/23 - Bell Number, Stirling Number of the first kind, Partition Number
06/10/23 - Different types of partition numbers, Generating function for the sequence of partition numbers, Euler's Pentagonal Number Theorem
13/10/23 - Midterm Exam (Friday 11:00 AM - 12:30 PM)
16/10/23 - Lattice Paths: Rectangular, Subdiagonal, HVD-paths
18/10/23 - Subdiagonal HVD-paths, Schröder path, Small Schröder path, Large Schröder Number, Small Schröder Number
20/10/23 - System of Distinct Representatives (SDR) and its existence
No class: Waves and 20 Years of BITS Pilani, K K Birla Goa Campus
03/11/23 - Largest Subfamily with an SDR, Stable Marriage, Gale-Shapley Algorithm (5:00 PM-6:15 PM)
06/11/23 - Open day
08/11/23 - Women-optimal and Men-optimal Stable Complete Marriage, Block Design, BIBD and its properties (5:00 PM-6:15 PM)
10/11/23 - SBIBD, Difference Set, Steiner Triple System (5:00 PM-6:15 PM)
13/11/23 - Diwali Holiday
15/11/23 - Kirkman Triple System, Latin Square (5:00 PM-6:15 PM)
17/11/23 - Mutually orthogonal Latine Squares (5:00 PM-6:15 PM)
20/11/23 -Symmetries of an n-gone, Burnside Theorem (5:00 PM-6:15 PM)
22/11/23 - Polya's Counting: Cycle Index, Pattern Inventory
24/11/23 - Quiz 2
26/11/23 - Deadline to submit Project Report (by 5 PM)
27/11/23 - Presentations for Projects (Extra Class)
29/11/23 -Polya's Enumeration Formula
01/12/23 - Enumeration problems in Graph Theory: Counting the number of k-colorings, number of labeled trees
04/12/23 - Applications: Shanon Switching Game
10/12/23 - Comprehensive Exam