Lecture 15: Counting problems and generating functions
5701 views
|
1
rating
Lesson Description:
More counting problems solved with generating functions.
More information about this course:
http://www.aduni.org/courses/discrete
Licensed under Creative Commons Attribution ShareAlike 2.0:
http://creativecommons.org/licenses/by-sa/2.0/
Additional Resources:
- Lecture Notes - Lecture Notes from the course
- Problem Set 6 - A problem set with some problems from this lecture
- Problem Set 7 - A problem set with some problems from this lecture
Questions answered by this video:
- What are generating functions and how can they be used for counting problems?
- What is the generating function for the sequence of triangle numbers?
- What are the generating functions for rows of Pascal's Triangle?
- In how many ways can you distribute 8 cookies to 3 kids if each kid gets between 2 and 4 cookies?
- What is the generating function for the sequence A(n) = 1?
- What does the geometric series generating function 1/(1 - ax) look like as a polynomial?
- What is the resulting polynomial for the generating function 1/(1 - x)^2 = (1 + x + x^2 + x^3 + ...)*(1 + x + x^2 + x^3 + ...)?
- What happens when you multiply a polynomial or generating function by 1/(1 - x)?
- What are partial sums, and how do you obtain them with generating functions?
- What are the generating functions for the diagonals of Pascal's Triangle?
- What happens when you shift a generating function by multiplying by x?
- How many base 10 numbers are there with n digits and an even number of 0s?
-
Staff Review
Generating functions are explained and used to more easily solve some problems that have been done in previous lectures. It turns out that generating function in Algebra have a lot to do with counting problems. A good background in Algebra and geometric series is necessary to understand this lecture.
