2.5 Permutation

How many possible ways to rank 2 teams A and B?

Assume there are no ties.

How many possible ways to rank 3 teams A, B, and C?

Assume there are no ties.

Permutation

An ordering of distinguishable objects

\[ \begin{aligned} \text{Permutations of }n &= n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1 \\ \\ &=n! \\ \end{aligned} \]

In a track race with 8 athletes, how many results are possible? (Assume no ties.)

Image source

\[8! = 8 \times 7 \times \cdots \times 2 \times 1 = 40,320\]

Python implementation

# Method 1: Import the entire module
import math

print(math.factorial(8))

# Method 2: Import a function from the module
from math import factorial

print(factorial(8))

How many podium (i.e., top three) results are possible? (Assume no ties.)

\[8 \times 7 \times 6 = 336\]

\(k\)-permutations of \(n\) objects

\(k\)-permutations of \(n\) objects

\[ n \times (n-1) \times (n-2) \times \cdots \times (n-k+1) \]

\[ \begin{aligned} &n \times (n-1) \times (n-2) \times \cdots \times (n-k+1) \\ \\ =& \frac{n \times (n-1) \times (n-2) \times \cdots \times (n-k+1)}{1} \\ \\ =& \frac{n \times (n-1) \times (n-2) \times \cdots \times (n-k+1) \times (n-k) \times (n-k-1) \times \cdots \times 2 \times 1}{(n-k) \times (n-k-1) \times \cdots \times 2 \times 1} \\ \\ =& \frac{n!}{(n-k)!} \\ \end{aligned} \]

\(0!=1\)

\(a^0=1\)

Exercise

Suppose your music collection include

• \(n_1\) pop songs
• \(n_2\) rock songs
• \(n_3\) country songs

In how many ways can you arrange your music, so that each genre is contiguous?

Exercise (cont’d)

• Now you are making a playlist.
• You pick \(k_i\) out of the \(n_i\) songs of genre \(i\;(= 1, 2, 3)\), where \(k_i = 0, 1, \cdots, n_i\).
• How many playlists are possible, so that each genre is contiguous?