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:

- 1,2
- 1,3
- 2,3
- 1,1
- 2,2
- 3,3

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:

- 1,2
- 2,1
- 1,3
- 3,1
- 2,3
- 3,2
- 1,1
- 2,2
- 3,3

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:

- 1,2
- 2,1
- 1,3
- 3,1
- 2,3
- 3,2

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: ?

OK, let’s begin:

## What are Permutations?

A **permutation** of objects out of , 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 different options, and you need to select objects. How many options you have for the first selection?

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

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

I think we are ready to count now:

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

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

So the coices are:

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

In total, we find out that there are 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 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 , the number of options to pick 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 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 object to pick from. In the third selection, I have object to choose from…

Therefore, by the rule of product, the number of choices to pick out of 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 (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 is by the fraction .

#### 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 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!