Lecture 15: Counting problems and generating functions

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.

More counting problems solved with generating functions.

• 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?