Difference between revisions of "Generating function"
| (6 intermediate revisions by 4 users not shown) | |||
| Line 1: | Line 1: | ||
| − | |||
| − | |||
The idea behind '''generating functions''' is to create a [[power series]] whose [[coefficient]]s, <math>c_0, c_1, c_2, \ldots</math>, give the terms of a [[sequence]] which of interest. Therefore the power series (i.e. the generating function) is <math>c_0 + c_1 x + c_2 x^2 + \cdots </math> and the sequence is <math>c_0, c_1, c_2,\ldots</math>. | The idea behind '''generating functions''' is to create a [[power series]] whose [[coefficient]]s, <math>c_0, c_1, c_2, \ldots</math>, give the terms of a [[sequence]] which of interest. Therefore the power series (i.e. the generating function) is <math>c_0 + c_1 x + c_2 x^2 + \cdots </math> and the sequence is <math>c_0, c_1, c_2,\ldots</math>. | ||
| Line 11: | Line 9: | ||
The reason to go to such lengths is that our above polynomial is equal to <math>(1+x)^n</math> (which is clearly seen due to the [[Binomial Theorem]]). By using this equation, we can rapidly uncover identities such as <math>{n \choose 0}+{n \choose 1}+...+{n \choose n}=2^n</math>(let <math>{x}=1</math>), also <math>{n \choose 1}+{n \choose 3}+\cdots={n \choose 0}+{n \choose 2}+\cdots</math>. | The reason to go to such lengths is that our above polynomial is equal to <math>(1+x)^n</math> (which is clearly seen due to the [[Binomial Theorem]]). By using this equation, we can rapidly uncover identities such as <math>{n \choose 0}+{n \choose 1}+...+{n \choose n}=2^n</math>(let <math>{x}=1</math>), also <math>{n \choose 1}+{n \choose 3}+\cdots={n \choose 0}+{n \choose 2}+\cdots</math>. | ||
| − | === See also | + | == Convolutions == |
| + | Suppose we have the sequences <math>a_0, a_1, a_2, ...</math> and <math>b_0, b_1, b_2, ...</math>. We can create a new sequence, called the convolution of <math>a</math> and <math>b</math>, defined by <math>c_n = a_0b_n + a_1b_{n-1} + ... + a_nb_0</math>. Generating functions allow us to represent the convolution of two sequences as the product of two power series. If <math>A</math> is the generating function for <math>a</math> and <math>B</math> is the generating function for <math>b</math>, then the generating function for <math>c</math> is <math>AB</math>. | ||
| + | |||
| + | == See also == | ||
* [[Combinatorics]] | * [[Combinatorics]] | ||
* [[Polynomials]] | * [[Polynomials]] | ||
* [[Series]] | * [[Series]] | ||
| − | * [http://www.math. | + | |
| + | == External Link == | ||
| + | *[http://www.math.upenn.edu/~wilf/DownldGF.html GeneratingFunctionology] | ||
Revision as of 17:21, 23 November 2007
The idea behind generating functions is to create a power series whose coefficients, 
, give the terms of a sequence which of interest. Therefore the power series (i.e. the generating function) is 
and the sequence is 
.
Simple Example
If we let 
, then we have 
.
This function can be described as the number of ways we can get 
heads when flipping 
different coins.
The reason to go to such lengths is that our above polynomial is equal to 
(which is clearly seen due to the Binomial Theorem). By using this equation, we can rapidly uncover identities such as 
(let 
), also 
.
Convolutions
Suppose we have the sequences 
and 
. We can create a new sequence, called the convolution of 
and 
, defined by 
. Generating functions allow us to represent the convolution of two sequences as the product of two power series. If 
is the generating function for and 
is the generating function for , then the generating function for 
is 
.
