Introduction to Enumerative Combinatorics

  • 4.7
Approx. 111 hours to complete

Course Summary

This course focuses on the study of enumerative combinatorics, a branch of mathematics that deals with counting and arranging objects.

Key Learning Points

  • Learn how to count and analyze combinatorial structures such as permutations, combinations, and partitions
  • Understand the theory of generating functions and how they can be used to solve combinatorial problems
  • Gain insights into the application of combinatorics in various fields such as computer science, physics, and biology

Related Topics for further study


Learning Outcomes

  • Develop a deep understanding of the fundamental principles of enumerative combinatorics
  • Learn how to apply combinatorial techniques to solve real-world problems
  • Acquire the skills necessary to pursue further studies in combinatorics and related fields

Prerequisites or good to have knowledge before taking this course

  • Familiarity with basic algebra and calculus
  • Comfort with mathematical proofs and concepts

Course Difficulty Level

Advanced

Course Format

  • Self-paced
  • Online
  • Video Lectures
  • Assignments

Similar Courses

  • Applied Combinatorics
  • Combinatorics and Probability

Related Education Paths


Notable People in This Field

  • Herbert Wilf
  • Ronald Graham

Related Books

Description

Enumerative combinatorics deals with finite sets and their cardinalities. In other words, a typical problem of enumerative combinatorics is to find the number of ways a certain pattern can be formed.

Outline

  • Introduction
  • About the University
  • Introduction
  • About University
  • Rules on the academic integrity in the course
  • Course Overview
  • Grading and Logistics
  • Suggested Readings
  • About the Instructor
  • Permutations and binomial coefficients
  • Words
  • Permutations
  • k-permutations
  • Merry-go-rounds and Fermat’s little theorem 1
  • Merry-go-rounds and Fermat’s little theorem 2
  • Binomial coefficients
  • The Pascal triangle
  • Quiz 2
  • Binomial coefficients, continued. Inclusion and exclusion formula.
  • The cab driver problem
  • Balls in boxes and multisets 1
  • Balls in boxes and multisets 2
  • Integer compositions
  • Principle of inclusion and exclusion: two examples
  • Principle of inclusion and exclusion: general statement
  • The derangement problem
  • Quiz 3
  • Linear recurrences. The Fibonacci sequence
  • Fibonacci’s rabbit problem
  • Fibonacci numbers and the Pascal triangle
  • Domino tilings
  • Vending machine problem
  • Linear recurrence relations: definition
  • The characteristic equation
  • Linear recurrence relations of order 2
  • The Binet formula
  • Sidebar: the golden ratio
  • Linear recurrence relations of arbitrary order
  • The case of roots with multiplicities
  • Spoilers! Solutions for quizzes 2, 3, and 4.
  • Quiz 4
  • A nonlinear recurrence: many faces of Catalan numbers
  • Triangulations of a polygon
  • Recurrence relation for triangulations
  • The cashier problem
  • Dyck paths
  • Recurrence relations for Dyck paths
  • Reflection trick and a formula for Catalan numbers
  • Binary trees
  • Solutions
  • !!!Solutions for the older version of the Middterm
  • Generating functions: a unified approach to combinatorial problems. Solving linear recurrences
  • Generating functions: first examples
  • Formal power series
  • When are formal power series invertible?
  • Derivation of formal power series
  • Binomial theorem for negative integer exponents
  • Solving the Fibonacci recurrence relation
  • Solving the Fibonacci recurrence 2: Binet formula
  • Generating functions of linear recurrence relations are rational
  • Solving linear recurrence relations: general case
  • Math expressions
  • Quiz 6
  • Generating functions, continued. Generating function of the Catalan sequence
  • Composition of formal power series
  • Derivation and integration of formal power series
  • Chain rule. Inverse function theorem
  • Logarithm. Logarithmic derivative
  • Binomial theorem for arbitrary exponents
  • Generating function for Catalan numbers
  • Quiz 7
  • Partitions. Euler’s generating function for partitions and pentagonal formula
  • Definition and first examples
  • Young diagrams
  • Generating function for partitions
  • Partitions with odd and distinct summands
  • Sylvester’s bijection
  • Euler’s pentagonal theorem
  • Proof of Euler’s pentagonal theorem 1
  • Proof of Euler’s pentagonal theorem 2
  • Computing the number of partitions via the pentagonal theorem
  • Spoilers! Solutions for quizzes 6, 7, and 8.
  • Quiz 8
  • Gaussian binomial coefficients. “Quantum” versions of combinatorial identities
  • Generating function for partitions inside a rectangle
  • q-binomial coefficients: definition and first properties
  • Recurrence relation for q-binomial coefficients 1
  • Recurrence relation for q-binomial coefficients 2
  • Explicit formula for q-binomial coefficients
  • Euler’s partition function
  • Sidebar: q-binomial coefficients in linear algebra
  • q-binomial theorem
  • Solutions
  • !!!Solutions for the older version of the Final

Summary of User Reviews

Read reviews on the Enumerative Combinatorics course offered by Coursera. The course has received positive feedback from users. Many users appreciated the comprehensive nature of the course and how well it was taught.

Key Aspect Users Liked About This Course

Comprehensive nature of the course

Pros from User Reviews

  • Course is well-structured and easy to follow
  • Instructors are knowledgeable and engaging
  • Materials are presented in an organized and clear manner

Cons from User Reviews

  • Some users found the pace of the course to be too slow
  • Not enough opportunities for hands-on practice
  • Some users felt that the course was too theoretical
English
Available now
Approx. 111 hours to complete
Evgeny Smirnov
HSE University
Coursera

Instructor

Evgeny Smirnov

  • 4.7 Raiting
Share
Saved Course list
Cancel
Get Course Update
Computer Courses