Difference between revisions of "Generating function"
ComplexZeta (talk | contribs) |
(added links) |
||
| 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 | + | 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. |
| − | |||
| − | + | == Simple Example == | |
| − | 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+ | + | 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 | + | |
| − | 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>( | + | This function can be described as the number of ways we can get <math>\displaystyle{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>. | ||
| + | |||
| + | === See also === | ||
| + | |||
| + | * [[Combinatorics]] | ||
| + | * [[Polynomials]] | ||
| + | * [[Series]] | ||
Revision as of 17:03, 19 June 2006
The idea behind generating functions is to represent a combinatorial function 
in terms of a polynomial function which is equivalent for all purposes. This function is 
, where the coefficient of 
is the number of ways an event 
can occur.
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 
.
