generating function

(Combinatorics, mostly:) Given a sequence {a_n}, one way of expressing the properties of the entire sequence is by defining its generating function

A(z) = a₀ + z a₁ + z² a₂ + ... + zⁿ a_n + ...

A(z) can be defined for real z, or for complex z; it might not be defined for large |z|, and it might not be defined for z != 0... In the last case, however, getting meaningful results out of expressions for A(z) might be tricky. It's still possible when there is some other field or domain where the infinite sum is meaningful.

Now analysing the sequence {a_n} reduces to analysing A(z). For example, if {a_n} satisfies a recurrence relation

a_n = c₁ a_n-1 + c₂ a_n-2 + ... + c_k a_n-k

A few generating functions are tabulated below. Plese see the WU on Bessel functions for an example of how generating functions may be used to immense benefit.

Bessel functions:sum(J_ntⁿ) = e^{(x/2)*(t-1/t)}
Legendre Polynomials:sum(P_ntⁿ)=(1-2tx+t²)^(-1/2)
Laguerre Polynomials:sum(L_ntⁿ)= (1-t)^(-1)e^-(xt/1-t)
Hermite polynomials:sum(H_ntⁿ/n!)=e^{-t^2 + 2tx}

Note the extra n! in the relation for Hermite polynomials. It is put there by convention. Arfken or Abramowitz would provide a good introduction to Special Functions in general.

Functions can also be used to generate sets of strings. This is what grammars do in formal language theory.

There are also graph grammars, grammars on commutative strings, and on other kinds of objects.

A related subject is inference rules in logic. Inference rules can often be seen as functions to generate sets of logical propositions from an initial set. Such an inference is a deduction (logical derivation, proof). One way to look at different systems of logic is to think of them as systems of generating functions of propositions. The study of their mathematical properties is often nontrivial and of great practical relevance - in particular, in the case of systems for automated reasoning, the study of computational aspects such as the efficiency with which derivations can be obtained.