Editing Generating function (section)

==Types==

===Ordinary generating function (OGF)===

When the term ''generating function'' is used without qualification, it is usually taken to mean an ordinary generating function. The ''ordinary generating function'' of a sequence {{math|''a''<sub>''n''</sub>}} is:
<math display="block">G(a_n;x)=\sum_{n=0}^\infty a_n x^n.</math>
If {{math|''a''<sub>''n''</sub>}} is the [[probability mass function]] of a [[discrete random variable]], then its ordinary generating function is called a [[probability-generating function]].

===Exponential generating function (EGF)===

The ''exponential generating function'' of a sequence {{math|''a''<sub>''n''</sub>}} is
<math display="block">\operatorname{EG}(a_n;x)=\sum_{n=0}^\infty a_n \frac{x^n}{n!}.</math>

Exponential generating functions are generally more convenient than ordinary generating functions for [[combinatorial enumeration]] problems that involve labelled objects.<ref>{{harvnb|Flajolet|Sedgewick|2009|p=95}}</ref>

Another benefit of exponential generating functions is that they are useful in transferring linear [[recurrence relations]] to the realm of [[differential equations]]. For example, take the [[Fibonacci sequence]] {{math|{''f<sub>n</sub>''}<nowiki/>}} that satisfies the linear recurrence relation {{math|''f''<sub>''n''+2</sub> {{=}} ''f''<sub>''n''+1</sub> + ''f''<sub>''n''</sub>}}. The corresponding exponential generating function has the form
<math display="block">\operatorname{EF}(x) = \sum_{n=0}^\infty \frac{f_n}{n!} x^n</math>

and its derivatives can readily be shown to satisfy the differential equation {{math|EF{{pprime}}(''x'') {{=}} EF{{prime}}(''x'') + EF(''x'')}} as a direct analogue with the recurrence relation above. In this view, the factorial term {{math|''n''!}} is merely a counter-term to normalise the derivative operator acting on {{math|''x''<sup>''n''</sup>}}.

===Poisson generating function===
The ''Poisson generating function'' of a sequence {{math|''a''<sub>''n''</sub>}} is
<math display="block">\operatorname{PG}(a_n;x)=\sum _{n=0}^\infty a_n e^{-x} \frac{x^n}{n!} = e^{-x}\, \operatorname{EG}(a_n;x).</math>

===Lambert series===
{{main article|Lambert series}}

The ''Lambert series'' of a sequence {{math|''a''<sub>''n''</sub>}} is
<math display="block">\operatorname{LG}(a_n;x)=\sum _{n=1}^\infty a_n \frac{x^n}{1-x^n}.</math>Note that in a Lambert series the index {{mvar|n}} starts at 1, not at 0, as the first term would otherwise be undefined. 

