Generating functions: first examples

Loading...

From the course by National Research University Higher School of Economics

Introduction to Enumerative Combinatorics

51 ratings

National Research University Higher School of Economics

Introduction to Enumerative Combinatorics

51 ratings

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.

From the lesson

Generating functions: a unified approach to combinatorial problems. Solving linear recurrences

We introduce the central notion of our course, the notion of a generating function. We start with studying properties of formal power series and then apply the machinery of generating functions to solving linear recurrence relations.

Generating functions: first examples10:40

Formal power series11:54

When are formal power series invertible?9:38

Derivation of formal power series12:31

Binomial theorem for negative integer exponents8:50

Solving the Fibonacci recurrence relation9:29

Solving the Fibonacci recurrence 2: Binet formula6:40

Generating functions of linear recurrence relations are rational7:39

Solving linear recurrence relations: general case10:01

Meet the Instructors

Evgeny Smirnov
Associate Professor
Faculty of Mathematics

[MUSIC]

Hi, and welcome back to Introduction to Enumerative Combinatorics.

We started the second half of our course,

this is lecture five of our eight lecture series.

And it is entitled Generating Functions.

In this lecture we'll define the notion of generating functions.

It is a very convenient way to look at sequences of numbers.

So in our previous lectures we were dealing with sequences of various numbers

that had some combinatorial nature.

They were counting elements in various sets and so on.

And while generating functions allow us to look at such sequences as a whole.

So here's the definition.

Let.

A0, a1, a2, etc.,

be a sequence of numbers.

Well let's say that a IR, just real numbers,

we don't require them to be integers or whatever.

And so this sequence is indexed by non-negative integers, 0, 1, 2, etc.

So the generating function of this sequence

Is the following formal power series.

We denote it by A(q) where

q is a formal variable.

And this is a0 + a1q

+ a2q squared +...

+ anqn +...

So while this sequence can be infinite, so

this expression is not a polynomial, it is a formal power series.

We'll speak about formal power series in a minute.

And we can use a shorthand notation,

A(q) is the sum of anqn, for

n greater than or equal to 0.

Okay, so

let us first consider some easy examples.

Let us start with a not very interesting sequence,

which consists of equal numbers of just ones.

Examples, Example 1.

Suppose that a0, a1, etc.,

is just the sequence of 1s.

In this case the generating function of this formal power series.

A(q) is, well let's look at this definition.

We need to write down 1+q times 1,

this is q + q squared +...

+ qn.

And then up to infinity.

So this is just the geometric progression with a common ratio q starting with 1.

And we know how to compute the sum of this progression.

This is 1 / 1-q.

Well, a little bit later we will explain how

to understand this equality formally.

What does this expression mean?

Okay, here's another example, a variation of this one.

Example 2, what if we start not with a sequence of 1s, but

just with a geometric progression?

So, a0, a1, etc., is a geometric

progression with the common ratio,

let's say lambda, lambda,

lambda squared, lambda cubed.

In this case, our A(q) will be a geometric progression again,

but the common ratio will be equal to lambda times q.

So this will be 1 + lambda q + lambda squared

times q squared + and so on and so on.

And this will be just 1/ 1- lambda, here.

So, This expression keeps track of this sequence.

So the sequence a0, a1, etc.,

is just a sequence of coefficients of this expression.

Or, if you wish, you can take the series expansion of this guy here.

And its coefficients are equal to a0, a1, and a2 and etc.

Okay, here's our third example which is somewhat more interesting.

Sometimes we're dealing with infinite sequences or

sometimes we're dealing with finite ones.

So as an example, let's take the mth row of the Pascal Triangle.

Let (a0, a1,

a2,...am) be

mth row of the Pascal triangle.

This means that,

an is just m choose n.

Or you can suppose that this sequence is infinite, so

We can think than an = 0 for

n greater than m.

So, this definition makes sense.

Because the number of ways of picking an n element

subset of an m element set is equal to 0.

If n is greater than m.

So, this makes perfect sense.

Okay, and in this case, the generating function will be as follows.

A(q) for this sequence is,

m choose 0 + m choose 1

times q +...+ m choose

m times q to the power m.

And note that this will be polynomial.

There will be no terms with powers of q greater than m.

So there will be just m plus 1 terms in this expression.

And you know very well that this is, in fact,

the following expression.

This is (1 + q) to the power m.

So this is Newton's binomial theorem.

So, Newton's binomial theorem tells us that the generating function for

the mth row of the Pascal triangle is nothing but (1 + q) to the power m.

[MUSIC]

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play