Generating Function

(redirected from Ordinary generating functions)

generating function

[′jen·ə‚rād·iŋ ‚fəŋk·shən]
A function g (x, y) corresponding to a family of orthogonal polynomials ƒ0(x), ƒ1(x),…, where a Taylor series expansion of g (x, y) in powers of y will have the polynomial ƒn (x) as the coefficient for the term y n .
A function, g (y), corresponding to a sequence a0, a1, ⋯) where g (y) = a0+ a1 y + a2 y 2+ …. Also known as ordinary generating function.

Generating Function


A generating function of the sequence f0, f1,..., fn is the function

assuming that this power series converges for at least one nonzero value of t.

The sequence f0, f1,..., fn,… can be a sequence of numbers or of functions. In the latter case, the generating function depends not only on t but also on the arguments of the functions fn. For example, if fn = aqn, where a and q are constants, the generating function is

If the fn are Fibonacci numbers—that is, if f0 = 0, f1 = 1, fn+2 = fn+1 + fn—we have

If fn = Tn (x) are Chebyshev polynomials—that is, if T0(x) = 1

and Tn (x) = cos (n arc cos x)—then

Knowledge of the generating function of a sequence often makes it easier to study the properties of the sequence. Generating functions are used in probability theory, in the theory of functions, and in the theory of invariants in algebra. Methods involving generating functions were first applied by P. Laplace to solve certain problems in probability theory.


Feller, W. Vvedenie v teoriiu veroiatnostei i eeprilozheniia, 2nd ed., vols. 1–2. Moscow, 1967. (Translated from English.)
Natanson, I. P. Konstruktivnaia teoriia funktsii. Moscow-Leningrad, 1949.
References in periodicals archive ?
Let us remark that the reason for the use of exponential generating functions, rather than ordinary generating functions (o.g.f.), is simplicity of transfer rules in the domain of labelled classes.
Most recently, Marberg (10) extended the result to coloured set partitions with a novel way of proving that the ordinary generating functions of j- noncrossing, k-nonnesting, r-coloured partitions according to size n are rational functions.
The transfer matrix approach Marberg used to establish the rationality of the ordinary generating function, [[summation].sub.n [greater than or equal to] 0] NC[N.sub.j,k] (n + 1, r)[x.sup.n] for set partitions of size n +1 is through translating the original problem to counting all closed walks of n-steps with certain column and row length restrictions (according to j, k) for each component from [empty set] [member of] [Y.sup.r], that is, r copies of the Hasse diagram of the Young lattice.
Let K be an adequate class with unlabelled count functions and ordinary generating functions as described above.
Thus the radius of convergence of the ordinary generating function of K is [[rho].sub.U] = 3[square root of 2].
In Section 3, we describe the transformation T that turns certain ordinary generating functions into Laguerre series.
Using the transformations T and [PHI], we can reduce the problem to finding ordinary generating functions for factorizations that only use one symbol and avoid the given vincular pattern.