Counting Problems Using Generating Functions (Brute Force Method)

A generating power series (known as "Generating Functions"), according to Wikipedia, is a power series in one variable whose coefficients and exponents are natural numbers (positive integers). Generating Functions are used here to help us to solve a counting problem.

The video makes the case that generating functions can be used to solve counting problems where order does not matter and identical items exist. While it is more work than counting cases, many students will find this an easier way to solve the problem.

I refer to Generating Functions as a "Brute Force" method, because in performing the power series expansion, the student will actually be able to solve all possible questions with items chosen from the same set of objects.

However, if the number of items is restricted in the sense of "how many ways can I select at least one ball of each color", the polynomial needs to be modified (this is not demonstrated in the video for the sake of brevity). In such cases, each factor must not have constant terms (this is an order zero term, and zero items are not allowed), and the expansion of the polynomial factors done accordingly.

In all, the polynomial is used as a tool, with no attempt to find the value of x or know its graph. Use is made of the exponents and coefficients without need to know anything about x.

It must also be stated that my habit in this video of referring to the sample space to check my answers will work very well so long as the number of objects are small.

A typo happens at 1:11 where the graphical insert starts with order-zero, and skips the order-one term. Generating functions as I understand them always have sequential exponents starting from zero. This is a harmless error, as the graphical insert was used to show the uses of the parts of the terms in the polynomial. An actual expansion appears later where this appears to be avoided.

Special thanks to Steve Rayan and Matt Sourisseau at the University of Toronto Department of Mathematics who taught us Generating Functions during a seminar this summer.

There are many videos on YouTube that discuss generating functions, there may be some on the side bar on this web page.

[terryjames]

Great content, nice and easy, appreciate it!

[pn]

Really straightforward and helpful, thanks

[ewqdsacxz]

Is there only one correct way to expand the equations, or can they be expanded however one pleases as long as you end up getting the coefficients?