Math 2.0

Combinatorics Definition

Generating function

Builds on Formal power series

Definition

Let RR be a commutative ring and let (an)n≥0(a_n)_{n \ge 0} be a sequence in RR. The ordinary generating function of (an)(a_n) is the formal power series A(x)=∑n≥0anxn∈R[ ⁣[x] ⁣].A(x) = \sum_{n \ge 0} a_n x^n \in R[\![x]\!].

Remarks

Example: the sequence 1,1,1,…1, 1, 1, \dots has the generating function ∑nxn=11−x\sum_n x^n = \frac{1}{1 - x}, the geometric series. Operations on sequences become operations on series. The product of power series corresponds to the convolution cn=∑i+j=naibjc_n = \sum_{i+j=n} a_i b_j. The exponential generating function is a variant with the weights xn/n!x^n / n!.

Reading path

To understand this page from the ground up, read these 2 pages in order. The foundations come first.

Show the path as a graph
Formal power series, definition, no evidence levelFormal power seriesdefinitionGenerating function, definition, no evidence levelGenerating functiondefinition
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Formal power series definition
  2. Generating function definition

Where this leads

5 pages build on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Generating_function, Ordinary generating function (OGF)
About this page
Tag0HH6JX5WZZ
URIm2://0HH6JX5WZZ
Kinddefinition
WritingW1 stated
MSC05A15
DefinesGenerating function
UsesFormal power series

Markdown · JSON · Edit on GitHub

What this page needs for W2

  • edge instance_of in: one example (0 of 1)
  • edge not_instance_of in: one non-example that fails one clause (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Used by