Permutations

Order matters for Permutations.

How many ways can we order 3 numbers $(1,2,3)$? There are 6 ways.

• 1 - 2 - 3
• 1 - 3 - 2
• 2 - 1 - 3
• 2 - 3 - 1
• 3 - 1 - 2
• 3 - 2 - 1

The number of ways is just $n!$

Quick explanation: How many ways can we select the number in the first position, we have 3. Now we have 2 options for the second position. Similarly, only 1 choice for the third position.

ways $= 3 * 2 * 1 = 3! = 6$

With repetition

Arranging $k$ items from $n$ is just $n^k$.

You have to pick $k$ items and $n$ choice for each of them.

Without repetition

Expanding on the example above, if we want to find the number of the possible ordering of 3 numbers from $(1,2,3,4,5)$.

• 5 choices for the first position
• 4 choices for the second position
• 3 choices for the third position

This is denoted by $P(n,k)$ - $n$ permute $k$. Defined as:

$P(n,k) = \frac{n!}{(n-k)!}$

So, for the above example, the number of ways is

$P(5,3) = \frac{5!}{2!} = 5*4*3 = 60$

---

In the next lesson, we’ll move on to combinations.