Notes: Permutations and combinations

The multiplication principle

Suppose we can break an event

{E}

up into two steps: step 1 followed by step 2. If there are

{m}

ways for step 1 to occur and

{n}

ways for step 2, then the total number of ways for

{E}

to occur is

{m\times n.}

Example 1: (A) forming a number with repetition

How many ways are there to form a five-digit number satisfying the following conditions using only the numbers from 1,2,3,4,5,6,7. Repetitions are allowed.

(a) No restrictions.

(b) The number must be greater than 30,000.

(c) The number must be odd.

(d) The number must be greater than 30,000 and odd.

(a)

{7 \times 7 \times 7 \times 7 \times 7} = 7^5 = 16\,807.

(b)

{5 \times 7 \times 7 \times 7 \times 7} = {5 \times 7^4} = 12\,005.

(c)

{7 \times 7 \times 7 \times 7 \times 4} = {7^4 \times 4} = 9\,604.

(d)

{5 \times 7 \times 7 \times 7 \times 4} = {5 \times 7^3 \times 4} = 6\,860.

Rearrangements/permutations: the factorial

There are

{\boxed{n! \textrm{ ways}}}

to rearrange

{n}

unique items in a line.

The factorial of a positive integer

{n}

, denoted

{n!,}

is defined by

{n! = n(n-1)(n-2) \cdots (1).}

For example,

{4! = 4(3)(2)(1) = 24.}

The addition principle

Suppose we can break an event

{E}

up into two cases: case 1 or case 2 (with no overlap). If there are

{m}

ways for case 1 to occur and

{n}

ways for case 2, then the total number of ways for

{E}

to occur is

{m + n.}

Example 1: (B) forming a number by rearranging

How many ways are there to rearrange the five digits 1,2,3,4,5 to form a five-digit number satisfying the following conditions. Repetitions are not allowed.

(a) No restrictions.

(b) The number must be greater than 20,000.

(c) The number must be odd.

(d) The number must be greater than 20,000 and odd.

(a)

{5! = 120.}

(b)

{4 \times 4! = 96.}

(c)

{3 \times 4! = 72.}

(d) Case 1: Start with an odd number (3 or 5).
Number of ways

{= 2 \times 2 \times 3! = 24.}

Case 2: Start with an even number (2 or 4).
Number of ways

{= 2 \times 3 \times 3! = 36.}

Required number of ways

{=24 + 36 = 60.}

Choosing/combinations

There are

{\boxed{ {n \choose r} \textrm{ or } ^n\mkern{-1mu}C_r \textrm{ ways } }}

to select

{r}

items from

{n}

unique items. These items are unordered.

For an ordered selection, we have

{\boxed{ {n \choose r} \times r!, }}

also denoted as

{^n\mkern{-3mu}P_r.}

{n \choose r} = \frac{n!}{r!(n-r)!}

Example 1: (C) forming a number by choosing

How many ways are there to use the digits from 1,2,3,4,5,6,7 to form a five-digit number satisfying the following conditions. Repetitions are not allowed.

(a) No restrictions.

(b) The number must be greater than 30,000.

(c) The number must be odd.

(d) The number must be greater than 30,000 and odd.

(a)

{{7 \choose 5} \times 5! = 2520.}

(b)

{5 \times {6 \choose 4} \times 4! = 1800.}

(c)

{4 \times {6 \choose 4} \times 4! = 1440.}

(d) Case 1: Start with an odd number (3, 5 or 7).
Number of ways

{= 3 \times 3 \times {5 \choose 3} \times 3! = 540.}

Case 2: Start with an even number (4 or 6).
Number of ways

{= 2 \times 4 \times {5 \choose 3} \times 3! = 480.}

Required number of ways

{=480 + 540 = 1020.}

Example 2: forming groups

A group of students is to be chosen to represent three schools,

{A,B \textrm{ and } C.}

The group is to consist of

{10}

students, and is chosen from a set of

{15}

students consisting of

{2}

from

{A,}

{4}

from

{B,}

and

{9}

from

{C.}

