Combinatorics
eyildirim@gsu.edu.tr
Content
Objective
This course presents the fundamental principles, structures, and techniques of enumerative and structural combinatorics. It covers bijective reasoning, generating functions, partially ordered sets, graphs and trees, Catalan structures, permutations, partitions, Young tableaux, and classical combinatorial correspondences. The course also aims to develop students' ability to construct rigorous combinatorial arguments and to identify common structures in seemingly disparate counting problems.
Course Content
This course offers an introduction to combinatorics through the study of finite sets and finite functions, counting principles, generating functions, relations and graphs, partially ordered sets and lattices, trees, permutations, partitions, and arrays. Classical enumerative families, such as Catalan configurations, binary trees, polygonal triangulations, and integer partitions, are studied along with the bijections that connect them. The course concludes with the study of Young tableaux and the Robinson-Schensted-Knuth correspondence, illustrating the interaction between enumeration, algebraic structure, and combinatorial algorithms.
Course Learning Outcomes
By the end of this course, students will be able to apply the fundamental principles of enumeration; construct and analyze combinatorial bijections; and enumerate and connect standard Catalan families. Students will also be able to present combinatorial reasoning clearly and rigorously.
Teaching and Learning Methods
This course will include lectures with concrete examples and combinatorial proofs. At the end of the course, students will give presentations on chosen topics, with the aim of developing their mathematical autonomy and their ability to communicate combinatorial concepts effectively.
References
Introduction à la combinatoire
Notes de cours
Professeur : François Bergeron
Weekly Contents
| Week | Weekly Contents |
|---|---|
| 1 | Recall on sets, functions, and bijections |
| 2 | Cardinalities of sets, the pigeonhole principle, the inclusion-exclusion principle, sequences and generating series |
| 3 | Relations, graphs, isomorphisms, equivalences, partitions |
| 4 | Orders, lattices, paths in a directed graph |
| 5 | Trees, endofunctions |
| 6 | Binary trees, triangulations of a polygon |
| 7 | Exam |
| 8 | Solutions of the exam |
| 9 | Catalan configurations and bijections |
| 10 | Permutations, inversions, partitions |
| 11 | Ferres diagrams, Euler's pentagonal theorem |
| 12 | Young tableaux, Robinson-Schensted-Knuth correspondence |
| 13 | Student presentations |
| 14 | Student presentations |
Assessment System
| Activities | Number | Contribution |
|---|---|---|
| Contribution of in-term studies to overall grade | 2 | 60 |
| Contribution of final exam to overall grade | 1 | 40 |
| Total | 3 | 100 |
| Activities | Number | Contribution |
|---|---|---|
| Assignments | 0 | 0 |
| Presentation | 1 | 30 |
| Midterm Examinations (including preparation) | 1 | 30 |
| Project | 0 | 0 |
| Laboratory | 0 | 0 |
| Other Applications | 0 | 0 |
| Quiz | 0 | 0 |
| Term Paper/ Project | 0 | 0 |
| Portfolio Study | 0 | 0 |
| Reports | 0 | 0 |
| Learning Diary | 0 | 0 |
| Thesis/ Project | 0 | 0 |
| Seminar | 0 | 0 |
| Other | 0 | 0 |
| Make-up | 0 | 0 |
| Total | 2 | 60 |
Relation of Proficiency
| No | Program Learning Outcomes | Contribution | ||||
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | ||
| 1 | understands principles of deductive reasoning; has experience to verify well-foundedness and exactness of mathematical statements in systematic ways; | X | ||||
| 2 | can properly state and use concepts and results of major mathematical interest; | X | ||||
| 3 | masters current computational techniques and algorithms; has a good ability in their use; can identify relevant tools, among those one has learned, suitable to solve a problem and is able to judge whether or not one is in possession of these tools; | X | ||||
| 4 | is able to express one’s mathematical ideas in an organised way both in written and oral forms; | X | ||||
| 5 | understands relations connecting substantial concepts and results; can switch from one viewpoint to another on mathematical objects (pictures, formulae, precise statements, heuristic trials, list of examples,...); | X | ||||
| 6 | has followed individually a guided learning strategy; has pursued steps toward the resolution of unfamiliar problems; | X | ||||
| 7 | has a theoretical and practical knowledge in computer science well adapted for learning a programming language; | X | ||||
| 8 | has investigated the relevance of modeling and using mathematical tools in natural sciences and in the professional life; is conscious about historical development of mathematical notions; | X | ||||
| 9 | has followed introduction to some mathematical or non-mathematical disciplines after one’s proper choice; had experience to learn selected subjects according to one’s proper arrangement; | X | ||||
| 10 | masters French language as well as other foreign languages, to a level sufficient to study or work abroad. | X | ||||
ECTS
| Activities | Number | Period | Total Workload |
|---|---|---|---|
| Class Hours | 14 | 3 | 42 |
| Working Hours out of Class | 14 | 3 | 42 |
| Assignments | 0 | 0 | 0 |
| Presentation | 1 | 14 | 14 |
| Midterm Examinations (including preparation) | 1 | 8 | 8 |
| Project | 0 | 0 | 0 |
| Laboratory | 0 | 0 | 0 |
| Other Applications | 0 | 0 | 0 |
| Final Examinations (including preparation) | 1 | 10 | 10 |
| Quiz | 0 | 0 | 0 |
| Term Paper/ Project | 0 | 0 | 0 |
| Portfolio Study | 0 | 0 | 0 |
| Reports | 0 | 0 | 0 |
| Learning Diary | 0 | 0 | 0 |
| Thesis/ Project | 0 | 0 | 0 |
| Seminar | 0 | 0 | 0 |
| Other | 0 | 0 | 0 |
| Make-up | 0 | 0 | 0 |
| Yıl Sonu | 0 | 0 | 0 |
| Hazırlık Yıl Sonu | 0 | 0 | 0 |
| Hazırlık Bütünleme | 0 | 0 | 0 |
| Total Workload | 116 | ||
| Total Workload / 25 | 4.64 | ||
| Credits ECTS | 5 | ||