Combinatorics • Topic 3

Permutations

A permutation is an ordered arrangement of objects. The order matters: $(1, 2)$ is different from $(2, 1)$ .

Linear Permutations

Arranging

n

distinct objects in a row.

Theorem

The number of ways to arrange

n

distinct objects is

n!

(n-factorial).

n! = n \times (n - 1) \times \dots \times 2 \times 1

Arranging

r

objects chosen from a set of

n

distinct objects (

n P r

P (n, r) = \frac{n !}{( n - r )!} = n (n - 1) \dots (n - r + 1)

If some objects are identical, we divide out the overcounting. If we have

n

objects where

n_{1}

are type A,

n_{2}

are type B, etc.:

Theorem (Multinomial Coefficient)

Arrangements = \frac{n !}{n _{1} ! n _{2} ! \dots n _{k} !}

where

\sum n_{i} = n

Example (Mississippi)

How many ways to arrange "MISSISSIPPI"? Total letters: 11. M: 1, I: 4, S: 4, P: 2.

\frac{11 !}{1 ! 4 ! 4 ! 2 !} = 34, 650

Arranging

n

distinct objects in a circle. Since rotations are considered identical, we fix one object to break the symmetry.

Theorem

Number of circular arrangements of

n

objects is

(n - 1)!

(Note: If flipping the circle is allowed—like a bracelet—divide by 2).

Exercise (Problem 1)

How many ways can 5 boys and 5 girls sit in a row if they must alternate genders?

Exercise (Problem 2)

In how many ways can 6 people sit around a round table if Alice and Bob refuse to sit next to each other?

Exercise (Problem 3)

Find the number of permutations of

{1, 2, 3, 4, 5}

such that 1 comes before 2, and 2 comes before 3.