Difference between revisions of "Generating function"
ComplexZeta (talk | contribs) m |
ComplexZeta (talk | contribs) 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 [[ | + | 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 in terms of a power series 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
.
See also
- Combinatorics
- Polynomials
- Series
- generatingfunctionology a PDF version