Permutations

Let me ask you a question:

“Suppose that I have a bag with 3 balls in it. How many ways are there to pick 2 balls out of it?”

Well, what do you think? Most people would say that you have three ways of doing so, you can name the balls (first, second, third) and then the options are to pick:

First and Second balls.
First and Third balls.
Second and Third balls.

And that’s a well explained answer – That was my answer. However, who said that you can’t also pick, for example, the first ball twice? If you can, then the options are:

That is, 6 options! when you allow – repetitions / multiple selections of the same ball, you get more options .

Moreover, who said that picking the first ball and then the second, is the same as picking the second and then the first? Let’s see how many options are there when you consider both cases as different:

And that’s 9 options. When you consider the order of the selection, there are more options. Last one – how many selections are there if order matters, and you can’t selected the same ball twice? Let’s count the options:

So we got 6 options. Let’s summarize:

	Repetitions allowed	Repetitions are not allowed
Order matters	9	6
Order doesn’t matter	6	3

So we have found multiple ways to interpret the question. What are the conclusions?

The question is not well-defined.
There are 4 ways to answer it.

Something a bit more complicated

Now let me ask you another question, how many ways are there to pick 45 balls out of a bag with 120 balls, where repitions are allowed and order matters?

Umm… I have kind of an answer for it – a lot! I am not intending on listing all the options, since there are so many!

However, by the end of the post I will be able to give you an exact answer with no effort at all! You know what? I’ll just write the answer now so you would understand why I am not planning on counting the options manually:

3,657,261,988,008,837,196,714,082,302,655,030,834,027,437,228,032,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000

FYI, if you don’t believe me and decide to count the options yourself, and let’s also assume that every second you count one option. If I am right – then to count it will take you this much years:

115,894,114,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000

So if you have a plan to count the options – I suggest you to drop it.

The plan

As I said before, I am going to present here and in the next post an easy way to answer this question. And not just this question, but a lot more! Such as:

If you participate in a race against 20 equally skilled other people, what are the odds that you will win?
Suppose that you are in a restaurant and there are 5 different meals you can order. However, you can only pick 3 – In how many ways can you do so?
How many integer solutions are there for the equation: $x_1 + x_2 + x_3 = 8$ ?

OK, let’s begin:

What are Permutations?

A permutation of $k$ objects out of $n$ , is a selection where order matters.

There are two types of permutations:

permutation with mutiple selections.
permutation without multiple selections.

Let’s find out how many permutations are there where mutiple selections are allowed:

mutiple selections – allowed

Suppose that there are $n$ different options, and you need to select $k$ objects. How many options you have for the first selection?

Well, since there are $n$ objects – you have $n$ options. What about the second selection? There are $n$ objects, and since you can pick an object more than once, it doesn’t matter what we have picked before – thus, there are, again, $n$ options!

The same argument applies to the third selection, the fourth, the fifth and so on…

Here, k= 4 (number of selections) and n = 3 (number of object)

I think we are ready to count now:

First of all, we have $n$ objects to choose from. Every object you pick, yields a different choice.

After you chose the first object, you have again, $n$ object you pick.

So the coices are:

Picking the first and then the first / second / the third / … / the n-th object – ( $n$ choices).
Picking the second and then the first / second / the third / … / the n-th object – ( $n$ choices).
And so on… until:
Picking the n-th and then the first / second / the third / … / the n-th object – ( $n$ choices).

In total, we find out that there are $\overbrace{n}^{\text{first choice}} \cdot \overbrace{n}^{\text{second choice}} = n^2$ choices!

This is a really important thing to understand, make sure that you do! What I just presented now is the Rule of product – which simply states that:

“if there are a ways of doing something and b ways of doing another thing, then there are a · b ways of performing both actions.” (cited from wikipedia)

Implementing the ‘Rule of product‘

Ok, let’s implement this idea: After you have picked the second object, again, you have $n$ objects you can pick. Therefore, the nubmber for 3 object, the number of the selections is:

\overbrace{n}^{\text{First choice}}\cdot \overbrace{n}^{\text{Second choice}}\cdot \overbrace{n}^{\text{Third choice}}= \overbrace{n^2}^{\text{First two choices}} \cdot \overbrace{n}^{\text{Third choice}}=n^3

For a general $k$ , the number of options to pick $k$ object when multiple selelctions are allowed is:

\overbrace{n}^{\text{First choice}}\cdot \overbrace{n}^{\text{Second choice}}\cdots\overbrace{n}^{k\text{-th choice}}=n^k

That’s it!

Quick solution to the latest problem

If we apply it to the problem where we need to pick 40 balls out of 120 balls, then the number of the choices to do so is:

{\underbrace{n}_{\text{balls}}}^{\overbrace{k}^{\text{selections}}}=120^{40}

And that is how I solved the problem from the begining – without spending all my life listing selections!

mutiple selections – not allowed

After we have met the rule of product, this is going to be easier. Same as before, I have $n$ objects to choose from in the first selection.

However, after I pick one obejct, in the second selection – I can’t pick it again. Thus, I have $n-1$ object to pick from. In the third selection, I have $n-2$ object to choose from…

Therefore, by the rule of product, the number of choices to pick $k$ out of $n$ objects where you can’t select an object more than once is:

(\overbrace{n}^{\text{First choice}} )\cdot( \overbrace{n-1}^{\text{Second choice}})\cdots(\overbrace{n-(k-1)}^{\text{k-th choice}})

And I’ll denote it by:

(n)_k=n\cdot(n-1)\cdots(n-(k-1))

Factorial

If you are not familiar with this term, I define the facotrial of a natural number as:

n!=n\cdot(n-1)\cdot(n-2)\cdots1

Where we define $0!=1$ (it makes sense – we’ll see it in the future), notice that:

\frac{n!}{(n-k)!}=\frac{n\cdot(n-1)\cdots\overbrace{(n-k)\cdot(n-k-1)\cdots1}^{(n-k)!}}{(n-k)!}

=\frac{n\cdot(n-1)\cdots(n-k+1)\cdot (n-k)!}{(n-k)!}=n\cdot(n-1)\cdots(n-k+1)=(n)_k

So antoher way to represent $(n)_k$ is by the fraction $\frac{n!}{(n-k)!}$ .

Quick example

Suppose that there is race with 10 Competing, in how many different ways can it end?

For the first place in the race there are 10 options – which is the number of the competings.

After we ‘picked’ a winner – there are 9 cometings left – so there are now $10\cdot 9 = 90$ different possibilities. I think that you understand where I am going with it…

This question fits exactly what we have just seen. The nunmber of outcomes of the race is exactly the number of choices to pick 10 objects (competings) out of 10 objects (places in the race). The answer is:

(10)_{10}=\frac{10!}{(10-10)!}=\frac{10!}{1}=10!

Summary

So we’ve met the term of a permutation here. However, the job is not done! In the next post I will introduce the term of a combination and by doing so – We’ll be able to answer all the question from the introduction, and a lot more!