Lecture 15: Counting problems and generating functions

Sick of ads?‚Äč Sign up for MathVids Premium
Taught by ArsDigita
  • Currently 4.0/5 Stars.
5729 views | 1 rating
Lesson Summary:

In this lesson, the concept of generating functions is introduced as a technique to solve recurrence equations, but it is stressed that understanding the fundamentals of counting is necessary before leveraging the power of generating functions. The process of using generating functions is explained as a way to connect algebraic formulas with counting problems, and a problem of distributing cookies to children is used as an example to demonstrate the connection between algebra and counting. While using generating functions may not always provide an easier solution than other methods, it allows for a deeper understanding of the mathematical concepts at play.

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.