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/
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
Currently 4.0/5 Stars.
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.