Combinations

Loading...

Del curso dictado por University of California San Diego

Combinatorics and Probability

129 calificaciones

University of California San Diego

Combinatorics and Probability

129 calificaciones

Curso 2 de 5 en SpecializationIntroduction 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.

De la lección

Binomial Coefficients

In how many ways one can select a team of five students out of ten students? What is the number of non-negative integers with at five digits whose digits are decreasing? In how many ways one can get from the bottom left cell to the top right cell of a 5x5 grid, each time going either up or to the right? And why all these three numbers are equal? We'll figure this out in this module!

Previously on Combinatorics5:50

Number of Games in a Tournament10:54

Combinations8:31

Conoce a los instructores

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

We are now ready to introduce an important combinatorial object called combination.

So imagine that you are going through a car journey.

And you have five friends,

but unfortunately you have only three vacant places in your car.

So what you would like to compute is a number of ways of selecting three

of your friends out of five that you are going to take

with you to your journey out of five of your friends, okay?

Of course, in this case we don't care who of your three friends is going to

sit where in the car.

So basically, what we're looking for, so

speaking more formally is what is the number of ways of selecting

three elements out of five elements, okay?

So let's try to compute these number of ways.

So you need to select three friends.

There are five choices of the first friend, four choices of the second friend,

and three choices of the third friend, right?

So this gives us 5 x 4 x 3.

But as we've seen already, this actually computes not the number of

subsets of three friends, but the number of three permutations, right?

In particular, each subset for example,

of friends a, b, c was counted six times.

It was counted as abc, for example, as acb,

as bac, bca, cab and cba.

But since we're not interested in the actual arrangement of

these three elements, we need to divide everything by six, right?

So we would like to count each subset exactly once while in

our current estimate, it was counted exactly six times.

So the final answer is (5 x 4 x 3) divided

3 factorial, which gives us 10.

So this is an important combinatorial quantity.

Let's also justify our count just by trying to generate all such combinations,

namely here we have five friends, a, b,c, d, e.

And we asked the combinations method to compute all possible

subsets of size 3 of all these five letters.

So what it gives us is exactly ten such possibilities, okay?

Now, we're ready to give a definition.

So if we have a set, S, then it's k-combination is a subset of size k, okay?

So, and the number of different such subsets of size k

is denoted by n choose k.

So where n is the size of the set S.

So more precisely or more formally, n choose k is defined with the number

of different subsets of size k, of an n element set.

And once again, it is pronounced as n choose k, and

it is written like this, okay?

So, this is a very important combinatorial quantity.

So in particular, you can go to Google and compute any such number.

For example, if you compute 5 choose 3 in Google,

it will give you a result, okay?

Once again, it is 10.

So there are ten ways of choosing three of your friends out

of five of your friends, okay?

Now, before giving the formula, let's look once again

at the difference between the number of 3-combinations and 3-permutations.

So let's list all possible 3-permutations.

So recall that in a 3-permutation, we just would like to put one of your five

friends to the first place, then one of the remaining four friends to the second

place, and then one of the remaining three friends to the third place.

So this gives us 5 x 4 x 3 which is 60, and all 60 permutations,

3-permutations are shown here on the slide.

And they are arranged in a nice way such that as you see in the same column,

we have exactly the same three elements permuted, right?

And we know that for elements abc,

there are exactly 3 factorial possible ways of permute them, right?

So in which means that the number of 3-permutations

is 3 factorial larger than the number of 3-combinations.

More precisely, what we see here is that in this table, the height of this table is

3 factorial while the width of this table is 5 choose 3.

At the same time,

the total size of the elements in this table is the number of 3-permutations.

And we know how to compute it.

The number of 3-permutations is 5 x 4 x 3

which is nothing else as 5 factorial divided by

2 factorial which is just 5-3 factorial.

So this gives us the following formulas.

The number of elements is equal to the height of this

table times the width of this table, okay?

And this will lead us, this substitution will lead us to the general formula for

computing n choose k.

So the formula is as follows.

n choose k is equal to n factorial divided by k factorial,

and divided by n minus k factorial, okay?

So this is the formula and now let's try to prove it.

So we have actually everything needed to prove it already, okay?

So first, let me remind you that n choose k is the number of

subsets of size k out of n elements, okay?

Now, first, let's count the number of k-permutations, okay?

So, for k-permutations, there are exactly n choices for the first element.

Then there are n-1 choices for the second element, n-2 choices for

the third element and so on.

(n- k +1) choices for the k-th element.

And this computes the number of k-permutations.

And we know already that it is equal to n factorial divided by (n-k) factorial.

Which is just a convenient way of writing the expression n times

(n-1) times (n-2) times (n- k + 1), okay?

And this says, as we've discussed already,

this computes the number of k-permutations but not the number of k-subsets.

And the number of k-permutations is exactly k

factorial times larger than the number of k-subsets, right?

Why is that?

Well, because just when we count the number of k-permutations,

every subset is counted exactly k factorial times.

Because if you have a subset of size k,

there are k factorial ways of permuting its elements, right?

Which finally gives us the estimate n factorial divided n minus k factorial.

Let me remind you that this part, n factorial divided by n minus k factorial,

is exactly the number k-permutations.

And we need to divide it by k factorial to finally

get the number of different k subsets, okay?

So once again, let me show you the results and estimate.

So n choose k is equal to n factorial divided by

k factorial divided by n minus k factorial.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2018 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play