Lecture 23 of 58Week 5
Product theorem and applications of Mobius Inversion
Prof. Narayanan N · IIT Madras
Credits and licence
- From
- Combinatorics, IIT Madras (at NPTEL)
- Licence
- CC BY-NC-SA, as NPTEL states it. Non-commercial use only.
- Attribution
- NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
- Who can watch
- Tweens profiles and older. How courses are placed
All the lectures
- Pigeonhole Principle
- Dirichlet theorem and Erdos-Szekeres Theorem
- Ramey theorem as generalisation of PHP
- An infinite flock of Pigeons
- Basic Counting - the sum and product rules
- Examples of basic counting
- Examples: Product and Division rules
- Binomial theorem and bijective counting
- Counting lattice paths
- Multinomial theorem
- Applying Multinomial theorem
- Integer compositions
- Set partitions and Stirling numbers
- Stirling and Hemachandra recursions
- Integer partitions
- Young's diagram and Integer partitions
- Principle of Inclusion and Exclusion
- Applications of PIE
- The twelvefold way
- Inclusion exclusion: Linear algebra view
- Partial Orders
- Mobius Inversion Formula
- Product theorem and applications of Mobius Inversion
- Formal power series, ordinary generating functions
- Application of Ordinary generating functions
- Product of Generating functions
- Composition of generating functions
- Exponential Generating Function
- Composition of EGF
- Euler pentagonal number theorem
- Graphs - introduction
- Paths Walks, Cycles
- Digraphs and functional digraphs
- Componenets, Connectivity, Bipartite graphs
- Acyclic graphs
- Graph colouring
- Mycielski graphs
- Product of graphs
- Menger's theorem
- System of Distinct representatives
- Planar graphs
- Euler identity
- Map colouring problem - history
- The Discharging Method - part 1
- The Discharging Method - part 2
- Introduction to Group actions
- Colouring and symmetries - examples
- Burnside's lemma
- Proof of Burnsides lemma
- Polya's theorem
- Species of structures- definitions and examples
- Associated seris and Product of species
- Species: Substitution and Derivative
- Species: Pointing and countilg labelled trees
- Review and Further directions
- More on further topics
- Linear Algebra method: Ultra short introduction
- Probabiistic Method: Ultra short introduction