Find the number of ways in which the group can be chosen if it includes

(a)

{1}

student from

{A,}

{3}

from

{B,}

and

{6}

from

{C,}

(b) students from

{B \textrm{ and } C}

only,

(c) at least

{8}

students from

{C,}

(d) at least

{1}

student from each school.

(a)

{{2 \choose 1} \times {4 \choose 3} \times {9 \choose 6} = 672.}

(b)

{{13 \choose 10} = 286.}

(c) Case 1: exactly 8 students from

{C:}

{{9 \choose 8} \times {6 \choose 2} = 135.}

Case 2: exactly 9 students from

{C:}

{{9 \choose 9} \times {6 \choose 1} = 6.}

Required number of ways

{=135 + 6 = 141.}

(d) We consider the complement, which involves some school not being represented.
Case 1:

{A}

not represented:

{{13 \choose 10} = 286.}

Case 1:

{B}

not represented:

{{11 \choose 10} = 11.}

Required number of ways

{= {15 \choose 10} - (286+11) = 2706.}

Grouping

{A \; B}

{C \; D \; E}

To rearrange

{A,B,C,D,E}

with

{A,B}

together, we group them together and treat it as if we have 4 items only. Subsequently we rearrange

{A,B}

among themselves. This gives us

{4! \times 2!}

Slotting

{\square \; C \; \square \; D \; \square \; E \; \square}

To rearrange

{A,B,C,D,E}

with

{A,B}

separated, we first rearrange

{C,D,E}

. Subsequently, we notice there are 4 "slots" that

{A,B}

can go in so we choose which of these slots are taken. Finally, we rearrange

{A,B.}

This gives us

{3! \times {4 \choose 2} \times 2! = 72}

Complement

Consider an event

{E.}

The complement ("opposite") of

{E}

is denoted as

