Lecture 15: Counting problems and generating functions

Sick of ads?‚Äč Sign up for MathVids Premium
Taught by ArsDigita
  • Currently 4.0/5 Stars.
5682 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:
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.