AoPSWiki

Trying to get to the USAMO in 2010? Our AIME Problem Series can help you get there! Click here to enroll today!

Personal tools

Log in

Search

Toolbox

Generating function

From AoPSWiki

The idea behind generating functions is to create a power series whose coefficients, $c_0, c_1, c_2, \ldots$ , give the terms of a sequence which of interest. Therefore the power series (i.e. the generating function) is $c_0 + c_1 x + c_2 x^2 + \cdots$ and the sequence is $c_0, c_1, c_2,\ldots$ .

Contents

1 Simple Example
2 Convolutions
3 See also
4 External Link

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+\cdots+$ ${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$ (let ${x}=1$ ), also ${n \choose 1}+{n \choose 3}+\cdots={n \choose 0}+{n \choose 2}+\cdots$ .

Convolutions

Suppose we have the sequences $a_0, a_1, a_2, ...$ and $b_0, b_1, b_2, ...$ . We can create a new sequence, called the convolution of $a$ and $b$ , defined by $c_n = a_0b_n + a_1b_{n-1} + ... + a_nb_0$ . Generating functions allow us to represent the convolution of two sequences as the product of two power series. If $A$ is the generating function for $a$ and $B$ is the generating function for $b$ , then the generating function for $c$ is $AB$ .

See also

External Link

generatingfunctionology

Retrieved from "http://www.artofproblemsolving.com/Wiki/index.php/Generating_function"

Categories: Combinatorics | Definition

Try our innovative online adaptive learning system, Alcumus.
Over 1100 problems and 60+ video lessons. FREE!

© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us