Number of Tuples

Loading...

From the course by University of California San Diego

Combinatorics and Probability

112 ratings

University of California San Diego

Combinatorics and Probability

112 ratings

Course 2 of 5 in the 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.

From the lesson

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

Meet the Instructors

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

Hi. I'm Vladimir Podolskii. And today, we are going to discuss how to compute

Tuples and Permutations. Let's start with Tuples.

Now, let's consider the following problem: How many different five symbol passwords

can we create if you can use only lowercase Latin letters?

And so, the size of the alphabet that is 26.

So how many passwords are there?

And it turns out that to solve this problem we need only the rule of sum, and that's it.

But we need to solve this problem step-by-step,

and we should apply the rule of sum, the rule of sum step-by-step.

So, let's see how to do it.

And let's start with not five-letter password,

but just a one-letter password.

Then, clearly, there are 26 options for one letter,

and so, there are 26 possible passwords for one letter,

so this is not much.

Okay. Let's proceed to two letters.

Now, we have two letters and we have 26 options to pick each of them.

And this is exactly decision for the rule of sum.

We need to pick the pair of objects.

The first one we can pick in 26 ways,

and the second one we can pick in 26 ways as well.

So, the a rule of product tells us that there are 26 times 26 pairs, this is 676.

Okay. Let's proceed to third letters now.

And what we have now already know from

the previous calculations is that we can pick the first two letters in 676 ways.

Okay. Now, we can pick the third letter in 26 ways,

so we can apply the rule of product again.

Now, the element of the first set is already the pair of the first two letters,

and the element of the second pair or the second set is the third letter.

So, we have to multiply the number of elements in

the first set to the number of elements in the second set,

so we multiply 676 times 26,

and here is the answer.

That's already something. Again, not a lot.

There are not many passwords of three letters,

but already, we have some considerable number.

Okay. Let's proceed further,

and we can just argue by the same way.

We now know that the number of passwords,

the number of sequences of three letters.

We have already calculated the number of sequences of three letters.

It is 26 times 26 times 26.

We can pick the fourth letter in 26 ways.

So, now, we can pick,

so we can apply the rule of sum again.

The element of the first set is a triple of first three letters,

and the element of the second set is the fourth letter.

So, now, for four letters,

we have 26 times 26 times 26 times 26 possible passwords.

And we make this step again.

So, for five letters,

we now have 26 multiply by itself five times.

And this number, so this is how many passwords we need if we are only

allowed five letters and we can only use lowercase Latin letters.

Okay. So, we have shown these arguments on some specific example,

but this is a general argument.

Suppose now, we have the full one, the full one setting.

Supposed we have a set of n symbols.

So, we have to choose from n symbols now.

And we ask for one question: How many different sequences of

length k we can form out of these n symbols?

So, n and k are parameters. Here they can be anything.

These sequences are usually called "Tuples."

And this is the first standard setting we have to consider in combinatorics;

this is an important setting and we will use it later on.

Okay. So, let's see.

We can just play the same argument,

just instead of 26 for n and 5 for k,

we can now have arbitrary parameters.

Let's quickly go for this argument again.

There are n possibilities to pick the first letter.

And for each next letter there are, again, n possibilities,

so we apply the rule of product repeatedly and

each time we multiply by n. So, in the end,

the answer is the product of n by itself k times;

that is n to the k. So,

this is the answer in general form.

So, this is the answer in this standard setting of computing Tuples.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play