# Combinatorics

- Institution: IIT Madras
- Department: Mathematics
- Teacher: Prof. Narayanan N
- Level: Undergraduate
- Language: English
- Subjects: Mathematics
- Source: [NPTEL](https://nptel.ac.in/courses/111106155)
- Licence: [CC BY-NC-SA](https://nptel.ac.in/faq) (Non-commercial use only.)
- Syllabus: [at the source](https://nptel.ac.in/courses/111106155)
- Who can watch: Tweens profiles and older (sources give no ratings; placed by Invisible Network from the source's own words)

We start with the finite and infinite avatars of the Pigeonhole Principle, Basic counting tools and the twelvefold way followed by compositions and partitions of integers and Stirling numbers. We then look at Inclusion exclusion and Mobius inversion followed by generating functions. We then look at Polya's theorem, graphs and conclude with a short introduction to species of structures.

Intended audience: UG students

Prerequisites: Basic Mathematical Maturity expected from a Mathematics student at the level of 10+2. Familiarity with group theory will be addedadvantage (not necessary).

## Lectures

1. [Pigeonhole Principle](https://invisiblenetwork.ai/learn/nptel/111106155/f5f2c686b499) (YouTube)
2. [Dirichlet theorem and Erdos-Szekeres Theorem](https://invisiblenetwork.ai/learn/nptel/111106155/6884e9859df1) (YouTube)
3. [Ramey theorem as generalisation of PHP](https://invisiblenetwork.ai/learn/nptel/111106155/5518e0e6ffb2) (YouTube)
4. [An infinite flock of Pigeons](https://invisiblenetwork.ai/learn/nptel/111106155/e7d2861f8b3e) (YouTube)
5. [Basic Counting - the sum and product rules](https://invisiblenetwork.ai/learn/nptel/111106155/ce956a048c86) (YouTube)
6. [Examples of basic counting](https://invisiblenetwork.ai/learn/nptel/111106155/945fc90d3460) (YouTube)
7. [Examples: Product and Division rules](https://invisiblenetwork.ai/learn/nptel/111106155/557e7fee2286) (YouTube)
8. [Binomial theorem and bijective counting](https://invisiblenetwork.ai/learn/nptel/111106155/f1f8d0f91104) (YouTube)
9. [Counting lattice paths](https://invisiblenetwork.ai/learn/nptel/111106155/bbd891271601) (YouTube)
10. [Multinomial theorem](https://invisiblenetwork.ai/learn/nptel/111106155/b075fe5d9a1b) (YouTube)
11. [Applying Multinomial theorem](https://invisiblenetwork.ai/learn/nptel/111106155/4dc8270294f8) (YouTube)
12. [Integer compositions](https://invisiblenetwork.ai/learn/nptel/111106155/4a0be3ff188c) (YouTube)
13. [Set partitions and Stirling numbers](https://invisiblenetwork.ai/learn/nptel/111106155/d1cb0cd5beff) (YouTube)
14. [Stirling and Hemachandra recursions](https://invisiblenetwork.ai/learn/nptel/111106155/f2e98112ec45) (YouTube)
15. [Integer partitions](https://invisiblenetwork.ai/learn/nptel/111106155/60e6ad3f0e6f) (YouTube)
16. [Young's diagram and Integer partitions](https://invisiblenetwork.ai/learn/nptel/111106155/7838a263dd3d) (YouTube)
17. [Principle of Inclusion and Exclusion](https://invisiblenetwork.ai/learn/nptel/111106155/0430b9d540ce) (YouTube)
18. [Applications of PIE](https://invisiblenetwork.ai/learn/nptel/111106155/944b5e335455) (YouTube)
19. [The twelvefold way](https://invisiblenetwork.ai/learn/nptel/111106155/de4d84ac1818) (YouTube)
20. [Inclusion exclusion: Linear algebra view](https://invisiblenetwork.ai/learn/nptel/111106155/6e8f5d2eeb6f) (YouTube)
21. [Partial Orders](https://invisiblenetwork.ai/learn/nptel/111106155/74281914f433) (YouTube)
22. [Mobius Inversion Formula](https://invisiblenetwork.ai/learn/nptel/111106155/e0891644e9ea) (YouTube)
23. [Product theorem and applications of Mobius Inversion](https://invisiblenetwork.ai/learn/nptel/111106155/33fdbe003a0b) (YouTube)
24. [Formal power series, ordinary generating functions](https://invisiblenetwork.ai/learn/nptel/111106155/52e7b3d09ef3) (YouTube)
25. [Application of Ordinary generating functions](https://invisiblenetwork.ai/learn/nptel/111106155/da4ffda58719) (YouTube)
26. [Product of Generating functions](https://invisiblenetwork.ai/learn/nptel/111106155/1d8c75a55147) (YouTube)
27. [Composition of generating functions](https://invisiblenetwork.ai/learn/nptel/111106155/737d08bd9c29) (YouTube)
28. [Exponential Generating Function](https://invisiblenetwork.ai/learn/nptel/111106155/c9c336c1cbbc) (YouTube)
29. [Composition of EGF](https://invisiblenetwork.ai/learn/nptel/111106155/0f326b0454f2) (YouTube)
30. [Euler pentagonal number theorem](https://invisiblenetwork.ai/learn/nptel/111106155/1e29dbce5534) (YouTube)
31. [Graphs - introduction](https://invisiblenetwork.ai/learn/nptel/111106155/022ea620f446) (YouTube)
32. [Paths Walks, Cycles](https://invisiblenetwork.ai/learn/nptel/111106155/d8995ba2a352) (YouTube)
33. [Digraphs and functional digraphs](https://invisiblenetwork.ai/learn/nptel/111106155/15ecc45af9a4) (YouTube)
34. [Componenets, Connectivity, Bipartite graphs](https://invisiblenetwork.ai/learn/nptel/111106155/b54b1146ce57) (YouTube)
35. [Acyclic graphs](https://invisiblenetwork.ai/learn/nptel/111106155/58ce896996e8) (YouTube)
36. [Graph colouring](https://invisiblenetwork.ai/learn/nptel/111106155/3332113327de) (YouTube)
37. [Mycielski graphs](https://invisiblenetwork.ai/learn/nptel/111106155/96f60ec84036) (YouTube)
38. [Product of graphs](https://invisiblenetwork.ai/learn/nptel/111106155/66da06252a45) (YouTube)
39. [Menger's theorem](https://invisiblenetwork.ai/learn/nptel/111106155/4eb723b6fdf5) (YouTube)
40. [System of Distinct representatives](https://invisiblenetwork.ai/learn/nptel/111106155/58f242ee5239) (YouTube)
41. [Planar graphs](https://invisiblenetwork.ai/learn/nptel/111106155/03087a17327c) (YouTube)
42. [Euler identity](https://invisiblenetwork.ai/learn/nptel/111106155/bc3fdf4ad3d9) (YouTube)
43. [Map colouring problem - history](https://invisiblenetwork.ai/learn/nptel/111106155/1589a80fb075) (YouTube)
44. [The Discharging Method - part 1](https://invisiblenetwork.ai/learn/nptel/111106155/5feaba0ff66d) (YouTube)
45. [The Discharging Method - part 2](https://invisiblenetwork.ai/learn/nptel/111106155/71c43605c683) (YouTube)
46. [Introduction to Group actions](https://invisiblenetwork.ai/learn/nptel/111106155/c89f6a40f502) (YouTube)
47. [Colouring and symmetries - examples](https://invisiblenetwork.ai/learn/nptel/111106155/971717834239) (YouTube)
48. [Burnside's lemma](https://invisiblenetwork.ai/learn/nptel/111106155/12fe28790a0d) (YouTube)
49. [Proof of Burnsides lemma](https://invisiblenetwork.ai/learn/nptel/111106155/753d3f8d040f) (YouTube)
50. [Polya's theorem](https://invisiblenetwork.ai/learn/nptel/111106155/fdca80e15235) (YouTube)
51. [Species of structures- definitions and examples](https://invisiblenetwork.ai/learn/nptel/111106155/44ddbbb5f277) (YouTube)
52. [Associated seris and Product of species](https://invisiblenetwork.ai/learn/nptel/111106155/77d06a2b6702) (YouTube)
53. [Species: Substitution and Derivative](https://invisiblenetwork.ai/learn/nptel/111106155/e3f8a702a6ae) (YouTube)
54. [Species: Pointing and countilg labelled trees](https://invisiblenetwork.ai/learn/nptel/111106155/fb8757cffb7a) (YouTube)
55. [Review and Further directions](https://invisiblenetwork.ai/learn/nptel/111106155/16093b48fe7c) (YouTube)
56. [More on further topics](https://invisiblenetwork.ai/learn/nptel/111106155/d03bd256fcd0) (YouTube)
57. [Linear Algebra method: Ultra short introduction](https://invisiblenetwork.ai/learn/nptel/111106155/c986364c5b98) (YouTube)
58. [Probabiistic Method: Ultra short introduction](https://invisiblenetwork.ai/learn/nptel/111106155/af7b3ce52ba8) (YouTube)