Generating function of a sequence (gentris)

Lecture



Generating function (or generator ) sequence Generating function of a sequence (gentris) - this is a formal power series

Generating function of a sequence (gentris) .

Often, the generating function of a sequence of numbers is the Taylor series of some analytic function, which can be used to study the properties of the sequence itself. However, in the general case, the generating function does not have to be analytic. For example, both rows

Generating function of a sequence (gentris) and Generating function of a sequence (gentris)

have a radius of convergence of zero, that is, diverge at all points except zero, and at zero both are equal to 1, that is, as functions, they coincide; nevertheless, they differ as formal ranks.

The generating functions make it possible to simply describe many complex sequences in combinatorics, and sometimes help to find explicit formulas for them.

The method of generating functions was developed by Euler in the 1750s.

Content

  • 1 Properties
  • 2 Examples of use
    • 2.1 In combinatorics
    • 2.2 In probability theory
  • 3 Variations and generalizations
    • 3.1 Exponential generating function
  • 4 Literature
  • 5 References

Properties [edit]

  • The generating function of the sum (or difference) of two sequences is equal to the sum (or difference) of the corresponding generating functions.
  • The product of generating functions Generating function of a sequence (gentris) and Generating function of a sequence (gentris) sequences Generating function of a sequence (gentris) and Generating function of a sequence (gentris) is a convolution generating function Generating function of a sequence (gentris) these sequences:

Generating function of a sequence (gentris)

Examples of use [edit]

In combinatorics [edit]

Let be Generating function of a sequence (gentris) Is the number of compositions of a non-negative integer n of length m , that is, representations of n in the form Generating function of a sequence (gentris) where Generating function of a sequence (gentris) - non-negative integers. Number Generating function of a sequence (gentris) It is also the number of combinations with repetitions of m through n , that is, the number of samples n possibly repeating elements from the set Generating function of a sequence (gentris) (with each member Generating function of a sequence (gentris) in the composition can be interpreted as the number of elements i in the sample).

For a fixed m generating function of the sequence Generating function of a sequence (gentris) is an:

Generating function of a sequence (gentris)

Therefore number Generating function of a sequence (gentris) can be found as a coefficient for Generating function of a sequence (gentris) in decomposition Generating function of a sequence (gentris) by powers of x . To do this, you can use the definition of the binomial coefficients, or directly take the derivative n times at zero:

Generating function of a sequence (gentris)

In probability theory [edit]

  • If a Generating function of a sequence (gentris) - positive integer random variable (special case discrete), having a probability distribution

Generating function of a sequence (gentris)

then its expectation can be expressed in terms of the generating function of the sequence Generating function of a sequence (gentris)

Generating function of a sequence (gentris)

as the value of the first derivative in the unit: Generating function of a sequence (gentris) (It is worth noting that the series for P (s) converges, at least when Generating function of a sequence (gentris) ). Really,

Generating function of a sequence (gentris)

When substitution Generating function of a sequence (gentris) get the value Generating function of a sequence (gentris) , which by definition is the expectation of a discrete random variable. If this series diverges, then Generating function of a sequence (gentris) -- but Generating function of a sequence (gentris) has infinite mathematical expectation Generating function of a sequence (gentris)

  • Now take the generating function Generating function of a sequence (gentris) sequences of tails of distribution Generating function of a sequence (gentris)

Generating function of a sequence (gentris)

This generating function is associated with a previously defined function. Generating function of a sequence (gentris) property: Generating function of a sequence (gentris) at Generating function of a sequence (gentris) . From this, by the mean-theorem, it follows that the expectation is equal to just the value of this function in the unit:

Generating function of a sequence (gentris)

  • Differentiating Generating function of a sequence (gentris) and using the ratio Generating function of a sequence (gentris) , we get:

Generating function of a sequence (gentris)

To get the variance Generating function of a sequence (gentris) , this expression must be added Generating function of a sequence (gentris) , which leads to the following formulas for calculating the variance:

Generating function of a sequence (gentris) .

In case of infinite dispersion Generating function of a sequence (gentris) .

Variations and generalizations [edit]

Exponential generating function [edit]

Exponential generating function of a sequence Generating function of a sequence (gentris) - this is a formal power series

  • Generating function of a sequence (gentris) .

    • If a Generating function of a sequence (gentris) and Generating function of a sequence (gentris) - exponential generating functions of sequences Generating function of a sequence (gentris) and Generating function of a sequence (gentris) then their work Generating function of a sequence (gentris) is an exponential generating function of a sequence Generating function of a sequence (gentris) .

Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Probability theory. Mathematical Statistics and Stochastic Analysis

Terms: Probability theory. Mathematical Statistics and Stochastic Analysis