The Lambert series coefficients in the power series expansions
<math display="block">b_n := [x^n] \operatorname{LG}(a_n;x)</math>for integers {{math|''n'' ≥ 1}} are related by the [[Divisor sum identities|divisor sum]]
<math display="block">b_n = \sum_{d|n} a_d.</math>The [[Lambert series|main article]] provides several more classical, or at least well-known examples related to special [[arithmetic functions]] in [[number theory]]. As an example of a Lambert series identity not given in the main article, we can show that for {{math|{{abs|''x''}}, {{abs|''xq''}} < 1}} we have that <ref>{{cite web |date=2017 |title=Lambert series identity |url=https://mathoverflow.net/q/140418 |website=Math Overflow}}</ref><math display="block">\sum_{n = 1}^\infty \frac{q^n x^n}{1-x^n} = \sum_{n = 1}^\infty \frac{q^n x^{n^2}}{1-q x^n} + \sum_{n = 1}^\infty \frac{q^n x^{n(n+1)}}{1-x^n}, </math>

where we have the special case identity for the generating function of the [[divisor function]], {{math|''d''(''n'') ≡ ''σ''<sub>0</sub>(''n'')}}, given by<math display="block">\sum_{n = 1}^\infty \frac{x^n}{1-x^n} = \sum_{n = 1}^\infty \frac{x^{n^2} \left(1+x^n\right)}{1-x^n}. </math>

===Bell series===

The [[Bell series]] of a sequence {{math|''a''<sub>''n''</sub>}} is an expression in terms of both an indeterminate {{mvar|x}} and a prime {{mvar|p}} and is given by:<ref>{{Apostol IANT}} pp.42–43</ref>
<math display="block">\operatorname{BG}_p(a_n;x) = \sum_{n=0}^\infty a_{p^n}x^n.</math>

===Dirichlet series generating functions (DGFs)===

[[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 {{math|''a''<sub>''n''</sub>}} is:<ref name="W56">{{harvnb|Wilf|1994|p=56}}</ref>
<math display="block">\operatorname{DG}(a_n;s)=\sum _{n=1}^\infty \frac{a_n}{n^s}.</math>

The Dirichlet series generating function is especially useful when {{math|''a''<sub>''n''</sub>}} is a [[multiplicative function]], in which case it has an [[Euler product]] expression<ref name="W59">{{harvnb|Wilf|1994|p=59}}</ref> in terms of the function's Bell series:
<math display="block">\operatorname{DG}(a_n;s)=\prod_{p} \operatorname{BG}_p(a_n;p^{-s})\,.</math>

If {{math|''a''<sub>''n''</sub>}} is a [[Dirichlet character]] then its Dirichlet series generating function is called a [[Dirichlet L-series|Dirichlet {{mvar|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:
<math display="block">[x^n] \operatorname{LG}(a_n; x) = b_n</math>if and only if
<math display="block">\operatorname{DG}(a_n;s) \zeta(s) = \operatorname{DG}(b_n;s),</math>where {{math|''ζ''(''s'')}} is the [[Riemann zeta function]].<ref>{{cite book |last1=Hardy |first1=G.H. |last2=Wright |first2=E.M. |last3=Heath-Brown |first3=D.R |last4=Silverman |first4=J.H. |title=An Introduction to the Theory of Numbers|url=https://archive.org/details/introductiontoth00ghha_922|url-access=limited|publisher=Oxford University Press |page=[https://archive.org/details/introductiontoth00ghha_922/page/n357 339]|edition=6th |isbn=9780199219858 |year=2008}}</ref>

The sequence {{mvar|a<sub>k</sub>}} generated by a [[Dirichlet series]] generating function (DGF) corresponding to:<math display="block">\operatorname{DG}(a_k;s)=\zeta(s)^m</math>has the ordinary generating function:<math display="block">\sum_{k=1}^{k=n} a_k x^k = x + \binom{m}{1} \sum_{2 \leq a \leq n} x^{a} + \binom{m}{2}\underset{ab \leq n}{\sum_{a = 2}^\infty \sum_{b = 2}^\infty} x^{ab} + \binom{m}{3}\underset{abc \leq n}{\sum_{a = 2}^\infty \sum_{c = 2}^\infty \sum_{b = 2}^\infty} x^{abc} + \binom{m}{4}\underset{abcd \leq n}{\sum_{a = 2}^\infty \sum_{b = 2}^\infty \sum_{c = 2}^\infty \sum_{d = 2}^\infty} x^{abcd} + \cdots</math>

===Polynomial sequence generating functions===

The idea of generating functions can be extended to sequences of other objects. Thus, for example, polynomial sequences of [[binomial type]] are generated by:
<math display="block">e^{xf(t)}=\sum_{n=0}^\infty \frac{p_n(x)}{n!} t^n</math>where {{math|''p''<sub>''n''</sub>(''x'')}} is a sequence of polynomials and {{math|''f''(''t'')}} is a function of a certain form. [[Sheffer sequence]]s are generated in a similar way. See the main article [[generalized Appell polynomials]] for more information.

Examples of [[polynomial sequence]]s generated by more complex generating functions include:

* [[Appell polynomials]]
* [[Chebyshev polynomials]]
* [[Difference polynomials]]
* [[Generalized Appell polynomials]]
* [[Q-difference polynomial|{{mvar|q}}-difference polynomials]]

=== Other generating functions ===
Other sequences generated by more complex generating functions include:

* Double exponential generating functions e.g. the [[Bell numbers#Generating function|Bell numbers]]
* Hadamard products of generating functions and diagonal generating functions, and their corresponding [[generating function transformation#Hadamard products and diagonal generating functions|integral transformations]]

==== Convolution polynomials ====
Knuth's article titled "''Convolution Polynomials''"<ref>{{cite journal |last1=Knuth |first1=D. E. |date=1992 |title=Convolution Polynomials |journal=Mathematica J. |volume=2 |pages=67–78 |arxiv=math/9207221 |bibcode=1992math......7221K}}</ref> defines a generalized class of ''convolution polynomial'' sequences by their special generating functions of the form
<math display="block">F(z)^x = \exp\bigl(x \log F(z)\bigr) = \sum_{n = 0}^\infty f_n(x) z^n,</math>
for some analytic function {{mvar|F}} with a power series expansion such that {{math|''F''(0) {{=}} 1}}.

We say that a family of polynomials, {{math|''f''<sub>0</sub>, ''f''<sub>1</sub>, ''f''<sub>2</sub>, ...}}, forms a ''convolution family'' if {{math|[[Degree of a polynomial|deg]] ''f<sub>n</sub>'' ≤ ''n''}} and if the following convolution condition holds for all {{mvar|x}}, {{mvar|y}} and for all {{math|''n'' ≥ 0}}:
<math display="block">f_n(x+y) = f_n(x) f_0(y) + f_{n-1}(x) f_1(y) + \cdots + f_1(x) f_{n-1}(y) + f_0(x) f_n(y). </math>

We see that for non-identically zero convolution families, this definition is equivalent to requiring that the sequence have an ordinary generating function of the first form given above.

A sequence of convolution polynomials defined in the notation above has the following properties:

* The sequence {{math|''n''! · ''f<sub>n</sub>''(''x'')}} is of [[binomial type]]
* Special values of the sequence include {{math|''f<sub>n</sub>''(1) {{=}} [''z<sup>n</sup>''] ''F''(''z'')}} and {{math|''f<sub>n</sub>''(0) {{=}} ''δ''<sub>''n'',0</sub>}}, and
* For arbitrary (fixed) <math>x, y, t \isin \mathbb{C}</math>, these polynomials satisfy convolution formulas of the form
<math display="block">\begin{align}
f_n(x+y) & = \sum_{k=0}^n f_k(x) f_{n-k}(y) \\
f_n(2x) & = \sum_{k=0}^n f_k(x) f_{n-k}(x) \\
xn f_n(x+y) & = (x+y) \sum_{k=0}^n k f_k(x) f_{n-k}(y) \\
\frac{(x+y) f_n(x+y+tn)}{x+y+tn} & = \sum_{k=0}^n \frac{x f_k(x+tk)}{x+tk} \frac{y f_{n-k}(y+t(n-k))}{y+t(n-k)}.
\end{align}</math>

For a fixed non-zero parameter <math>t \isin \mathbb{C}</math>, we have modified generating functions for these convolution polynomial sequences given by
<math display="block">\frac{z F_n(x+tn)}{(x+tn)} = \left[z^n\right] \mathcal{F}_t(z)^x, </math>
where {{math|𝓕<sub>''t''</sub>(''z'')}} is implicitly defined by a [[functional equation]] of the form {{math|𝓕<sub>''t''</sub>(''z'') {{=}} ''F''(''x''𝓕<sub>''t''</sub>(''z'')<sup>''t''</sup>)}}. Moreover, we can use matrix methods (as in the reference) to prove that given two convolution polynomial sequences, {{math|⟨ ''f<sub>n</sub>''(''x'') ⟩}} and {{math|⟨ ''g<sub>n</sub>''(''x'') ⟩}}, with respective corresponding generating functions, {{math|''F''(''z'')<sup>''x''</sup>}} and {{math|''G''(''z'')<sup>''x''</sup>}}, then for arbitrary {{mvar|t}} we have the identity
<math display="block">\left[z^n\right] \left(G(z) F\left(z G(z)^t\right)\right)^x = \sum_{k=0}^n F_k(x) G_{n-k}(x+tk). </math>

Examples of convolution polynomial sequences include the ''binomial power series'', {{math|𝓑<sub>''t''</sub>(''z'') {{=}} 1 + ''z''𝓑<sub>''t''</sub>(''z'')<sup>''t''</sup>}}, so-termed ''tree polynomials'', the [[Bell numbers]], {{math|''B''(''n'')}}, the [[Laguerre polynomials]], and the [[Stirling polynomial|Stirling convolution polynomials]].