Discrete mathematics forms the mathematical foundation of computer and information science. It is also a fascinating subject in itself. Learners will become familiar with a broad range of mathematical objects like sets, functions, relations, graphs, that are omnipresent in computer science. Perhaps more importantly, they will reach a certain level of mathematical maturity - being able to understand formal statements and their proofs; coming up with rigorous proofs themselves; and coming up with interesting results. This course attempts to be rigorous without being overly formal. This means, for every concept we introduce we will show at least one interesting and non-trivial result and give a full proof. However, we will do so without too much formal notation, employing examples and figures whenever possible. The main topics of this course are (1) sets, functions, relations, (2) enumerative combinatorics, (3) graph theory, (4) network flow and matchings. It does not cover modular arithmetic, algebra, and logic, since these topics have a slightly different flavor and because there are already several courses on Coursera specifically on these topics.
Pascal's Triangle
Loading...
来自 Shanghai Jiao Tong University 的课程
Discrete Mathematics
59 个评分
从本节课中
Enumerative Combinatorics
A big part of discrete mathematics is about counting things. A classic example asks how many different words can be obtained by re-ordering the letters in the word Mississippi. Counting problems of this flavor abound in discrete mathematics discrete probability and also in the analysis of algorithms.
与讲师见面
Dominik SchederAssistant Professor
The Department of Computer Science and Engineering
[MUSIC]
Hello everybody, at the end of last time,
we saw that we need a deeper understanding of the bionoiminal coefficient.
N choose k, if we want to obtain compact nice formulas for
certain sums and count more sophisticated objects.
So this time, we start the battle against the binomial coefficient,
let's try to see, let's see how far we get.
So the first thing, I want to show you by the binomial coefficient,
it satisfies this nice recurrence.
So this fact actually have two proves, one is just by pure calculation and
one is more about thinking about what n choose k means.
So let me give you the proof by calculation first.
So remember, we have a formula for the binomial coefficient,
which is n factorial divided by k factorial times n minus k factorial.
And now we can just plug in the formula into
our recurrent appearance to see whether it works out.
So let's try to do that, so
what is n-1 choose k + n-1 choose k-1.
Okay, let's just plug in the formula that we have.
This is n-1 factorial divided
by k factorial, and here,
we get n-1-k factorial.
And here we get n-1 factorial, and
here, we get k-1 factorial and n-k factorial.
Okay, let's put the fraction together, so what is the common denominator,
the common denominator is k factorial n-k factorial which is already quite good.
And the first term, we have to multiply by, so
this we have to multiply it by the term that's basically missing down here.
Yeah, which term is missing down here,
that is n-k, and here,in the right term,
the factor that is missing down here is factor of k.
So this is times k, and
now you see we can factor out the n-1 and
get n-k+k divided by this
And now this is of course, This n and then this together is the n factorial.
So we're done because this is again the formula for n choose k, but
this just a proof of your calculation.
It's not very inspiring, let me show you a little bit more inspiring proof
that actually tells you why this recurrent formula is true.
So let this be our set of size n and
let's take an element x in the set.
Now if you want, if we select the subset of size k, this is a subset x of size k.
There are two possibilities.
First, we include this element x in our set,
and we select k-1 additional
elements from the rest.
And for this, how many chances do we have?
Well n-1 choose k-1, right?
Because there's n-1 elements left, and
we have to take k-1 from them, or we could choose to not include x.
But then have to select,
We have to select k elements from the rest.
I mean from the set without x, so for
this now we have n-1 elements left, and we have to select k of them.
So the total number of choices is just this plus this, all right?
So together,
it gives the full number of choices which we have seen as n choose k, right?
This is a more intuitive proof of the recurrent formula.
All right, so here is a nice thing kind of a fun thing you can do with a formula.
So let me write, for example, 3 to 0, 3 to 1 and so on, in one row.
What it basically tells you, for
choose 2 is simply the sum of these guys upstairs.
And 4 to the 4, I mean, technically would be the sum of this, but
what do we have here?
Well here technically, we have 3 choose 4, but
this is of course 0, because you cannot select 4 elements, right?
There are not enough elements around.
So we can, okay, kind of this, and
I mean if you do that so let's fill in the numbers.
You see, kind of the first row, we have here is 1 3 3 1, and
then the next would be like this.
And of course, I mean this row also comes from something.
So actually, we can start like this.
This would be 0 choose 0, and then this would be 1 choose 0, and so on.
And we get the next row by just adding up the two neighbors upstairs.
And it goes on like this like 15 20 15 6 1, and let's do one more.
Okay, my computer is bugging me about some whatever,
some Wi-Fi or something, no idea what.
All right, so we get a kind of triangle,
where the nth row at the kth position has a binomial coefficient n choose k.
And this has a name, it's called Pascal's triangle.
And a fun thing happens, if you take Pascal's triangle module two.
So you're only looking at which numbers are odd and which are even.
So let's mark all the odd numbers, so these are odd, this is odd,
and then this is odd, and here this is odd, this is odd, this odd.
So we get kind of a certain structure, and if use a computer to plot this,
or you simply to go Wikipedia and look at the figure, you get this kind of
nice fractal like object which is called Sierpinski triangle.
Now this is called Sierpinski triangle.
So let me write this, this is basically n choose k modular 2.
Another important thing with a binomial coefficient appears as
the following formula.
So in high school, you might have learned
the following formula x + y squared is x
squared + 2xy + y squared.
And maybe you even remember the formula for this.
Anyway, but today we will see a formula for general n, which is the following.
It's called the binomial theorem x + y to the n is this complicated sum, and
let me explain it a little bit.
So here, this is an expression with two variables.
This is called a binomial and this is it's coefficient, right?
In this expression, and therefore it's named binomial coefficient there is
where the name actually comes from.
So again, I want to show you to proof of the theorem.
First one with a lot of calculation, and then approve with just thinking.
Here's the first proof.
Use induction on n.
Our base case is that n = 0 in which case x + y to the 0 is 1.
And the right hand side would be the sum from 0 to 0,
0 choose k, x to the ky to the 0-k.
You can easily check this, it's also 1.
So for the step, we suppose the formula is correct for n, and
we have to prove it for n + 1.
So what is x + y to the n + 1?
Well one thing that is easy to see, it's x + y times x + y to the n.
So now by induction, we can plug in the formula for x + y to the n,
because we can assume by induction that the binomial theorem is true.
Here's a little trick to make things a little bit easier.
In this sum, we sum up from k = 0 to n, but actually, you can convince yourself,
we can actually sum up of all values k, of all integers k.
Because if k is not in this range, for example, is k is negative or
larger than 0, then n choose k is, if you look into the definition anyway 0.
So by just letting k run over all integers, we just add a bunch of zeroes.
So we don't change the sum, but it makes the proof a little bit easier.
Okay, so we use the induction hypothesis and
see that this is x + y times n choose k,
x to the k and y to the n-k.
And now we can expand this product,
we get x times the sum plus y to the sum, so we get now two sums.
The first sum, we multiply by x, so we get k + 1 up here,
and the second sum we multiply by y.
So, x to the k,
y to the n+1-k.
And now we do some little trick that's called a change of variable.
We say, hey, look in this sum,
we renamed k + 1 to bj.
And if we do that, then we get over here the sum of all j,
now you have to think what is k?
Well k is j-1, and then now we get x to the jy,
and now you have to think what is n-k?
Well n-k turns out to be n+1-j, and
here, we simply get the same sum.
And now you see the change of variable,
because we set to k ranges over the whole integers.
Now we set j to be k + 1, it also ranges over the whole integers.
So we don't need to keep track from where to where the variable runs.
And this makes the change of variable a little bit easier,
we just have to think less.
And now you see, this term here, it's the same as here.
So now we can pull the two sums together,
and we actually get the sum over all k, x to the k,
y to the n+1-k times the sum of these two things times.
Let's see whether I have enough space,
n choose j-1 + k-1, now change the name back n choose k.
And by our recurrence formula, we know that this is simply n + 1 choose k.
All right, so this is the inductive proof of this theorem.
Now that would be the last thing for today.
I want to show you the kind of more intuitive proof of this theorem.
So x + y to the n equals, and you can just write it out.
If you think about it,
this is a sum of 2 to the n terms, right?
If you multiply it out for every combination you get a sum of, so
you get 2 to the n total.
And when do we get like x
to the k time y to n-k?
Well when we select, x
in k out of on all n (x + y),
and there are n choose k ways to select that.
And therefore, the coefficient of x to the k times y to the n-k is exactly
the binomial coefficient n choose k.
All right, that's it for today, thanks.
[MUSIC]
