imported>Practice M. Perfect: /* growthexperiments-addlink-summary-summary:3|0|0 */

2025-10-23T22:37:40Z

growthexperiments-addlink-summary-summary:3|0|0

imported>Bumpf: /* Other generating functions */fixed strange OEIS search link (at least make it directly to the entry instead of a search of the first few values!) to the wiki article.

2025-05-03T22:42:43Z

Other generating functions: fixed strange OEIS search link (at least make it directly to the entry instead of a search of the first few values!) to the wiki article.

Show changes

← Previous revision		Revision as of 22:37, 23 October 2025
Line 1:		Line 1:
	{{Short description\|Formal power series~~; coefficients encode information about a sequence indexed by natural numbers~~}}		{{Short description\|Formal power series}}
	{{About\|generating functions in mathematics\|generating functions in classical mechanics\|Generating function (physics)\|generators in computer programming\|Generator (computer programming)\|the moment generating function in statistics\|Moment generating function}}		{{About\|generating functions in mathematics\|generating functions in classical mechanics\|Generating function (physics)\|generators in computer programming\|Generator (computer programming)\|the moment generating function in statistics\|Moment generating function}}

Line 105:		Line 105:
	Other sequences generated by more complex generating functions include:		Other sequences generated by more complex generating functions include:

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

Line 196:		Line 196:
	{{Main\|Linear recursive sequence}}		{{Main\|Linear recursive sequence}}

	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.		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 <ref name="GFLECT">{{harvnb\|Lando\|2003\|loc=§2.4}}</ref>		We also notice that the class of rational generating functions precisely corresponds to the generating functions that enumerate ''quasi-polynomial'' sequences of the form <ref name="GFLECT">{{harvnb\|Lando\|2003\|loc=§2.4}}</ref>
Line 273:		Line 273:
	<math display="block">c_0(z) F^{(r)}(z) + c_1(z) F^{(r-1)}(z) + \cdots + c_r(z) F(z) = 0, </math>		<math display="block">c_0(z) F^{(r)}(z) + c_1(z) F^{(r-1)}(z) + \cdots + c_r(z) F(z) = 0, </math>

	where the coefficients {{math\|''c<sub>i</sub>''(''z'')}} are in the field of rational functions, <math>\mathbb{C}(z)</math>. Equivalently, <math>F(z)</math> is holonomic if the vector space over <math>\mathbb{C}(z)</math> spanned by the set of all of its derivatives is finite dimensional.		where the coefficients {{math\|''c<sub>i</sub>''(''z'')}} are in the field of rational functions, <math>\mathbb{C}(z)</math>. Equivalently, <math>F(z)</math> is holonomic if the [[vector space]] over <math>\mathbb{C}(z)</math> 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, {{math\|''c<sub>i</sub>''(''z'')}} are polynomials in {{mvar\|z}}. Thus we can see an equivalent condition that a generating function is holonomic if its coefficients satisfy a '''{{mvar\|P}}-recurrence''' of the form		Since we can clear denominators if need be in the previous equation, we may assume that the functions, {{math\|''c<sub>i</sub>''(''z'')}} are polynomials in {{mvar\|z}}. Thus we can see an equivalent condition that a generating function is holonomic if its coefficients satisfy a '''{{mvar\|P}}-recurrence''' of the form
Line 303:		Line 303:
	When the series [[Absolute convergence\|converges absolutely]],		When the series [[Absolute convergence\|converges absolutely]],
	<math display="block">G \left ( a_n; e^{-i \omega} \right) = \sum_{n=0}^\infty a_n e^{-i \omega n}</math>		<math display="block">G \left ( a_n; e^{-i \omega} \right) = \sum_{n=0}^\infty a_n e^{-i \omega n}</math>
	is the discrete-time Fourier transform of the sequence {{math\|''a''<sub>0</sub>, ''a''<sub>1</sub>, ...}}.		is the [[discrete-time Fourier transform]] of the sequence {{math\|''a''<sub>0</sub>, ''a''<sub>1</sub>, ...}}.

	=== Asymptotic growth of a sequence ===		=== Asymptotic growth of a sequence ===
Line 550:		Line 550:
	====Example: The money-changing problem====		====Example: The money-changing problem====

	The number of ways to pay {{math\|''n'' ≥ 0}} cents in coin denominations of values in the set {1,~~ ~~5,~~ ~~10,~~ ~~25,~~ ~~50} (i.e., in pennies, nickels, dimes, quarters, and half dollars~~, respectively~~), where we distinguish instances based upon the total number of each coin but not upon the order in which the coins are presented, is given by the ordinary generating function		The number of ways to pay {{math\|''n'' ≥ 0}} cents in coin denominations of values in the set {{math\|{{mset\|1, 5, 10, 25, 50}}}} (i.e., in pennies, nickels, dimes, quarters, and half dollars), where we distinguish instances based upon the total number of each coin but not upon the order in which the coins are presented, is given by the ordinary generating function
	<math display="block">\frac{1}{1-z} \frac{1}{1-z^5} \frac{1}{1-z^{10}} \frac{1}{1-z^{25}} \frac{1}{1-z^{50}}\,.</math>		<math display="block">\frac{1}{1-z} \frac{1}{1-z^5} \frac{1}{1-z^{10}} \frac{1}{1-z^{25}} \frac{1}{1-z^{50}}\,.</math>
	When we also distinguish based upon the order in which the coins are presented (e.g., one penny then one nickel is distinct from one nickel then one penny), the ordinary generating function is		When we also distinguish based upon the order in which the coins are presented (e.g., one penny then one nickel is distinct from one nickel then one penny), the ordinary generating function is
Line 606:		Line 606:
	<math display="block"> [z^n]T(z) = [z^{n-1}] \frac{1}{n} (1+z^2)^n </math>		<math display="block"> [z^n]T(z) = [z^{n-1}] \frac{1}{n} (1+z^2)^n </math>

	Via the binomial theorem expansion, for even <math mode="inline">n</math>, the formula returns <math mode="inline">0</math>. This is expected as one can prove that the number of leaves of a binary tree are one more than the number of its internal nodes, so the total sum should always be an odd number. For odd <math mode="inline">n</math>, however, we get		Via the [[binomial theorem]] expansion, for even <math mode="inline">n</math>, the formula returns <math mode="inline">0</math>. This is expected as one can prove that the number of leaves of a [[binary tree]] are one more than the number of its internal nodes, so the total sum should always be an odd number. For odd <math mode="inline">n</math>, however, we get

	<math mode="block">[z^{n-1}] \frac{1}{n} (1+z^2)^n = \frac{1}{n} \dbinom{n}{\frac{n+1}{2}} </math>		<math mode="block">[z^{n-1}] \frac{1}{n} (1+z^2)^n = \frac{1}{n} \dbinom{n}{\frac{n+1}{2}} </math>

Generating function - Revision history

imported>Practice M. Perfect: /* growthexperiments-addlink-summary-summary:3|0|0 */

imported>Bumpf: /* Other generating functions */fixed strange OEIS search link (at least make it directly to the entry instead of a search of the first few values!) to the wiki article.