Derivation and integration of formal power series

Loading...

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

Introduction to Enumerative Combinatorics

51 notes

National Research University Higher School of Economics

Introduction to Enumerative Combinatorics

51 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]

Our next topic is derivation and integration of formal power series.

In our previous lecture we already discussed taking the derivative

of a formal power series A(q) Which

was a naught + a1q + a2q squared + etc.

Its derivative was defined

as a1 + 2a2q + 3

It should be 2,

3a3q squared + etc.+

nanq to the power n- 1 + etc.

Okay, and we know that taking the derivative is linear,

The sum of the derivative is the derivative of the sum.

And that, well, it was left as an exercise.

But it is really easy, that,

The derivative of the product can be computed by the Leibniz rule.

So AB prime is

A prime times B +

A times B prime.

Okay, and, Having this definition,

we already can solve some very simple differential equations.

For instance, question.

Find all such power series which satisfy the differential equation.

Find all formal power series F(q),

satisfying the equation

F prime =

F The solution is pretty simple.

Just compute the coefficients of this formal power series one by one.

If F is f naught +

f1q + f2q2+ etc.,

then F prime is

f1 + 2f2q +

3f3 q2+ etc.

And these two power series must be equal.

So, So

fn = (n

+1)fn+1.

For all n greater than or

equal to 0.

And in this case, you can find them one by one.

And so you see that

fn is nothing but

f0 divided by n

factorial.

So if f0 = c, then our

F(q) has the form c(1

+1 over 1 factorial

q +1 over 2 factorial

q2 + etc.+ 1 over

n factorial qn + etc.).

And in this series you probably recover the power series for the exponent.

So exp(q) is 1 + 1

over 1 factorial q +

1 over 2q2+ 1 over

3 factorial q3 +etc.

Then, F(q) is nothing but

a multiple of the exponent.

I'm sorry, there should be,

of course this should be squared over here, not q to the third.

Okay, so we have the power series for the exponent.

And we'll use it further.

Okay, but before we do that, let

us define the operation, which is inverse to taking the derivative.

This is integration of formal power series.

So, Integration

can also be defined formally by the same formulas as you have with polynomials.

So the integral of A(q) is defined as

a naught q +

a1 over 2q2

+ a2 over 3

q3 + etc.+

an over n+1

q n+1 +etc.

Okay, and, You see

that what happens if you start with some formal power series,

then to compute its derivative, And then take its integral.

Well, the first guess would be to say that you get what

you started with, named A(q), but this is not completely true.

Because you see that the integral

of formal power series has no constant term by definition.

So there's is no constant term here.

This series starts with a naught q.

So what you get by taking the integral is,

The series A(q) without its constant term.

So it is a1q +a2q2+ A3q3 + etc.

And it is, A(q)-

its constant term.

Or to put it in a different way,

A(q)- A(0).

And this, if you wish, this can be created as the Newton-Leibniz formula.

Newton-Leibniz formula is familiar to you from mathematical analysis.

Further, we'll prove the chain rule,

which tells us how to differentiate the composition of two functions.

You already know the analog of the chain rule from mathematical analysis.

And we will see that for formal power series, things are pretty much the same.

[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