Difference between revisions of "Generating function"

 
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> <math>A(0)+A(1)x+A(2)x^2+A(3)x^+...</math>
+
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>
 +
  <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 ====
 +
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>
 +
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>

Revision as of 23:59, 18 June 2006

The idea behind generating functions is to represent a combinatorical function $A(k)$ in terms of a polynomial function which is equivalent for all purposes. This function is:

 $A(0)+A(1)x+A(2)x^2+A(3)x^3+...$
where the coefficient $A(k)$ of $x^k$ is the number of ways an event 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+...+$${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$(plug in 1 for x), also ${n \choose 1}+{n \choose 3}+...={n \choose 0}+{n \choose 2}+...$