Generating function for Catalan numbers

Loading...

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

Introduction to Enumerative Combinatorics

48 notes

National Research University Higher School of Economics

Introduction to Enumerative Combinatorics

48 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

In this final piece, we'll discuss the application of

the method of generating functions to the combinatorial

problem which we are dealing with in our lecture four.

Namely to getting an expressed formula for Catan numbers.

Let me recall that the Catalan numbers,

Were defined by the following recurrence relation.

C0 was equal to 1, and

Cn was defined by the previous

ones as C0 CN minus 1 plus C1Cn

minus 2 plus C2Cn minus 3

plus etc plus Cn minus 1 C0.

That is sum for i for

1 to n minus 1 of

CiCn-i-1.

So the first several Catalan numbers were.

1, 1, 2, 5,

14, 42, etc.

In the lecture four, we have obtained an explicit formula for Catalan numbers,

using some clever combanitorial trick, the reflection method.

In this passage, we will see how to avoid this

trick from a power series and the expansion for

Newton's binomial for a non-integer alpha.

Okay, let me take the following thing.

Let me first form the generating sequence for Catalan numbers.

Generating functions sorry.

It is as follows Cat(q) is

the sum of Cn q to the power n for

n non negative and it is one

plus q plus two q squared plus

five q to the third plus etc.

Okay, and let's see what happens if we take, well this is an infinite series.

And what happens if we take this series and multiply it by itself,

we'll take it square.

Moreover, we multiply it by q.

So q times Cat of

q squared is C0

squared times

q plus C0 C1 +

C1 C0 q squared

+ (C0 2 + C1C1

+ C2C0) q to

the 3rd + etc.

So you see that these qualifications are exactly the Catalan numbers.

Number 1, 2, 3, and so on.

So, what we'll get will be almost the gyrating function for the Catalan numbers.

Cat of q.

The only difference is that it won't have any constant term.

And in the original function, the constant term was 1.

So this is Cat(q)- 1.

So we get the following equation.

We see that, q

times Cat of q

squared minus

Cat of q plus 1

is equal to 0.

This is a quadratic equation.

With coefficients from the ring from a power series and

the solution of this equation can be also found as a formal power series.

Well, we know the general formula how to solve quadratic equations and

it tells us that the solution is as follows.

This is 1.

That is the minus linear term

of the equation minus the square

root of the discriminant,

which is 1 minus 4q divided by q taken twice

Okay, why do I take the minus sign here and not the plus?

Because This expression in the numerator is a formal power series.

In this case is divisible by q and

I want to divide it by q because I have q in the denominator.

And if I take plus here, what am I going to get will be a power

series with a no zero constant term which will not be divisible by 2q.

So I need only one solution out of this two solutions of my quadratic equation.

And so I have this

expression for the generating function of the Catalan numbers and

what I'm going to do now is I'm going to use the Newton's binomial

theorem to expand this as a formal power series.

I need to compute the expansion for the square root of 1- 4q.

It is 1- 4q to the power of one half.

And this can be computed by Newton's binomial theorem.

So this is the sum for

n > 0 of one-half choose

n times- 4q to the power of n.

Let me write it as follows, negative 1 to the power

of n times 4 to the power of n times q to the power of n.

Let us write down an explicit expression for

the binomial coefficient, one-half choose n.

It is as follows one-half choose n is

1 over n factorial times one-half

times minus one-half then we subtract

1 from 8 from the previous multiple

times minus three-halves, and etc.

And we have n factors of this type.

This means that the last factor will be -2n- 3/2.

And this is negative one to the power

n minus one divided by two to the power

n times n factorial times one times

three times etc times 2n minus 3.

And let me Write

this expression in a slightly different way,

namely let me multiply the numerator and

the denominator by two,

four etc up to to 2n and by 2n-1.

The last odd factor which is missing here.

So this is -1 to the power

n divided by two 2 to the power

n times n factorial,

times 1 over 2,

4 etc 2n minus 2 times

2n times 1 over 2n minus

1 times 2n factorial.

And what is this expression?

It is exactly 2 to the power n times n factorial.

So we have, of course here it's n minus 1 not n.

Minus 1 to the power n minus 1,

4 to the power n times n factorial squared.

Times 2n-1 multiplied

by 2n factorial.

And this is, (-1)

to the power n- 1 times 4 to the power

n times (2n- 1) times (2 n choose n).

And this is the expression which, well something very similar

appeared in the explicit formula for Catalan numbers.

And of course this is not a coincidence, so having this,

we see that this 4 of n and this 4 walks to the power n and

this 4 walks to the power n vanishes the minus sign also vanishes.

So the square root of

one minus 4q is minus

the sum of 1 over 2n-

1, Times,

2n choose n times q to the power of n for

n greater than or equal to 1.

And this is almost what we need.

To get the generating function for Catalan numbers,

we need to subtract this expression from 1 and divide it by 2q.

And in this way, we'll get our final answer,

Cn, the nth catalog number, will be equal to one-half,

coming from the denominator here times the coefficient

in front of q to the power n+1 in this expression.

So it will be 1 over

2n plus 1 times 2n

plus 2 choose n+1

And this is, well it is easy to understand

that this thing will be indeed equal to

1 over n plus 1 multiplied by 2n choose n,

or to write it in a slightly different way,

this is 2n factorial divided by n

factorial times n plus 1 factorial.

And this is our explicit formula for Catalan numbers,

and we recover it once again from the method of generating functions and

in this proof we did not use the combinatorial reflection trick.

So the generating functions and formal power series give us a very

powerful method of solving various combinatorial problems.

Thank you.

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