YoVDO

Combinatorics

Offered By: Indian Institute of Technology Madras via Swayam

Tags

Combinatorics Courses Graph Theory Courses Generating Functions Courses Pigeonhole Principle Courses

Course Description

Overview

We start with the finite and infinite avatars ofthe Pigeonhole Principle, Basic counting tools and the twelvefold way followed bycompositionsand partitions ofintegers and Stirlingnumbers.We then look atInclusion exclusion and Mobius inversion followed by generatingfunctions.We thenlook atPolya'stheorem,graphs andconclude witha short introduction to species of structures.INTENDED AUDIENCE :UG studentsPRE-REQUISITES : Basic Mathematical Maturity expected from a Mathematics student at the level of 10+2. Familiarity with group theory will be addedadvantage (not necessary).INDUSTRY SUPPORT : TCS, Infosys, Microsoft Research, Any companies developing discrete mathematics related areas or algorithms.

Syllabus

Week 1 : Pigeonhole Principle

Week 2 :BasicandBijectivecounting.

Week 3 : Compositions and Partitions.

Week 4 : Advanced Counting.

Week 5 : Inclusion Exclusion, Mobius Inversion.

Week 6 : Generating Functions

Week 7 : Graph theory,introduction, trees, connectivity.

Week 8 : Menger, Hall, Konig - equivalence and System of Distinct Representatives.

Week 9 : Planar graphs.

Week 10: Groups and Polya theory.

Week 11: Species of structures.

Week 12: An overview, scope and further directions.


Taught by

Prof. Narayanan N

Tags

Related Courses

Combinatorial Mathematics | 组合数学
Tsinghua University via edX
Problem Solving Techniques
YouTube
Discrete Math II - Combinatorics
Kimberly Brehm via YouTube
Discrete Mathematical Structures
NIOS via YouTube
A Brief Tour of Proof Complexity - Lower Bounds and Open Problems - Toniann Pitassi
Institute for Advanced Study via YouTube