Principle of inclusion and exclusion: general statement

Loading...

Do curso por National Research University Higher School of Economics

Introduction to Enumerative Combinatorics

64 classificações

National Research University Higher School of Economics

Introduction to Enumerative Combinatorics

64 classificações

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.

Na lição

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

Conheça os instrutores

Evgeny Smirnov
Associate Professor
Faculty of Mathematics

[MUSIC]

The following formula, known as the principle of inclusion and exclusion,

generalizes the previous example.

Theorem,

Let A1....An be finite subsets,

Over a certain set X.

And suppose we know the number of elements in each of them and

in each of their intersections.

Then the inclusion-exclusion principle allows us to

find the number of elements in their union.

Then the number of elements in the union of these sets,

Is equal to the number of, The sum of numbers of elements in each of these sets.

Minus, The sum

of the number of n's in each double intersection.

So I need to take all pairs of i and j where i < j.

And take the number of

elements in each Ai cap Aj.

And then I need to sum it up with the total number of

elements in all triple intersections.

I'll take all triples i < j < k.

Ai cap Aj, Ak.

Minus all intersections of four, etc etc,

until we get the intersection of all of them.

And this intersection is taken with the sign -1 to the power n- 1.

So the sign in front of each intersection depends on the parity

of, Of the number of sets.

A1 intersected with, An.

So for n equal to 2 or 3, we get the formulas from our two previous examples.

This formula has several proofs and as an exercise,

I propose you to prove by induction.

This is not very hard.

By induction on the number of sets, of course.

And I'm going to show you another proof which is more combinatorial,

which is more in the spirit of our course.

And, It is as follows.

Let us take an element from this set.

Let, from the union of Ai's.

And let's see how many ways, well,

how many times do we count it in the right hand side?

How many times, How many times does it,

Appear, In the right hand side?

Well, to also their generality,

we can suppose that X belongs to the first p sets and

does not belong to the sets A p + 1 etc An.

Suppose that X belongs to A1 etc Ap,

so it belongs to their intersection as well.

And X does not belong to Ap+1,

Ap+2...An.

Okay, then this means that, this element

contributes into the right hand side of the sum,

the following number of times.

X contributes, To the right hand side,

With multiplicity.

Well, let's find this multiplicity.

So, X is counted among the first p summands here.

So it is counted p times in the first

group of summands with multiplicity p.

Then it also occurs in the double intersections and

it occurs in p, choose two of them.

And for each intersection,

it just counter with a negative sign.

So, if X belongs to p sets,

it is counted p choose two times in the double intersections.

p- p choose 2.

Then if p is greater than or equal to 3,

it appears in the triple intersections.

And in the triple intersections, it is counted p choose 3 times.

Then, In the intersections of 4,

it is counted p choose 4 times, etc.

Until we get -1 to the power

of p-1, p choose p.

And what is this sum?

Well, this is very similar to the sum of binomial

coefficients taken with alternating signs.

And this is in fact,

1 +, we add and subtract 1 from the sum,- 1 + p- p choose 2.

+ p choose 3- etc + -1 to

the power of p-1 p choose p.

And we know that the sum being the alternating sum of my

normal coefficients in one row over the Pascal triangle,

counted with a negative sign is equal to 0.

So, this is equal to 1, so that means that each element of

the union A1....An is counted

in the right hand side of this formula with multiplicity equal exactly to 1.

So, the principle of inclusion and exclusion holds.

So we have tend the principle of inclusion and exclusion.

And now we will apply it to a combinatorial problem of

counting the arrangements.

[MUSIC]

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2019 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play