Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Generating function"
m
 
(22 intermediate revisions by 15 users not shown)
Line 1: Line 1:
−
The idea behind generating functions is to represent a [[combinatorical]] [[function]] <math>A(k)</math> in terms of a [[polynomial function]] which is equivalent for all purposes. This function is:<br>
+
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>.
−
  <math>A(0)+A(1)x+A(2)x^2+A(3)x^3+...</math><br>where the coefficient <math>A(k)</math> of <math>x^k</math> is the number of ways an event ''k'' can occur.
 
  
−
==== Simple Example ====
+
== Simple Example ==
−
If we let <math>A(k)={n \choose k}</math> then we have:<br>
+
 
−
<math>{n \choose 0}+{n \choose 1}x + {n \choose 2}x^2+...+</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 ''k'' heads when flipping ''n'' 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>(plug in 1 for ''x''), also <math>{n \choose 1}+{n \choose 3}+...={n \choose 0}+{n \choose 2}+...</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>.
 +
 
 +
== 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]]
 +
* [[Polynomials]]
 +
* [[Series]]
 +
 
 +
== 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, $c_0, c_1, c_2, \ldots$, give the terms of a sequence which is 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$.

More Examples

Many generating functions can be derived using the sum formula for geometric series \[\frac{1}{1-x} = \sum_{k=0}^{\infty} x^k = 1 + x + x^2 + x^3 + \dots\] for $x \in (-1,1)$.

For example, using a change of variables, \[\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\] for $x \in \left( -\frac{1}{a}, \frac{1}{a} \right)$ (if $a > 0$) or $x \in \left( \frac{1}{a}, -\frac{1}{a} \right)$ (if $a < 0$), generating the powers of $a$ for any real $a$. The identity holds for all $x$ when $a = 0$, but the result is uninteresting (both the generating function and the desired power series are just $1$).

Taking the derivative and multiplying by $x$ gives a generating function for the nonnegative integers: \[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\] for $x \in (-1,1)$.

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$.

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 $1+x+x^2$, 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 $1+x+x^2$ and the generating function for the white egg basket is $1+x+x^2+x^3$. Now to find the number of ways to pick eggs from multiple baskets, just simply multiply the functions together, getting $1+3x+6x^2+8x^3+8x^4+6x^5+3x^6+x^7$. We want the number of ways to choose 4 eggs, so we just need to look at the coefficient of $x^4$ and see that there are 8 ways to choose 4 eggs.

See also

External Link

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Generating_function&oldid=172431"