Difference between revisions of "Generating function"
m |
|||
(5 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 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 8: | Line 8: | ||
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>. | ||
+ | |||
+ | == 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 == | == 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>. | 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 == | == See also == | ||
Line 19: | Line 33: | ||
== External Link == | == External Link == | ||
− | *[http://www.math.upenn.edu/~wilf/DownldGF.html | + | *[http://www.math.upenn.edu/~wilf/DownldGF.html generatingfunctionology] |
+ | |||
+ | [[Category:Combinatorics]] | ||
+ | [[Category:Definition]] |
Latest revision as of 12: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
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.