Generating function

The idea behind generating functions is to represent a combinatorical function $A(k)$ in terms of a polynomial function which is equivalent for all purposes. This function is:

 
where the coefficient  of  is the number of ways an event k can occur.

Simple Example

If we let $A(k)={n \choose k}$ then we have:
${n \choose 0}+{n \choose 1}x + {n \choose 2}x^2+...+$ ${n \choose n}x^n$ This function can be described as the number of ways we can get k heads when flipping n different coins. The reason to go to such lengths is that our above polynomial is equal to $(1+x)^n$ (which is clearly seen due to the Binomial Theorem). By using this equation, we can rapidly uncover identities such as ${n \choose 0}+{n \choose 1}+...+{n \choose n}=2^n$ (plug in 1 for x), also ${n \choose 1}+{n \choose 3}+...={n \choose 0}+{n \choose 2}+...$

Page

Toolbox

Search

Generating function

Simple Example