Generating Function

In mathematics, given a sequence a_0, a_1, a_2, ..., a_i, ..., the GeneratingFunction is the series:

\sum_{i = 0}^{\infty} a_i x^i.

GeneratingFunctions appear in combinatorics, probability theory, and in theoretical computer science. They often provide good ways of computing a series when simple enumeration would be slow. Examples:

 Binomial(n, k), n fixed --> (1 + x)^n

FibonacciSequence       --> x/(1-x-x^2)


Number of ways to make change of k cents given coins worth 1, 5, 10, 25 cents

                         --> 1/[(1-x)(1-x^5)(1-x^10)(1-x^25)]


To use the last, you could try using partial fractions. Unfortunately, that won't work out too well.

-- EricJablow

EditText of this page (last edited July 1, 2003) or FindPage with title or text search