The derangement problem

Loading...

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

Introduction to Enumerative Combinatorics

55 個評分

National Research University Higher School of Economics

Introduction to Enumerative Combinatorics

55 個評分

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 we'll apply the inclusion and exclusion principle to the so

called derangement problem.

But before that, let me make just one remark to the inclusion and

exclusion principle.

Sometimes it turns out that the problem we're considering is symmetric in

the following sense that,

If we have the sets A1, etc., An,

then the number of elements in each intersection of k sets,

Ai intersected with Ai1 intersected with Ai2, etc.

Aik does not depend,

On the Ai's, But only on k.

This means that each intersection of k sets has the same

number of element, elements depending only upon k.

In particular, all the sets, A1 etc., An, consists of the same number of n's.

And we note this number by A to the power of k.

It is by definition the number of elements in each of these.

Then, the inclusion-exclusion formula can be written in the following form.

Then the number of elements in the union,

Is n times A, which means that we take the sum, the cardinalities,

of all Ai's minus the double intersections,

which all consist of the same number of elements.

And there are n choose 2 of

them, plus n choose 3.

A cubed minus, minus etc.,

plus negative 1 to the power

A minus 1, A to the power n.

And this is this symmetric variant

of the inclusion exclusion formula.

And now, let us apply this formula to the derangement problem.

The problem is as follows.

Suppose we have and people who come to a theater and

each of them leaves their coat in the cloak room before the play

and after the play ends, everyone gets a coat back.

But let's say that the attendant does not look at the tickets.

So he gives to each person some random coat which may not

belong to him, but which may belong to someone else.

So n people leave their

coats, In the cloak room.

And afterwards each of them gets a random coat.

Gets, Back a random coat,

Which may belong to him or to someone else.

And what is the probability that everyone will get someone else's coat?

Well sometimes this problem is formulated with,

N letters which are sent by secretary and

they are put into envelopes but the secretary

puts each letter into random envelopes, and

what's the probability that everyone will

get a letter addressed to someone else?

Okay, so the total number of configurations of

permutations is, as we know, n factorial.

N factorial is the total number, Of permutations.

Well, configurations of coats.

And our question is, in how many

ways does this permutation map each

number into a different number?

So, how many permutations out of these have no fixed points?

That is, That

they never map a number into itself.

Well to compute those, we're going to compute the opposite number,

namely the number of permutations having at least one fixed point or

the number of situations where someone will get his or her own coat back.

So, we compute

the number,

Of permutations with fixed points.

And let Ai denote the set of

permutations bringing i to itself.

And while in similar way,

if we take any subset of

numbers from 1 to n,

Ai1 intersected with Aik

is the set of permutations

bringing I1 into I1 etc., Ik into Ik.

And what we want to get,

we're interested in the number n factorial

minus A1 union with A2 union with An.

And how to compute this number?

Well first we, let's look at each individual AI.

The number of elements inside each AI, Actually it does not depend upon I.

So where in this situation, and this means that this permutation brings i to i.

And for all the remaining n minus 1 variable, there are no restrictions.

So there are n minus 1 factorial possibilities.

And let us look at intersections of k, and

this means that a permutation from this set

brings i1 into i1, etc., ik into ik.

So for k entries, their position is fixed.

And the remaining n minus k entries can be mapped either

to any other entries different from i1 etc., ik.

So, Ai1 intersecting with Aik.

Undenoted by A to the power of K and

this is n minus K factorial.

Okay, then let us apply

this version of the inclusion, exclusion principle.

So then the unit, This is

the set of permutations

having fixed points,

A1 union with A2 union

with An is n times,

n minus 1 factorial,

minus n choose 2,

times n minus 2 factorial plus etc.,

plus negative 1 to

the power of n minus one,

times 0 factorial.

So we see that this is n factorial.

This is n times n minus 1 over 2 times n minus 2 factorial.

So this is n factorial, Divided by 2 factorial.

Plus, again in the numerator, we get n factorial.

And in the denominator we get 3 factorial.

Minus etc., plus.

Negative 1 to the power n minus 1,

n factorial divided by n factorial.

And the total number of configurations

is n factorial minus this sum.

And let me write it as follows.

n factorial minus A1, etc, An.

Such permutations are called derangements.

Is n factorial times 1 minus 1

plus 1 over 2 factorial minus

1 over 3 factorial plus etc.,

plus minus 1 to the power n divided by n factorial.

And, This is the number

of derangements, the number of configurations,

such that each person does get someone else's coat.

And if you want to find the probability, you need to divide it by

the total number of configurations, namely by n factorial.

So, let me write down this probability.

So, we have found the number of derangements.

And the probability is obtained as,

well let me denote it by p of n as a function of n.

It is obtained as the total number of derangements,

here it is, divided by the total number of configurations, n factorial.

So, this is 1 minus 1 plus 1 over 2

factorial minus 1 over 3 factorial plus etc.,

plus negative 1 to the power n divided by n factorial.

And while this formula allows you to compute

this probability for an arbitrary n, but it is instructive to look at

the limit of this value as n tends to infinity.

So you probably remember the series for the exponential.

So e to the power x can be found as 1

plus x plus x squared over 2 factorial

plus x cubed divided by 3 factorial

plus etc., up to infinity.

Let me put here x to the power n divided by n factorial plus etc.

So as n tends to infinity.

This series gives you exactly the exponential of negative 1.

So, The limit of P of n,

as n tends to infinity,

is 1 minus 1 plus 1 over 2

factorial minus 1 over 3 factorial

plus etc., up to infinity.

And this is e to the power minus 1

which is 1 over e where e is the base of natural logarithms.

So where,

Where e is the base of natural logarithms, it's 2.,

71828,

etc.

And so 1 over e equals

approximately 0.37 so

and in fact this probability

converges to 1 over e pretty rapidly.

So if there are, say ten people come into a theatre,

the probability that everyone will get someone

else's coat is pretty close to this value,

so a little bit more than one third.

And this problem is,

As I said, an amazing example where the combinatorial

problem where problem completed from combinatorics,

gives you such a value as e as the base of natural logarithms.

Something that as we usually think belongs to analysis,

belongs to a completely different branch of mathematics.

But here we get it in a combinatorial problem.

So this problem as we have put it,

shows the unity of different branches of mathematics.

This is all for today, thank you.

[MUSIC]

探索我們的目錄

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

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

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

通過 App Store 下載

通過 Google Play 獲取