Explore
For Enterprise
Join for Free
Log In

Parcourir
Rechercher
For Enterprise
Connexion
Inscrivez-vous gratuitement

Composition of formal power series

Loading...

Introduction to Enumerative Combinatorics

Université nationale de recherche, École des hautes études en sciences économiques

4.6 (70 évaluations) | 6.7K étudiants inscrits

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. Do you have technical problems? Write to us: coursera@hse.ru

Visualiser le programme de cours

Avis

4.6 (70 évaluations)

5 stars
54 ratings
4 stars
10 ratings
3 stars
3 ratings
1 star
3 ratings

DP

Apr 21, 2017

Very good gourse, I persoally enjoyed the lectures in which the relatipnship with other areas of mathematics were discussed.

CX

Feb 12, 2018

by far the best math course I had (and I've taken many) on coursera

À 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

Enseigné par

Evgeny Smirnov
Associate Professor

Transcription

[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 provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

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

Disponible sur Google Play

Coursera
À propos
Direction
Carrières
Catalogue
Certificats
Certificats MasterTrack™
Diplômes
For Enterprise
For Government
Pour le campus

Communauté
Learners
Partners
Developers
Beta Testers
Translators

Se connecter
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Blog Tech

Plus
Conditions
Confidentialité
Aide
Accessibilité
Presse
Contact
Répertoire
Filiales