Explicit formula for q-binomial coefficients

Loading...

Del curso dictado por National Research University Higher School of Economics

Introduction to Enumerative Combinatorics

51 calificaciones

National Research University Higher School of Economics

Introduction to Enumerative Combinatorics

51 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

[MUSIC]

So, we have seen the inductive rule for coefficients.

But what about the explicit formula?

Well, for usual binomial coefficients,

the formula is well known,

(m + n, m ) = ( m + n )!

Divided by m!

Times n!

It turns out that literally the same analogue over

this formula holds for q binomial coefficients but

to state it we first need to state the right

notion of integer numbers and factorials.

Namely what are acute analogues of integers and

what is the q analog of n factorial?

So, q-integer numbers.

So what is an integer number?

Well, we'll denote it by n in squared brackets and

we define it as a strange way,

so n is the number of one element

subsets of an N elements set.

So this is, n choose one

and this is my definition.

And this is one plus q plus q squared plus etc,

and we sum up until q to the power n minus one.

Note that here, we sum up until n minus one, not until q to the power n.

So this is the generating functions for

young diagrams inside the rectangle of size 1 times n- 1.

Okay, and this can be

written down as fraction,

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

So this will be called the q integer number by definition.

So.

So our general rule for evaluating things at q equal to 1, halt.

So if we find a value of this binomial in q equal to 1,

this will be exactly n in the usual sense.

So, n evaluated at q equals to 1, is just n.

Okay.

How to sum up integers.

So if we add

n in square brackets to m in square brackets.

This, of course this won't be equal to m + n in squared brackets.

Well, these two polynomials are different.

They have different degrees and so on.

But fortunately, an analog of this formula holds.

So if we, Multiply one

of these numbers by q to the power of the first number.

So if we multiply this n is squared

brackets by q to the power of n or

alternatively if we take n and

add it with q to the power of n times m,

what we get is exactly the QL of m plus n.

We will need this formula and the following part.

Okay.

So what about factorials?

We define factorials in obvious way so

if n factorial is 1 times 2 times etc times N,

then what is the analog of, factorial of Q not Q integer N.

So this will be by definition, Q analog of 1 times.

Q analof of 2 times etc times N in squared brackets.

And also by definition

We define zero factorial to be equal to one.

Okay, so now comes our proposition, the analog of this quality.

M + N, choose m.

Equals m + n factorial.

Divided by m factorial.

[BLANK AUDIO] Times n factorial.

So we need to replace all the integers and this formula by their q analogues.

The usual binomial efficient by its q-analogue and the same formula will.

So if you eliminated as Q equal to one you will get exactly the same equality.

Okay, let's prove it.

We are proving by induction or m + n

If m + n = 1.

Then our quantity is obvious.

So here's the induction step.

Suppose our equality holds for m + n- 1

Now the left hand side

of the equality which is

m+n choose m is equal

to m+n-1 choose m-1 + q

to the power of m times

m+n-1 choose m.

And, My induction hypothesis,

this is equal to m plus n minus one factorial,

over m minus one factorial times n factorial.

We are dealing with q-analogs here.

Plus q to the m, m+n-1

factorial over m factorial

times n-1 factorial.

So, of these two fraction have common multiple.

[m + n- 1] factorial over [m- 1]

factorial times [n- 1] factorial.

And it is multiplied by 1 over n in

squared brackets plus q to the power

m divided by m in squared brackets.

And this is equal to.

M + n- 1 factorial,

over m- 1 factorial times

n- 1 factorial, times the sum,

Which is equal to [m] + q to the power m,

Times n, Divided by the common denominator.

M times n.

And using this observation.

We see that the numerator here is nothing but m plus n.

Which gives us the desired equality.

That this is equal to m+n

factorial over m factorail

times n factorial.

The proposition's proved.

[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