Generating Functions · Generating Functions
Lesson 7
A generating function for a sequence \[\{a_{n}\}_{n=0}^{\infty}=(a_{0}, a_{1}, \dotsc)\] is defined as the formal power series \[\mathcal{A}(x)=a_{0}+a_{1}x+a_{2}x^{2}+\dotsb=\sum_{n=0}^{\infty}a_{n}x^{n} \ .\] We will use the following notation to extract the coefficient \(a_{n}\) of the \(n\)-th power of the formal variable \(x\): \[a_{n}=[x^{n}]\mathcal{A}(x) \ .\]
For the curious 🤓
In literature, such generating functions are sometimes called ordinary. This is done to emphasize that there are other types of generating functions (e.g., exponential generating functions and Dirichlet generating functions).