AoPSWiki

Our Precalculus course starts on Dec. 4. Master trig, complex numbers, and vectors and matrices in 2 and 3 dimensions. Click here to enroll today!

Personal tools

Log in

Search

Toolbox

Generating function

From AoPSWiki

(Redirected from Generating functions)

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

Looking for a challenging algebra text? Preparing for MATHCOUNTS or the AMC exams?
Check out Art of Problem Solving's Introduction to Algebra by Richard Rusczyk.

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