Permutations

Loading...

Do curso por University of California San Diego

Combinatorics and Probability

130 classificações

University of California San Diego

Combinatorics and Probability

130 classificações

Curso 2 de 5 em Specialization Introduction to Discrete Mathematics for Computer Science

Counting is one of the basic mathematically related tasks we encounter on a day to day basis. The main question here is the following. If we need to count something, can we do anything better than just counting all objects one by one? Do we need to create a list of all phone numbers to ensure that there are enough phone numbers for everyone? Is there a way to tell that our algorithm will run in a reasonable time before implementing and actually running it? All these questions are addressed by a mathematical field called Combinatorics. In this course we discuss most standard combinatorial settings that can help to answer questions of this type. We will especially concentrate on developing the ability to distinguish these settings in real life and algorithmic problems. This will help the learner to actually implement new knowledge. Apart from that we will discuss recursive technique for counting that is important for algorithmic implementations. One of the main `consumers’ of Combinatorics is Probability Theory. This area is connected with numerous sides of life, on one hand being an important concept in everyday life and on the other hand being an indispensable tool in such modern and important fields as Statistics and Machine Learning. In this course we will concentrate on providing the working knowledge of basics of probability and a good intuition in this area. The practice shows that such an intuition is not easy to develop. In the end of the course we will create a program that successfully plays a tricky and very counterintuitive dice game. As prerequisites we assume only basic math (e.g., we expect you to know what is a square or how to add fractions), basic programming in python (functions, loops, recursion), common sense and curiosity. Our intended audience are all people that work or plan to work in IT, starting from motivated high school students.

Na lição

Basic Counting

Suppose we need to count certain objects. Can we do anything better than just list all the objects? Do we need to create a list all phone numbers to check whether there are enough phone numbers for everyone? Is there a way to tell whether our algorithm will run in a reasonable time before implementing and actually running it? All these questions are addressed by a mathematical field called Combinatorics. In this module we will give an introduction to this field that will help us to answer basic versions of the above questions.

Number of Tuples5:16

Licence Plates3:32

Tuples with Restrictions5:03

Permutations9:29

Conheça os instrutores

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Vladimir Podolskii
Associate Professor
Computer Science Department

So we have discussed how to count the number of Tuples,

and now we can move on to

our second standard combinatorial setting, permutations.

We will count how many permutations are there.

Consider the following general problem.

Suppose we have a set of n symbols and we would

like to count how many different sequences of length k are there,

consisting of these n symbols but with additional restriction,

we are now not allowing to use the same symbol twice.

Tuples of length k without repetitions of letters are called k-permutations.

And this is what we are going to compute in this problem,

the number of k permutations are going to compute in this problem.

And let's make the following useful observation,

if n is less than k,

if the number of symbols in our disposition is less than

the length of sequence they are trying to construct and we

are not allowed to repeat letters.

Then the answer is simple,

there are just no permutations as there are just not

enough different letters to construct the sequence of

length k. So in this case the answer is zero,

and this case is simple.

So, let's further on assume that k is at

most n. Let's consider this case, on trivial case.

Let's proceed to solution to our problem.

Here we see our sequence we denote the symbol by

star so lets numerate them from one to k.

And we will apply the rule of product,

we will solve this problem using the rule of product.

The first symbol we can pick in n ways.

What about the second symbol? How many choices do we have there?

And note that we can place there anything

except the symbol we already placed in the first position.

So there are n minus one options for the second symbol.

The symbol in the first position might be any symbol,

but for any symbol in the first position

there are n minus one possibilities for the second symbol.

So there are n possibilities.

For the first symbol, for each of them,

there are n minus one possibilities for the second symbol.

So in total, we have n times n minus

one possibilities to pick the first and the second symbol.

And now we can proceed in the same way.

Consider the first symbol,

we can pick the first two symbols by n times n minus one ways.

And for the third symbol,

whatever the first and the second symbols are,

for the first symbol we have n minus one options,

all symbols except the symbol in

the first position and the symbol in the second position.

So there are n minus two possibilities for

all ways to pick the first and the second symbol.

So for the first three symbols,

we have n times n minus one times n minus two possibilities, and so on.

For each next symbol, we have one less option.

And in the end,

so for the last symbol we will have n minus k plus one options.

So this might require a moment of reflection,

why it's n minus k plus one and not n minus k?

One easy way to observe it is to look at- so

let's see if near the first symbol we have one number above and one number below,

one and n. For the second symbol its the same,

we have two numbers two and minus one.

Know that for each symbol, for the first,

for the second, for the third, and so on,

the sum of these numbers is n plus one.

And when we move to the right,

the first number increases,

the second number decreases.

So then, the sum of these numbers always stay to be equal to n plus one.

So in the end it's also should be equal to n plus one.

So which would be minus k plus one below there.

So that's the easy way to observe that this is in minus k plus one.

There are n minus k plus one options there,

for the last symbol.

So in total, we have to multiply all of

these options and so we have n times n minus 1, and so on,

times n minus k plus one k-permutations of symbols of

length n. So this is not a very nice looking formula.

There is a convenient notation to make it look more simple and more short.

A convenient notation is n factorial. N factorial is just a product

of numbers from one to n. One times two, and so on, times n.

And in this notation, the number of k-permutations of n symbols looks nicer.

It has notes that we have product of- The answer to

our problem was the product of all numbers.

We multiply n by n minus one,

by n minus two, and so on,

but we stop on n minus k plus one.

So we can write it as n factorial divided by n minus k factorial.

So we consider n factorial,

and we divide it by all multipliers we do not want in our product.

So the answer in these terms is n factorial divided by n minus k factorial.

One important observation to make,

what if n minus k is equal to zero? This is possible.

So what if n is equal to k?

Then this formula we have,

it looks like we try to divide by zero,

n minus k is zero so we are trying to divide something,

this is time to divide by zero.

No it's not, it's not time to divide by zero factorial.

And you haven't said what it is yet.

And the standard convention here to make this formula true only also for the this case,

the standard convention is to save a zero factorial, is one.

So this what we will agree upon and then

this formula works also for the case of n equals k. And we are done,

the answer to his problem is n factorial divided by n minus k factorial.

So, now let's consider the following specific example.

So we have n books, n different books,

and we would like to place them on the shelf in some order.

So how many different orders we can do it?

We can think of each book as a symbol.

And now what we need to do,

we need to count how many sequences of n symbols do we have.

And again, as is in the previous problem,

we are not allowed to repeat the symbol twice.

We cannot place the same book in two places simultaneously on the bookshelf.

So we need to count n-permutations of n symbols, and these are called just permutations.

If we have n permutations of n symbols,

then we can just omit the prefix n there and talk about just permutations.

this is various standard objects in Combinatorics.

And by the previous result we have n factorial of them.

We could show in our previous problem shows that there are n factorial of

such permutations and so there are n factorial ways to place n books on the shelf.

There are n factorials orders to place n books on the shelf.

And recall, if you have seen our first course, "What is a Proof?",

recall that we have used this formula when discussing magic squares.

In this week, we have started the discussion of Combinatorics.

This field is important and will be important for us.

It is important for Probability Theory.

It will be important for estimation of running time of

algorithms and it is also important in mathematics in general.

And we have already discussed

two standard settings in Combinatorics, tuples and permutations.

We have discussed how we can

compute how many tuples are there of certain lengths over certain alphabet,

and how many permutations are there of certain lengths over certain alphabet.

And these two settings already

help us in many settings.

We also have discussed recursive counting,

it is also useful especially if you are trying to compute something.

Not to produce a formula,

but to compute something by an algorithm,

recursive counting is very useful there.

But we still do not know everything we need.

For example, if we would like to count what

are our chances to get two aces in the card game if you have six card hand.

We still do not know how to do it,

and we will discuss this later on.

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.

© 2018 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play