Difference between revisions of "Generating function"
ComplexZeta (talk | contribs) m (generatings functions are power series, not polynomials in general) |
m |
||
(15 intermediate revisions by 11 users not shown) | |||
Line 1: | Line 1: | ||
− | The idea behind generating functions is to | + | 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 is 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>. |
== Simple Example == | == Simple Example == | ||
Line 5: | Line 5: | ||
If we let <math>A(k)={n \choose k}</math>, then we have <math>{n \choose 0}+{n \choose 1}x + {n \choose 2}x^2+\cdots+</math><math>{n \choose n}x^n</math>. | If we let <math>A(k)={n \choose k}</math>, then we have <math>{n \choose 0}+{n \choose 1}x + {n \choose 2}x^2+\cdots+</math><math>{n \choose n}x^n</math>. | ||
− | This function can be described as the number of ways we can get <math> | + | This function can be described as the number of ways we can get <math>{k}</math> heads when flipping <math>n</math> different coins. |
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 | + | == More Examples == |
+ | |||
+ | Many generating functions can be derived using the [[Geometric sequence#Infinite|sum formula for geometric series]] <cmath>\frac{1}{1-x} = \sum_{k=0}^{\infty} x^k = 1 + x + x^2 + x^3 + \dots</cmath> for <math>x \in (-1,1)</math>. | ||
+ | |||
+ | For example, using a change of variables, <cmath>\frac{1}{1-ax} = \sum_{k=0}^{\infty} (ax)^k = \sum_{k=0}^{\infty} a^kx^k = 1 + ax + a^2x^2 + a^3x^3 + \dots</cmath> for <math>x \in \left( -\frac{1}{a}, \frac{1}{a} \right)</math> (if <math>a > 0</math>) or <math>x \in \left( \frac{1}{a}, -\frac{1}{a} \right)</math> (if <math>a < 0</math>), generating the powers of <math>a</math> for any real <math>a</math>. The identity holds for all <math>x</math> when <math>a = 0</math>, but the result is uninteresting (both the generating function and the desired power series are just <math>1</math>). | ||
+ | |||
+ | Taking the [[derivative]] and multiplying by <math>x</math> gives a generating function for the nonnegative integers: <cmath>x \left( \frac{1}{1-x} \right) ' = \frac{x}{(1-x)^2} = \sum_{k=0}^{\infty} kx^k = 0 + x + 2x^2 + 3x^3 + \dots</cmath> for <math>x \in (-1,1)</math>. | ||
+ | |||
+ | == 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>. | ||
+ | |||
+ | == Simple Exercises == | ||
+ | |||
+ | 1. There are three baskets on the ground: one has 2 purple eggs, one has 2 green eggs, and one has 3 white eggs. Eggs of the same color are indistinguishable. In how many ways can I choose 4 eggs from the baskets? | ||
+ | |||
+ | Solution for problem 1: The generating function for the first basket is <math>1+x+x^2</math>, since there is one way to choose 0 purple eggs (do nothing), 1 way to choose 1 purple egg (since eggs are indistinguishable), and 1 way to choose 2 purple eggs. In a similar fashion the generating function for the green egg basket is <math>1+x+x^2</math> and the generating function for the white egg basket is <math>1+x+x^2+x^3</math>. Now to find the number of ways to pick eggs from multiple baskets, just simply multiply the functions together, getting <math>1+3x+6x^2+8x^3+8x^4+6x^5+3x^6+x^7</math>. We want the number of ways to choose 4 eggs, so we just need to look at the coefficient of <math>x^4</math> and see that there are 8 ways to choose 4 eggs. | ||
+ | |||
+ | == See also == | ||
* [[Combinatorics]] | * [[Combinatorics]] | ||
* [[Polynomials]] | * [[Polynomials]] | ||
* [[Series]] | * [[Series]] | ||
− | * [http://www.math. | + | |
+ | == External Link == | ||
+ | *[http://www.math.upenn.edu/~wilf/DownldGF.html generatingfunctionology] | ||
+ | |||
+ | [[Category:Combinatorics]] | ||
+ | [[Category:Definition]] |
Latest revision as of 11:54, 7 March 2022
The idea behind generating functions is to create a power series whose coefficients, , give the terms of a sequence which is of interest. Therefore the power series (i.e. the generating function) is and the sequence is .
Contents
[hide]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 .
More Examples
Many generating functions can be derived using the sum formula for geometric series for .
For example, using a change of variables, for (if ) or (if ), generating the powers of for any real . The identity holds for all when , but the result is uninteresting (both the generating function and the desired power series are just ).
Taking the derivative and multiplying by gives a generating function for the nonnegative integers: for .
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 .
Simple Exercises
1. There are three baskets on the ground: one has 2 purple eggs, one has 2 green eggs, and one has 3 white eggs. Eggs of the same color are indistinguishable. In how many ways can I choose 4 eggs from the baskets?
Solution for problem 1: The generating function for the first basket is , since there is one way to choose 0 purple eggs (do nothing), 1 way to choose 1 purple egg (since eggs are indistinguishable), and 1 way to choose 2 purple eggs. In a similar fashion the generating function for the green egg basket is and the generating function for the white egg basket is . Now to find the number of ways to pick eggs from multiple baskets, just simply multiply the functions together, getting . We want the number of ways to choose 4 eggs, so we just need to look at the coefficient of and see that there are 8 ways to choose 4 eggs.