Explore
For Enterprise
Join for Free
Log In

艺术与人文
商务
计算机科学
数据科学
信息技术
健康
数学和逻辑
个人发展
物理科学与工程
社会科学
语言学习
学位和证书

浏览 Coursera 的全部课程

浏览
搜索
企业版
登录
免费加入

Pascal's Triangle

Loading...

离散数学

上海交通大学

3.5（94 个评分） | 23K 名学生已注册

查看授课大纲

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.

审阅

3.5（94 个评分）

5 stars
45 ratings
4 stars
13 ratings
3 stars
5 ratings
2 stars
9 ratings
1 star
22 ratings

AG

Dec 05, 2018

This course is good to comprehend relation, function and combinations.

MY

Aug 09, 2017

Short course!! I use it to review my discrete math knowledge.

从本节课中

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.

Pascal's Triangle14:57

教学方

Dominik Scheder
Assistant Professor

[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]

探索我们的目录

免费加入并获得个性化推荐、更新和优惠。

Coursera 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

© 2019 Coursera Inc. 保留所有权利。

通过 App Store 下载

通过 Google Play 获取

Coursera
关于
管理团队
工作机会
目录
证书
MasterTrack™ 证书
学位
企业版
政府版

社区
Learners
Partners
Developers
Beta Testers
Translators

连接
博客
Facebook
领英
Twitter
Instagram
YouTube
技术博客

更多
条款
隐私
帮助
内容访问
媒体
联系我们
目录
附属公司