Difference between revisions of "Generating function"

(6 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{WotWAnnounce|week=Nov 15-21}}
 
 
 
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.wisc.edu/~propp/491/gfologyLinked.pdf generatingfunctionology] a PDF version
+
 
 +
== 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, $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$.

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

Invalid username
Login to AoPS