| FazBrowse Wikipedia Viewer | Main Page | | |
| Viewing: https://en.wikipedia.org/wiki/Generating_function |
| Contents |
|---|
| Limitations |
| Poisson generating function |
| Bell series |
| Dirichlet series generating functions (DGFs) |
| Examples |
In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series. Generating functions are often expressed in closed form (rather than as a series), by some expression involving operations on the formal series.
There are various types of generating functions, including ordinary generating functions, exponential generating functions, Lambert series, Bell series, and Dirichlet series. Every sequence in principle has a generating function of each type (except that Lambert and Dirichlet series require indices to start at 1 rather than 0), but the ease with which they can be handled may differ considerably. The particular generating function, if any, that is most useful in a given context will depend upon the nature of the sequence and the details of the problem being addressed.
Generating functions are sometimes called generating series, in that a series of terms can be said to be the generator of its sequence of term coefficients.
x and composition with (i.e., substitution into) other generating functions; since these operations are also defined for functions, the result looks like a function of x.Not all expressions that are meaningful as functions of an is: an is fn+2 = fn+1 + fn. The corresponding exponential generating function has the form n! is merely a counter-term to normalise the derivative operator acting on ''n''</sup>"}},"i":0}}]}'/>x.
The Poisson generating function of a sequence ''n''</sub>"}},"i":0}}]}'/>an is
The Lambert series of a sequence ''n''</sub>"}},"i":0}}]}'/>an is bn:=[xn]LG(an;x)for integers |x|, |xq| < 1 we have that ∑n=1∞xn1−xn=∑n=1∞xn2(1+xn)1−xn.
The Bell series of a sequence ''n''</sub>"}},"i":0}}]}'/>an is an expression in terms of both an indeterminate BGp(an;x)=∑n=0∞apnxn.
Formal Dirichlet series are often classified as generating functions, although they are not strictly formal power series. The Dirichlet series generating function of a sequence ''n''</sub>"}},"i":0}}]}'/>an is: L-series. We also have a relation between the pair of coefficients in the Lambert series expansions above and their DGFs. Namely, we can prove that: ζ(s) is the Riemann zeta function.
The sequence k</sub>"}},"i":0}}]}'/>ak generated by a Dirichlet series generating function (DGF) corresponding to:exf(t)=∑n=0∞pn(x)n!tnwhere ''n''</sub>(''x'')"}},"i":0}}]}'/>pn(x) is a sequence of polynomials and F(0) = 1.
We say that a family of polynomials, 0</sub>, ''f''<sub>1</sub>, ''f''<sub>2</sub>, ..."}},"i":0}}]}'/>f0, f1, f2, ..., forms a convolution family if n</sub>'' ≤ ''n''"}},"i":0}}]}'/>deg fn ≤ n and if the following convolution condition holds for all n ≥ 0: fn(1) = [z] F(z) and n</sub>''(0) {{=}} ''δ''<sub>''n'',0</sub>"}},"i":0}}]}'/>fn(0) = δn,0, and
The left-hand side is the Maclaurin series expansion of the right-hand side. Alternatively, the equality can be justified by multiplying the power series on the left by 1 − x in the ring of power series.
Expressions for the ordinary generating function of other sequences are easily derived from this one. For instance, the substitution a: x by some power of x, x, x, ...) one gets the generating function n → n + 1, one sees that the coefficients form the sequence 1, 3, 6, 10, 15, 21, ... whose term ∑n=0∞(n+22)xn=1(1−x)3.
More generally, for any non-negative integer ∑n=0∞an(n+kk)xn=1(1−ax)k+1.
Since G(n2;x)=∑n=0∞n2xn=2(1−x)3−3(1−x)2+11−x=x(x+1)(1−x)3.
We may also expand alternately to generate this same sequence of squares as a sum of derivatives of the geometric series in the following form: nm=∑j=0m{mj}n!(n−j)!,
where }}"}},"i":0}}]}'/>{
k} denote the Stirling numbers of the second kind and where the generating function
zk(1−z)k+1=∑i=0k(ki)(−1)k−i(1−z)i+1,
we can apply a well-known finite sum identity involving the Stirling numbers to obtain that
The ordinary generating function of a sequence can be expressed as a rational function (the ratio of two finite-degree polynomials) if and only if the sequence is a linear recursive sequence with constant coefficients; this generalizes the examples above. Conversely, every sequence generated by a fraction of polynomials satisfies a linear recurrence with constant coefficients; these coefficients are identical to the coefficients of the fraction denominator polynomial (so they can be directly read off). This observation shows it is easy to solve for generating functions of sequences defined by a linear finite difference equation with constant coefficients, and then hence, for explicit closed-form formulas for the coefficients of these generating functions. The prototypical example here is to derive Binet's formula for the Fibonacci numbers via generating function techniques.
We also notice that the class of rational generating functions precisely corresponds to the generating functions that enumerate quasi-polynomial sequences of the form pi(n) is a polynomial in F(s,t):=∑m,n≥0f(m,n)wmzn
is a bivariate rational generating function, then its corresponding diagonal generating function,
Multiplication of ordinary generating functions yields a discrete convolution (the Cauchy product) of the sequences. For example, the sequence of cumulative sums (compare to the slightly more general Euler–Maclaurin formula) G(an;x)⋅11−x because m ≥ 1, we have the following two analogous identities for the modified generating functions enumerating the shifted sequence variants of ''n'' − ''m''</sub> ⟩"}},"i":0}}]}'/>⟨ gn − m ⟩ and ''n'' + ''m''</sub> ⟩"}},"i":0}}]}'/>⟨ gn + m ⟩, respectively: k times to multiply the sequence by ''k''</sup>"}},"i":0}}]}'/>n, but that requires alternating between differentiation and multiplication. If instead doing zkG(k)(z)=∑n=0∞nk_gnzn=∑n=0∞n(n−1)⋯(n−k+1)gnznfor all k∈ℕ.
Using the Stirling numbers of the second kind, that can be turned into another formula for multiplying by {fan + b} given an ordinary generating function 0 ≤ b < a, and a = 2, this is simply the familiar decomposition of a function into even and odd parts (i.e., even and odd powers): ωa = exp ∑n=0∞fan+bzan+b=1a∑m=0a−1ωa−mbF(ωamz).
For integers ∑n=0∞f⌊nm⌋zn=1−zm1−zF(zm)=(1+z+⋯+zm−2+zm−1)F(zm).
where the coefficients i</sub>''(''z'')"}},"i":0}}]}'/>ci(z) are in the field of rational functions, ℂ(z) spanned by the set of all of its derivatives is finite dimensional.
Since we can clear denominators if need be in the previous equation, we may assume that the functions, i</sub>''(''z'')"}},"i":0}}]}'/>ci(z) are polynomials in c^s(n)fn+s+c^s−1(n)fn+s−1+⋯+c^0(n)fn=0,
for all large enough 0</sub>"}},"i":0}}]}'/>n ≥ n0 and where the i</sub>''(''n'')"}},"i":0}}]}'/>ĉi(n) are fixed finite-degree polynomials in ⊙ on generating functions.
The functions ''z''</sup>"}},"i":0}}]}'/>e, arcsin z, pFq(...; ...; z) and the functions defined by the power series P-recursive sequences with holonomic generating functions include ''n''</sub> ≔ {{sfrac|1|''n'' + 1}} {{pars|s=150%|{{su|p=2''n''|b=''n''|a=c}}}}"}},"i":0}}]}'/>fn ≔ 2/n + 1, where sequences such as P-recursive due to the nature of singularities in their corresponding generating functions. Similarly, functions with infinitely many singularities such as Γ(z) are not holonomic functions.
| View original on Wikipedia | Back | FazBrowse Home |