Sidebar: q-binomial coefficients in linear algebra

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

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

Meet the Instructors

Evgeny Smirnov
Associate Professor
Faculty of Mathematics

[MUSIC]

Okay, this is side bar.

Let me tell you about another appearance of q-binomial coefficients in linear

algebra over finite fields.

So, if you don't know what a finite field is you can just skip this piece.

Suppose that q is a power of prime.

Q is p to the power,

let's say, capital N.

And then, we can consider a finite field with q elements.

This field will be denoted by Fq.

>> Okay, consider a vector space over Fq of dimension m+n.

V is isomorphic to Fq to the power m+n.

We can consider n-dimensional subspaces inside V.

Okay, Fq is a finite field so there are finite elements such as subspaces.

We can ask ourselves how many of them are there?

So, the answer is that this number is exactly

the q-binomial coefficient, m+n, choose n.

Theorem, The # { subspaces,

Inside Fq to the power m+n of

dimension =n} =

Q-binomial coefficient [m+n, choose n].

Let's prove this.

Okay, Let us pick a basis inside U, let,

In how many ways can we do that?

In how many ways can we pick n linearly independent vectors inside of V?

So to pick u1, we have

Q to the power m+n -1 possibilities.

Then, u2 well, -1 here is because the first

base is vector should be non-zero but

a part of the zero vector it can be an arbitrary vector of V.

Okay, then to pick u2, we have q to

the power m+n- q possibilities.

Because we want our vector u2 be linearly independent from u1 and

so it should be not contained in the line span by u1.

And the line span by u1 contains exactly q vector.

So, u2 should not be

contained in the span of u1.

And this line has cardinality q.

So for u3,

There are q to the power m+n- q squared possibilities.

Because u3, Should

not be contained inside the planes and by u1 and u2.

And this plane consists of q squared points.

For the last vector, un,

the number of possibilities to pick

it is q to the power m+n- q to the power n-1.

Because the condition is that,

it should not be contained in the subspace panned

by the previous vectors, u1 et cetera un-1.

So, the total number of tuples of n linearly independent vectors is equal to

(q to power of m+n-

1).(q to the power

m+n- q).et cetera.(q

to the power m+n- q to

the power n-1).

And this is the number of tuples.

(u1 et cetera un) which are linearly independent.

Each tuple, spans and n-dimensional space U.

But given subspace U, Correspond several tuples.

Let us compute their number.

So, for a given,

U says tuple will be basis of U, so then, number of bases,

Can be found in a similar way.

It is, (q to the power

n- 1).(q to the power n- q).et

cetera.(q to the power n- q to the power n-1).

So, the number of subspaces equals the ratio of this amount,

the number of tuples, divided by the number of tuples defining each given U.

So, #{U inside Fq to

the power of m+n of dimU=n}

= (q to the power m+n-

1).et cetera.(q to

the power m+n- q to the power

n-1)/q to the power n-

1)et cetera(q to the power

n- q to the power n-1).

And it is obvious that this thing equals

The q-binomial coefficient, [m+n choose n].

[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