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
m (generatings functions are power series, not polynomials in general)
Line 1: Line 1:
−
The idea behind generating functions is to represent a [[combinatorics|combinatorial]] [[function]] <math>A(k)</math> in terms of a [[polynomial]] [[function]] which is equivalent for all purposes. This function is <math>A(0)+A(1)x+A(2)x^2+A(3)x^3+\cdots</math>, where the coefficient <math>A(k)</math> of <math>x^k</math> is the number of ways an event <math>\displaystyle{k}</math> can occur.
+
The idea behind generating functions is to represent a [[combinatorics|combinatorial]] [[function]] <math>A(k)</math> in terms of a [[power series]] which is equivalent for all purposes. This function is <math>A(0)+A(1)x+A(2)x^2+A(3)x^3+\cdots</math>, where the coefficient <math>A(k)</math> of <math>x^k</math> is the number of ways an event <math>\displaystyle{k}</math> can occur.
  
 
== Simple Example ==
 
== Simple Example ==

Revision as of 20:13, 4 August 2006

The idea behind generating functions is to represent a combinatorial function $A(k)$ in terms of a power series which is equivalent for all purposes. This function is $A(0)+A(1)x+A(2)x^2+A(3)x^3+\cdots$, where the coefficient $A(k)$ of $x^k$ is the number of ways an event $\displaystyle{k}$ can occur.

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 $\displaystyle{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$.

See also

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