# Lecture 15: Counting problems and generating functions

Taught by ArsDigita
• Currently 4.0/5 Stars.
5701 views | 1 rating
Part of video series
Lesson Description:

More counting problems solved with generating functions.

Licensed under Creative Commons Attribution ShareAlike 2.0:

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.