Principle of inclusion and exclusion: two examples

Loading...

來自 National Research University Higher School of Economics 的課程

Introduction to Enumerative Combinatorics

51 個評分

National Research University Higher School of Economics

Introduction to Enumerative Combinatorics

51 個評分

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.

從本節課中

Binomial coefficients, continued. Inclusion and exclusion formula.

In the first part of this lecture we will see more applications of binomial coefficients, in particular, their appearance in counting multisets. The second part is devoted to the principle of inclusion and exclusion: a technique which allows us to find the number of elements in the union of several sets, given the cardinalities of all of their intersections. We discuss its applications to various combinatorial problem, including the computation of the number of permutations without fixed points (the derangement problem).

The cab driver problem17:26

Balls in boxes and multisets 110:20

Balls in boxes and multisets 26:04

Integer compositions11:21

Principle of inclusion and exclusion: two examples12:36

Principle of inclusion and exclusion: general statement9:59

The derangement problem19:22

與講師見面

Evgeny Smirnov
Associate Professor
Faculty of Mathematics

[MUSIC]

Now the topic that we're going to discuss today is the principle of inclusion and

exclusion.

Sometimes common elaborated as (PIE) We start with the following baby problem.

Example.

Suppose that in a class group, there are 24 students who

are able to speak Spanish, and 25 who speak French.

In a class group.

25 people speak Spanish.

And 24 speak French.

Suppose that there are eight people among them who are able to speak both languages.

My question is how many people can speak at least one foreign language?

How many students.

Speak at least.

One foreign language?

Well probably you have seen pictures usually used for solving this problem.

These are called Euler Venn diagrams.

So you can draw the sets of people speaking Spanish and

French as two circles overlapping,

and the intersection corresponds to,

to those who speak both languages.

So there are 25 people here and 24 here in this circle.

An the intersection consists of eight people.

So you want to find the total number of people in the union of these two sets.

And for this well of course you know how to do this, so if you want to find

the union of these two sets if you want to count the elements in the union.

You need to add the number of elements in S and F.

And if you do that, you count every one but you count the intersection twice.

Those who speak both Spanish and French are counted

first among the Spanish speakers, and then among the French speakers, so

if you want to find the total number of students in this unit

you need to subtract the intersection, S intersected with F.

So as you plug

in the values

here you get 25

+ 24- 8.

And this gives you 49- 8 that is 41.

So this was very easy.

Okay, let's consider another example with three foreign languages.

So suppose this is example two.

Suppose that in this class group there are people studying German.

And the number of Spanish and French speakers is the same.

And in addition, there are 15 people speaking German.

And among these, there are people who speak both German and Spanish.

And suppose that the number of such people is six.

Six speak German and Spanish.

And seven speak both German and French.

And on these there are people speaking all three foreign languages,

and suppose that the number of such people is equal to four.

Speak all three languages.

How to compute the number of people who speak at least one foreign language.

The question is again the same.

Okay, to do this we draw again,

the diagram with circles.

These are the Spanish speakers.

These are French speakers, and these are students speaking German,

and we'll put numbers 25, 24, and 15.

And what about the intersections?

So we have this set of students speaking both Spanish and

French, and there are eight people.

And in this intersection,

Spanish and German there are six people,

and here the row seven.

And also there is the triple intersection.

Which consists of four people knowing all three languages.

Okay, so

we'll want to compute the number of people speaking at least one foreign language.

How we do that, so we compute the number of

students in the union G ,union with S and union with F.

Is again the sum of all three groups of people,

speaking German, French, and Spanish.

And then we need to subtract the intersections because we count those who

speak two languages, we count them twice as in the previous example.

So we get, we need to subtract those who

speak both Spanish and French,

The intersection we subtract those speaking Spanish and German.

And we subtract those speaking German and French.

Okay, and now we are left with the triple intersection.

So the question is,

how we counted these students who speak all the three languages or not.

And if we did, how many times did we count that.

So let's see.

First, we counted the intersection three times when

we were adding G, F and S.

So these four people were counted three times.

And then we have subtracted each of them also

three times because they were counted among these

who spoke Spanish and French, Spanish and German, and German, and French.

So this means that we haven't counted them in the sum yet.

But we want to count them once.

So we need to add the intersection.

S intersected with F,

intersected with G.

And again, as we take the numerical

values we get that this is equal to

25 + 24 + 15- 8- 7- 6

+ the triple intersection which is four and

if I am not mistaken, I hope i am not.

We'll get.

47 as the total number of students who are able to speak,

at least one final language.

But okay, this numbers are not that important as this formula.

From this you can see it's structure, as you compare this formula with this one.

To count the union of three sets you

need to add up their cardinalities, and

then subtract the double intersections, and then add the triple intersection.

So the same thing holds here.

First you add the two sets and

then the cardinalities of these two sets, and then you subtract the intersection.

So here you take these intersections

interchangeably with plus and minus signs.

So if the intersection has, as here.

Two components, then you take it with a negative sign.

And if It has one of three components you take it with a plus sign.

And the generalization of this formula is called the inclusion exclusion formula.

And we're going to write it in the general form right now.

[MUSIC]

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

© 2018 Coursera Inc. 保留所有權利。

通過 App Store 下載

通過 Google Play 獲取