Composition of formal power series

Loading...

En provenance du cours de National Research University Higher School of Economics

Introduction to Enumerative Combinatorics

47 notes

National Research University Higher School of Economics

Introduction to Enumerative Combinatorics

47 notes

Enumerative combinatorics deals with finite sets and their cardinalities. In other words, a typical problem of enumerative combinatorics is to find the number of ways a certain pattern can be formed. In the first part of our course we will be dealing with elementary combinatorial objects and notions: permutations, combinations, compositions, Fibonacci and Catalan numbers etc. In the second part of the course we introduce the notion of generating functions and use it to study recurrence relations and partition numbers. The course is mostly self-contained. However, some acquaintance with basic linear algebra and analysis (including Taylor series expansion) may be very helpful.

À partir de la leçon

Generating functions, continued. Generating function of the Catalan sequence

In this lecture we discuss further properties of formal power series. In particular, we prove an analogue of the binomial theorem for an arbitrary rational exponent. We apply this technique to computing the generating function of the sequence of Catalan numbers.

Composition of formal power series9:14

Derivation and integration of formal power series10:29

Chain rule. Inverse function theorem7:24

Logarithm. Logarithmic derivative5:48

Binomial theorem for arbitrary exponents13:19

Generating function for Catalan numbers14:30

Rencontrer les enseignants

Evgeny Smirnov
Associate Professor
Faculty of Mathematics

[MUSIC]

Hi and welcome back to Introduction to Enumerative Combinatorics.

This is lecture six and it is entitled more on formal power series and

nonlinear recurrence relations.

In our previous lecture, we discussed linear recurrence relations and

sequences defined by these relations.

And we found that their generating functions are rational,

so they're ratios of two polynomials.

In this lecture, we will look at a sequence defined by

a nonlinear recurrence relation, namely by catalan numbers.

And we'll write down the corresponding generating function.

But to do this, we'll need more preliminaries on formal power series.

So we have introduced the formal power series as,

Formal linear combinations of the following form,

a0 + a1q + a2q squared + a3q to the third + etc.,

where as are coefficients, say real numbers.

And q is just a symbol, a formal variable, and

you're dealing with such expressions just as you're dealing with polynomials.

So you can multiply them, you can add them, and

you also can take the inverse two

formal power series provided that its constant term is non-zero.

This we have discussed in our previous lecture.

What else can we do with the formal power series?

For instance, if we have two formal part series,

we can try to take their composition.

So suppose we have another series

B(q) = b0 + b1q + b2q squared + etc.

And you can try to substitute B(q) instead of the variable q in A.

So you take A(B(q)).

So this is just, a0

+ a1B(q)+a2(B(q))

squared + etc.

So this is sum, Of the form.

An B(q) To

the power n, for n greater than or equal to 0.

My question is, when does this expression make sense?

What do I mean by making sense?

I mean, is it possible to compute each coefficient

of this series using only finitely many

operations with the coefficients an and bn?

The answer is that this sometimes is not

meaningful if the constant

term B(q) is not 0.

Let us look at the constant term of this composition.

So, Where do we get constants from?

So you see that here we have a0.

Then from this, the constant term of this sum is a1 times B0.

The constant term of this sum is a2 times B0 squared, etc.

So the constant term,

Of A,

Of (B(q)) is, what we expect

to get is a0 + a1b0 + a2b0

squared + etc., up to infinity.

This means that we cannot compute it using the quantitative

number of operations and this sum may be divergent.

It is not computed using only

finitely many summations and

multiplication.

It is always computed by finding the many operations only in the case

when b naught is equal to 0.

So, unless B naught is 0.

So if b naught is not equal to 0, this may be not meaningful.

And if b naught is equal to 0, well, this is an easy exercise for

you to understand that to compute each term of this sum,

you need only finitely many operations.

So A(B(q)), Is meaningful,

Only if,

The formal power series B has, No constant term.

Okay, here's an example.

So notice that A(q) is the geometric

progression with the common ratio q.

Which is 1/1-q.

And B(q) is just q squared.

In this case, A(B(q)) = 1

+ q squared, instead of each q,

we substitute q squared,

+ q to the fourth + q to the sixth, etc.

And this is the geometric progression with a common ratio q squared.

We'll need this operation of composition of two power series further,

but before we make some use of it, let us define formal derivation and

integration on formal power series.

[MUSIC]

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2018 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play