{E'.}

Sometimes it is easier to count

{E'.}

In such cases we can obtain the number of ways for

{E}

by the formula

{\boxed{n(E)=n(\textrm{total})-n(E')}}

For example, to rearrange

{A,B,C,D,E}

with

{A,B}

separated, we can observe that the complement is if

{A,B}

are together. We thus can use the grouping and complement methods to get

{5! - (4! \times 2!) = 72}

Slotting vs complement

For the example of separating

{A,B}

on the previous slide, both the slotting and complement methods give the same answer: they describe the same situation after all.

Let us now consider three items

{A,B,C}

out of six

{A,B,C,D,E,F.}

The slotting method gives us

{3! \times {4 \choose 3} \times 3! = 144}

The complement method gives us

{6! - (4! \times 3!) = 576}

They are different because the slotting method gives us a situation where

{A,B,C}

are separated/not next to one another.
Meanwhile, the complement method gives us a situation where

{A,B,C}

are not all together. We cannot have all three of them together but two of them together is allowed (vs the slotting case where this is not allowed).

Alternating

{\boxdot \; D \; \boxdot \; E \; \boxdot \; F \; \boxdot}

: slotting

{{4 \choose 3}}

{\boxtimes \; D \; \boxtimes \; E \; \boxtimes \; F \phantom{\; \boxdot}}

: alternating 1

{\phantom{\square \;} D \; \boxtimes \; E \; \boxtimes \; F \; \boxtimes}

: alternating 2

For the slotting method, we have

{3! \times {4 \choose 3} \times 3!}

where

{{4 \choose 3}}

represents choosing 3 out of 4 possible slots for

{A,B,C.}

If we want

{A,B,C}

to alternate with

{D,E,F,}

we have a more restricted arrangement: either we start with one of

{A,B,C}

or one of

{D,E,F.}

Hence the number of ways to alternate them is given by

{3! \times 2 \times 3!}

Example 3: rearranging people (in a line)

A group of 6 people consists of 3 married couples. Find the number of different possible orders for the group to stand in a line if

(a) there are no restrictions,

(b) each married man stands next to his wife,

(c) the men and women alternate,

(d) each married man stands next to his wife and the men and women alternate.

(a)

{6! = 720.}

(b)

{3! \times 2! \times 2! \times 2! = 48.}

(c)

{3! \times 2 \times 3! = 72.}

(d)

{3! \times 2 = 12.}

Circular rearrangement

There are

{\boxed{(n-1)! \textrm{ ways}}}

to rearrange

{n}

unique items in a circle.

{\textrm{A}}

{\textrm{B}}

{\textrm{C}}

{\textrm{D}}

{\bigcirc}

{\textrm{D}}

{\textrm{A}}

{\textrm{B}}

{\textrm{C}}

{\bigcirc}

{\textrm{C}}

{\textrm{D}}

{\textrm{A}}

{\textrm{B}}

{\bigcirc}

{\textrm{B}}

{\textrm{C}}

{\textrm{D}}

{\textrm{A}}

{\bigcirc}

Example 3: (B) rearranging people (in a circle)

A group of 6 people consists of 3 married couples. Find the number of different possible orders for the group to stand in a circle if

(a) there are no restrictions,

(b) each married man stands next to his wife,

(c) the men and women alternate,

(d) each married man stands next to his wife and the men and women alternate.

(a)

{(6-1)! = 120.}

(b)

{(3-1)! \times 2! \times 2! \times 2! = 16.}

(c)

{(3-1)! \times 1 \times 3! = 12.}

(d)

{(3-1)! \times 2 = 4.}

Rearranging identical objects

There are

{\boxed{ \frac{n!}{r_1!r_2!\cdots r_k!} \textrm{ ways} }}

to rearrange

{n}

items in a line, where there are

{r_1}

identical items of type 1,

{r_2}

identical items of type 2, etc.

For example, there are

\frac{9!}{3!2!2!}

ways to rearrange

{AAABCCDEE}

in a line.
There are

\frac{(9-1)!}{3!2!2!}

ways to rearrange them in a circle.

Example 4: (A) rearranging identical objects

Find the number of ways in which the letters of the word

{SEQUENCE}

can be arranged if

(a) there are no restrictions,

(b)

{S}

and

{Q}

must not be next to one another,

(c) between any two

{E\textrm{s}}

there must be at least 2 other letters,

(a)

{\frac{8!}{3!} = 6720.}

(b)

{6720 - \frac{7!\times 2!}{3!} = 5040.}

(c) Case 1:

{\square E \square \square E \square \square E}

, case 2:

{E \square \square E \square \square E \square}

case 3:

{E \square \square \square E \square \square E}

, case 4:

{E \square \square E \square \square \square E}

Number of ways for each case

{= 5!}

Required number of ways

{=5! \times 4 = 480.}

Choosing identical objects

We will use cases to handle combinations of identical objects.

Example 4: (B) choosing identical objects

A "codeword" is to be formed using the letters of

{COMPOSITION}

. Find the number of possible "codeword"s that are made up of

(a) 3 letters,

(b) 4 letters.

(a) Case 1: no repeats

{(\alpha \beta \gamma)}

:

{{8 \choose 3} \times 3! = 336}

Case 2: repeats twice

{(\alpha \alpha \beta)}

:

{{2 \choose 1} \times {7 \choose 1} \times \frac{3!}{2!} = 42}

Case 3: repeats thrice

{(\alpha \alpha \alpha)}

:

{1}

Required number of ways

{336+42+1 = 379.}

(a) Case 1: no repeats

{(\alpha \beta \gamma \delta)}

:

{{8 \choose 4} \times 4! = 1680}

Case 2: one letter repeats twice

{(\alpha \alpha \beta \gamma)}

:

{{2 \choose 1} \times {7 \choose 2} \times \frac{4!}{2!} = 504}

Case 3: two letters repeats twice

{(\alpha \alpha \beta \beta)}

:

{{2 \choose 2} \times \frac{4!}{2!2!} = 6}

Case 4: repeats thrice

{(\alpha \alpha \alpha \beta)}

:

{1 \times {7 \choose 1} \times \frac{4!}{3!} = 28 }

Required number of ways

{1680+504+6+28 = 2218.}