LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
Generating Functions for Catalan Numbers
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

Generating Functions for Catalan Numbers

72 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
MIT · Principles of Discrete Applied Mathematics · LECTURE 7

Peter Shor, teaching MIT's 18.200 Principles of Discrete Applied Mathematics, derives the generating function for the Catalan numbers and uses it to produce the closed-form formula for the sequence. The lecture builds the generating function step by step from a recurrence relation, works through the algebra needed to solve for it explicitly, and then extracts the Catalan number formula from the resulting expression. As the seventh session in the course, it assumes familiarity with earlier material on generating functions and recurrences, and it runs a full seventy two minutes at blackboard pace, with Shor working through each derivation in detail rather than skipping steps. The content is squarely combinatorics, useful for students wanting a worked example of how generating functions turn a recursive definition into a direct formula.

At a glance

Lecture facts

Runtime compared with the other 305 Mathematics lectures
Runtime1 h 12 m
Compared with MathematicsShorter than 57%
This series

Principles of Discrete Applied Mathematics

Every lecture in order, sized by its length.

  • Earlier lectures
  • This lecture
  • Still to come
Lecture 7 of 197 h 34 m before this · 23 h 23 m in total

More from this course

12 LECTURES
Pigeonhole Principle

Pigeonhole Principle

MIT · 74 MIN
Lecture 2: Independence and Conditioning

Lecture 2: Independence and Conditioning

MIT · 71 MIN
Lecture 3: Inclusion-Exclusion

Lecture 3: Inclusion-Exclusion

MIT · 79 MIN
Lecture 4: Counting

Lecture 4: Counting

MIT · 78 MIN
More Counting and Generating Functions

More Counting and Generating Functions

MIT · 72 MIN
More on Generating Functions

More on Generating Functions

MIT · 80 MIN
Tail Bounds

Tail Bounds

MIT · 81 MIN
Lecture 9: Chernoff Bounds

Lecture 9: Chernoff Bounds

MIT · 55 MIN
Basic Group Theory

Basic Group Theory

MIT · 75 MIN
Introduction to Linear Programming

Introduction to Linear Programming

MIT · 74 MIN
Duality in Linear Programming

Duality in Linear Programming

MIT · 76 MIN
Zero-Sum Games

Zero-Sum Games

MIT · 74 MIN