Permutation
See how to solve a permutation nPr
(+ permutation with repetition, circular permutation, bracelet permutation).
8 examples and their solutions.
Permutation
Formula
r numbers nPr = n⋅(n - 1)⋅(n - 2)⋅ ...
nPr: Starting from n, multiply r numbers. Meaning: From n things,
pick & arrange r things.
Combination (Math)
nPn = n! - [1]
nP1 = n - [2]
nP0 = 1 - [3]
nP1 = n - [2]
nP0 = 1 - [3]
[1]
[2]
Starting from n, multiply 1 number.
→ n
→ n
[3]
From n things, pick & arrange 0 things.
→ Don't do anything.
→ 1 way
→ Don't do anything.
→ 1 way
Example
6P4
Solution 6P4
= 6⋅5⋅4⋅3 - [1]
= 30⋅12
= 360
= 6⋅5⋅4⋅3 - [1]
= 30⋅12
= 360
[1]
Starting from 6, multiply 4 numbers.
Close
Example
9 students
Find the number of ways to choose 3 students and arrange them in a row.
Solution Find the number of ways to choose 3 students and arrange them in a row.
9P3 - [1]
= 9⋅8⋅7 - [2]
= 72⋅7
= 504
= 9⋅8⋅7 - [2]
= 72⋅7
= 504
[1]
From 9 students,
pick & arrange 3 students.
→ 9P3
pick & arrange 3 students.
→ 9P3
[2]
Starting from 9, multiply 3 numbers.
Close
Example
Numbers: 1, 2, 3, 4, 5, 6, 7, 8
By using the numbers once,
find the number of ways to make a 4-digit number.
Solution By using the numbers once,
find the number of ways to make a 4-digit number.
8P4 - [1]
= 8⋅7⋅6⋅5 - [2]
= 56⋅30
= 1680
= 8⋅7⋅6⋅5 - [2]
= 56⋅30
= 1680
[1]
From 8 numbers,
pick & arrange 4 numbers.
→ 8P4
pick & arrange 4 numbers.
→ 8P4
[2]
Starting from 8, multiply 4 numbers.
Close
Example
Numbers: 0, 1, 2, 3, 4, 5
By using the numbers once,
find the number of ways to make a 3-digit number.
Solution By using the numbers once,
find the number of ways to make a 3-digit number.
- 0
6P3 - 5P2 - [1]
= 6⋅5⋅4 - 5⋅4 - [2]
= 30⋅4 - 20
= 120 - 20
= 100
6P3 - 5P2 - [1]
= 6⋅5⋅4 - 5⋅4 - [2]
= 30⋅4 - 20
= 120 - 20
= 100
[1]
6 numbers
Make a 3-digit number.
→ From 6 numbers,
pick & arrange 3 numbers.
→ 6P3
- 0
But, if the hundredth number is 0,
it's not a 3-digit number.
(012, 023, ...)
So subtract these number of ways.
→ From 5 numbers (1, 2, 3, 4, 5),
pick & arrange 2 numbers.
→ 5P2
[2]
6P3
Starting from 6, multiply 3 numbers.
5P2
Starting from 5, multiply 2 numbers.
Starting from 6, multiply 3 numbers.
5P2
Starting from 5, multiply 2 numbers.
Close
Permutation with Repetition
Formula
N = n!p!⋅q!⋅r!⋅...
n = p + q + r + ... p, q, r: Numbers of identical things
Example
Letters: a, a, a, b, b, c, c
By using each letter once,
find the number of ways to make a 7-letter word.
Solution By using each letter once,
find the number of ways to make a 7-letter word.
n = 7
a: 3
b: 2
c: 2
N = 7!3!⋅2!⋅2!
= 7⋅6⋅5⋅4⋅3!3!⋅2⋅1⋅2⋅1 - [1]
= 7⋅6⋅5
= 7⋅30
= 210
a: 3
b: 2
c: 2
N = 7!3!⋅2!⋅2!
= 7⋅6⋅5⋅4⋅3!3!⋅2⋅1⋅2⋅1 - [1]
= 7⋅6⋅5
= 7⋅30
= 210
[1]
Close
Example
Find the number of shortest paths to move from A to B.
Solution →: 3
↓: 3 - [1]
n = 6
N = 6!3!⋅3!
= 6⋅5⋅4⋅3!3!⋅3⋅2⋅1
= 5⋅4
= 20
↓: 3 - [1]
n = 6
N = 6!3!⋅3!
= 6⋅5⋅4⋅3!3!⋅3⋅2⋅1
= 5⋅4
= 20
[1]
To make the shortest path,
you should move either → or ↓.
Width: 3 blocks
Height: 3 blocks
→ Pick & arrange →, →, →, ↓, ↓, ↓.
you should move either → or ↓.
Width: 3 blocks
Height: 3 blocks
→ Pick & arrange →, →, →, ↓, ↓, ↓.
Close
Circular Permutation
Definition
when arranging things in a circle.
These two cases are the same case
because when you rotate the left case ↷,
you can get the right case.
Formula
N = (n - 1)!
Example
5 students
Find the number of ways to make them sit at a round table.
Solution Find the number of ways to make them sit at a round table.
n = 5
N = 4! - [1]
= 4⋅3⋅2⋅1 - [2]
= 12⋅2
= 24
N = 4! - [1]
= 4⋅3⋅2⋅1 - [2]
= 12⋅2
= 24
[1]
Sitting in a round table
→ Circular permutation
→ Circular permutation
[2]
Close
Bracelet Permutation
Definition
when arranging things in a bracelet (or a necklace).
These two cases are the same case
because when you flip the left case,
you can get the right case.
Formula
N = (n - 1)!2
Example
7 beads
Find the number of ways to make a bracelet by using these beads.
Solution Find the number of ways to make a bracelet by using these beads.
n = 7
N = 6!2 - [1]
= 6⋅5⋅4⋅3⋅2⋅12 - [2]
= 6⋅5⋅4⋅3
= 30⋅12
= 360
N = 6!2 - [1]
= 6⋅5⋅4⋅3⋅2⋅12 - [2]
= 6⋅5⋅4⋅3
= 30⋅12
= 360
[1]
Making a bracelet
→ Bracelet permutation
→ Bracelet permutation
[2]
Close