Hi everybody and welcome back to the next module of the combinatorics course.

In this module, we are going to still discuss questions of the form.

How many objects are there satisfying some particular properties.

We will see many interesting questions.

And more importantly we will see solutions to such questions.

And in many cases we are going to

complement the solutions I'm sorry with simple Python script.

So, before going into the details,

let's first review what we've learned in the previous module.

So, the first one is the rule of thumb.

So, if we have N object of first type and

K objects of the second type and these two sets of objects do not intersect,

meaning that they do not share any common object.

Then they are exactly N plus K ways of selecting some object out of these two groups.

Okay? So, to give an example consider these two sets or two lists.

So, the first list is that A it consists of Alice, Bob and Charlie.

And the second list is B and it consists of four digits.

Zero, one, two and three.

Then if you compute the sum of these two lists,

then it will contain all these elements and of course it has length seven, right?

That's expected. The next one is the Rule of

Product and it says that if you have N object

in one hand and K object on the other hand and you would like

to select a pair of two objects,

one of the first type and one of the second type.

And the number of ways of doing this is equal to N times K. Once again,

let's check this with Python on some small example.

So I assume that we have a list A consisting of just two letters A and B.

And also we have this B consisting of three digits one, two and three.

Then the number of ways of forming a pair of

an object from the list A and an object from the list B is equal is to 6.

That is to the product of the lengths of A and the lengths of B.

All such possible pairs are shown here on the slide.

So, you can either take A or B.

So, these are two choices.

And then you can as a second element,

you can either take one,

two or three. So, three choices.

So, the number of ways is two times three.

Okay? So, the next important object is Tuples.

So, the number of way of,

if you have N objects and you would like to organize,

you would like form a tuple consisting

of- or you would like to form a ward consisting of

K elements such that you allow repetitions that is of any position.

They can be any of your elements than the number of

ways of doing so is when there's a K. Once again,

let's show an example.

It seems that we have two letters A and B and we would like to construct

all possible sequences of lengths for that consist of letters A and B.

Then the number of ways of doing so,

is equal to two to the power of four.

Right? And indeed.

So, for any of four positions

you have two choices right? You either take A or you take B.

So, by the product rule the number of ways of doing so

is two times two times two times two which is nothing else as two to the four.

Right? And all such positions are shown here on the slide.

So, the first such possibility is A A A A and then the last one is B B B B.

And you can generate all such tuples using

the product method that of itertools library.

Okay? So, finally let's discuss A-Permutations.

In this case, what you would like to do is given letters

you would like to form a word of lengths

and such that there are no repeated elements in this word.

Okay? Or in other words you would like to construct the K permutation.

Okay? So, in this case for the first position,

you have N choices because you can select any of N elements.

For the second position,

you have N minus one choices and in all the remaining elements except for the first one.

For the third position,

you have N minus two choices and so on.

So, by the product rule once again,

the total number of ways of doing so is N times N minus one,

times N minus two times and so on N minus K plus one.

And it is convenient to write this product as follows.

It is N factorial divided by N minus K factorial.

As usual let's try to generate all such K permutations.

We're going to do this with the method called permutations.

And I assume that we have five letters A B C D E and we're

going generate all permutations of size two.

So, for the first position, we have five choices,

for the second position we have four choices.

So, the number of ways of doing so is equal to 20.

Let's check it and indeed the following code produces us all 20 such two permutations.

So, it all starts with AB and it all ends with ED.