Euler’s partition function

Loading...

Del curso dictado por National Research University Higher School of Economics

Introduction to Enumerative Combinatorics

55 calificaciones

National Research University Higher School of Economics

Introduction to Enumerative Combinatorics

55 calificaciones

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.

De la lección

Gaussian binomial coefficients. “Quantum” versions of combinatorial identities

Our final lecture is devoted to the so-called "q-analogues" of various combinatorial notions and identities. As a general principle, we replace identities with numbers by identities with polynomials in a certain variable, usually denoted by q, that return the original statement as q tends to 1. This approach turns out to be extremely useful in various branches of mathematics, from number theory to representation theory.

Generating function for partitions inside a rectangle12:57

q-binomial coefficients: definition and first properties10:01

Recurrence relation for q-binomial coefficients 114:02

Recurrence relation for q-binomial coefficients 23:40

Explicit formula for q-binomial coefficients11:14

Euler’s partition function8:39

Sidebar: q-binomial coefficients in linear algebra9:14

q-binomial theorem10:37

Conoce a los instructores

Evgeny Smirnov
Associate Professor
Faculty of Mathematics

[SOUND] Sometimes it's more

convenient to use another form

of the previous equality.

Namely, proposition,

the key binomial coefficient

m plus n chose n is equal to

the the following fraction 1

minus q to the power of m plus 1.

Times (1-q^m+2)

times et cetera,

until (1-q^m+n)

So this expression consists of n

factors / (1- q) times (1- q

squared) times (1- q to the power n.

So, the number of factors in the denominator is the same, which is n.

Indeed, let us prove this.

As we know M+n

choose n is equal to [m+n]!

Divided by, [m] and

times n factorial.

So, we can divide the numerator and denominator by n factorial and

get n factorial in the denominator.

And m plus one times m plus two times ect,

times m plus n in the numerator.

So, here we are.

M+1 times m + 2

times ect times m + n.

So, we know an explicit formula for each of these q integers.

It is- 1- q to the power

M + 1 divided by 1- q x 1- q

to the power m+2 divided by

1-q x etc x 1- q to the power

of m plus n divided by 1- q and

this is the numerator and

the denominator is 1- q

divided by 1- q times 1- q

squared divided by 1- q etc.

1- q to the power n divided by 1- q.

And the number of multiples is

the same in the enumerator and

the denominator, so we get that this

is equal to 1- q to the power m + 1,

etc, times 1- q to the power m

+ n divided by 1- q times etc,

times 1- q to the power n.

The proposition is proved,

so what happens if now m turns to infinity.

Suppose that m is very large, let's say 1 million.

That means that- This expression in the numerator is almost 1.

The first term, well let's say the first million

terms of this expression will be zeroes.

And this means that the limit of the numerator

will be one as m tends to infinity.

And the limit of the, and

the denominator does not depend upon m,

so the limit of this expression,

m + n choose n as m goes to

infinity is equal to 1 over

1- q times 1- q squared,

times etc times 1- q to the power n and

this is exactly the expression for

which we have seen in our previous lecture,

this is the gen reading function

which is called Pn(q).

[INAUDIBLE] Partitions such that the length of each row does not exceed n.

So this is the generating function for

partitions with parts not exceeding n.

So, in a sense these are, Young diagrams,

Of fixed width but, Of arbitrary height.

So, they are located inside

a rectangle of size n times infinity.

We have obtained another proof of this equality.

And what happens if both m and n tend to infinity?

Then, the limit,

Of the expression for the q binomial coefficient m + n choose n.

Well of course it's not a polynomial anymore, it's a series.

This is our familiar

FN product 1 over

1- q to the power of k rrom one to infinity.

And this is exactly others

generating function or partitions.

[SOUND]

[MUSIC]

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2018 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play