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.
Introduction
Loading...
來自 National Research University Higher School of Economics 的課程
Introduction to Enumerative Combinatorics
62 個評分
Explore Related Videos
At Coursera, you will find the best lectures in the world. Here are some of our personalized recommendations for you
National Research University Higher School of Economics
62 個評分
與講師見面
Evgeny SmirnovAssociate Professor
Faculty of Mathematics
[SOUND] Hello, and welcome to our course
which is entitled Introduction
to Enumerative Combinatorics.
My name is and
I'm an Associate Professor of the National Research University Higher School of
Economics Department of Mathematics in Moscow, Russia.
The very first thing that you learn about mathematics when you're a kid is that
math is about counting things.
That mathematicians are counting something.
Well, I think that maybe they're
doing computations with very long numbers all day long.
Well, that's what you think about math and
about mathematicians when you were a child.
But later, you understand, as you study more and more mathematics,
that this is not completely true.
That much of mathematics is about proving something.
Much of math is about constructing new theories and finding out
properties of certain mathematical objects, and so on, and so on.
But there is one branch of mathematics, namely combinatorics, for
which is it essentially true that combinatorics is
about describing cardinalities of finances,
and well, so it is about counting certain objects,
having certain given properties.
So a typical question in combinatorics starts with the words,
in how many ways can we do something.
Well, let me give a couple of examples of typical commentorial questions.
So first of them is, in how many ways can we pick six numbers.
Six different numbers out of let's say the first 50?
Can we pick sic
distinct numbers.
In the range.
From 1 to 50.
A very practical question for everyone who had ever played a lottery.
So many lotteries are about getting the six random numbers in this range.
So if you want to compute the odds of winning, then winning a jackpot,
you need to find this number of different
ways of getting such a topple of six numbers.
Well, so in fact, many combinatorial questions were historically
motivated by gambling, by some games of chance,
such as card games, or games of dice, and so on.
So probably, you have already dealt with some combinatorial questions
when you were starting probability theory.
Well, another question is,
in how many ways can you split
say a $20 bill into smaller
bills of $1, $5 and $10?
Or another question is, suppose you're
climbing a ladder and here's your ladder.
And you can climb either one step or two steps at once.
So a typical way of climbing a ladder would be.
And here, climb one step up, two steps up, and then
another two steps, one step, and one step, and here you are on the top.
So if you are proceeding in this way, in how many ways can you climb this ladder?
If we're going either one or
two steps up at once.
Of course, we know how many steps does the ladder have.
Okay, so we'll be dealing with some questions of
finding cardinalities of finances,
finding the number of ways of doing something.
Before we start, let me tell you a couple of words about this course.
This course consists of eight lectures.
And the first half of our course, lectures from
one to four will be devoted to basic principles of enumeration.
And we'll be dealing with the basic commentorial problems involving
permutations, binomial coefficients in their many occurences and
sequences defined by layers of relations such as the Fibonacci sequence.
And some more involved in current relations, such as catalogue numbers.
And in the second half of our course we'll be dealing with a very powerful method of
solving combinatorial problems, namely with generating functions
and their uses in various combinatorial problems.
And in particular, we'll speak a lot about partitions, and
about variantions
of binomial coefficients, namely the Gaussian binomial coefficients,
or Q binomial coefficients as they are sometimes called.
So I hope you will enjoy our course and let's talk.
[SOUND]
