PROB & STATS · HIGHER LEVEL
Permutations
Counting arrangements: AND, OR, factorials, and putting things together (or not).
Section 1 of 13
Counting with AND
I can go for tea in $3$ ways.
I can go to a game in $2$ ways.
How many ways can I have tea and go to the game?
Tree diagram
Each branch = one possible choice. Follow a path from left to right to make one full outcome.
Tea $\to$ Game
T $\to$ L, T $\to$ R
C $\to$ L, C $\to$ R
F $\to$ L, F $\to$ R
T $\to$ L, T $\to$ R
C $\to$ L, C $\to$ R
F $\to$ L, F $\to$ R
Sample space
Write out all the possible answers:
TL CL FL
TR CR FR
TR CR FR
That's $6$ outcomes — and notice $3 \times 2 = 6$.
Order is really important. TL and LT mean different things — tea-then-Liverpool isn't Liverpool-then-tea.
Must learn
★AND = Multiply. If one task can be done in $p$ ways and another in $q$ ways, then both (AND) can be done in $p \times q$ ways.
(i) How many ways can $6$ dogs finish a race?
Could finish first? Did finish first? — there are $6$ dogs that could come first, but only $1$ does. Then $5$ could come second, and so on.
$\underline{6} \times \underline{5} \times \underline{4} \times \underline{3} \times \underline{2} \times \underline{1}$
$= 720$ ways
TRY-ME · Q1
How many ways can $4$ girls stand in a line?
Four positions in the line. How many girls can take position 1? Then position 2? Multiply.
$\underline{4} \times \underline{3} \times \underline{2} \times \underline{1}$
$= 24$ ways
$24$ ways
TRY-ME · Q2
How many ways can $5$ friends sit in $5$ seats?
Same as the dogs — five positions, fill them one by one.
$\underline{5} \times \underline{4} \times \underline{3} \times \underline{2} \times \underline{1}$
$= 120$ ways
$120$ ways
TRY-ME · Q3
How many ways can $7$ books be arranged on a shelf?
Seven positions. Multiply $7$ down to $1$.
$\underline{7} \times \underline{6} \times \underline{5} \times \underline{4} \times \underline{3} \times \underline{2} \times \underline{1}$
$= 5040$ ways
$5040$ ways
Section 2 of 13
Counting with OR
Same situation: tea in $3$ ways, game in $2$ ways.
But now ask: how many ways can I have tea or go to the game?
The sample space is just the list of all single choices:
T, C, F, L, R
That's $5$ outcomes — and notice $3 + 2 = 5$.
Must learn
★OR = Add. If one task can be done in $p$ ways and another in $q$ ways, then one or the other (OR) can be done in $p + q$ ways.
Two rules. Keep them clean: AND multiplies, OR adds. Every counting problem from here on uses one or both.
TRY-ME · Q4
A menu has $4$ starters, $6$ mains and $3$ desserts. How many ways to choose one full meal (starter and main and dessert)?
"And" three times — multiply.
$4 \times 6 \times 3$
$= 72$ meals
$72$ meals
TRY-ME · Q5
A shop sells $5$ types of crisps or $8$ types of chocolate bar. How many single-item snack choices?
"Or" — add.
$5 + 8$
$= 13$ choices
$13$ choices
Section 3 of 13
The factorial $n!$
We just did $8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1$ — and there's a shorthand for "multiply $n$ down to $1$":
$8! \;=\; 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 \;=\; 40320$
Read $8!$ as "$8$ factorial".
Must learn — factorial
★For $n \in \mathbb{N}$: $n! = n(n-1)(n-2)\cdots(3)(2)(1)$
★By convention $0! = 1$ and $1! = 1$.
(i) Compute $5!$
$5! \;=\; 5 \times 4 \times 3 \times 2 \times 1$
$= 120$
(ii) Compute $6!$
$6! \;=\; 6 \times 5 \times 4 \times 3 \times 2 \times 1$
$= 720$
Notice $6! = 6 \times 5! = 6 \times 120 = 720$. Each factorial is the next-bigger one's stepping stone.
TRY-ME · Q6
Compute $4!$ and $7!$.
For $4!$, multiply $4 \times 3 \times 2 \times 1$. For $7!$, you can use $7 \times 6!$ if it's quicker.
$4! = 4 \times 3 \times 2 \times 1 = 24$
$7! = 7 \times 6! = 7 \times 720 = 5040$
$4! = 24$, $7! = 5040$
$4! = 24$, $7! = 5040$
TRY-ME · Q7
Without a calculator, which is bigger: $10!$ or $3 \times 9!$?
Rewrite $10!$ as $10 \times 9!$ and compare.
$10! = 10 \times 9!$
$3 \times 9! = 3 \times 9!$
$10 \times 9! > 3 \times 9!$
$10!$ is bigger
$10!$ is bigger
Section 4 of 13
Break the bigger one down
When you see a fraction like $\dfrac{20!}{18!}$, your calculator won't do it as a button-press — and you don't want to multiply out $20!$. So we use a trick.
Must learn
★Break the bigger one down until the smaller factorial appears, then cancel.
(i) Evaluate $\dfrac{20!}{18!}$
$\dfrac{20!}{18!} \;=\; \dfrac{20 \cdot 19 \cdot 18!}{18!}$
$\;=\; 20 \cdot 19$
$\;=\; 380$
(ii) Evaluate $\dfrac{50!}{48!}$
$\dfrac{50!}{48!} \;=\; \dfrac{50 \cdot 49 \cdot 48!}{48!}$
$\;=\; 50 \cdot 49$
$\;=\; 2450$
Only break down as far as you need to. Two steps down was enough — don't keep going to $47!$, $46!$ etc.
TRY-ME · Q8
Evaluate $\dfrac{12!}{10!}$.
Break $12!$ down two steps until $10!$ appears.
$\dfrac{12!}{10!} = \dfrac{12 \cdot 11 \cdot 10!}{10!}$
$= 12 \cdot 11$
$= 132$
$132$
TRY-ME · Q9
Evaluate $\dfrac{100!}{98!}$.
Don't panic at the big numbers — break $100!$ down two steps only.
$\dfrac{100!}{98!} = \dfrac{100 \cdot 99 \cdot 98!}{98!}$
$= 100 \cdot 99$
$= 9900$
$9900$
TRY-ME · Q10
Evaluate $\dfrac{8!}{5!\,3!}$.
Break $8!$ down to $5!$ so the $5!$ on top cancels with the $5!$ on bottom. Then evaluate $3!$ on the bottom.
$\dfrac{8!}{5!\,3!} = \dfrac{8 \cdot 7 \cdot 6 \cdot 5!}{5! \cdot 3!}$
$= \dfrac{8 \cdot 7 \cdot 6}{6}$
$= 56$
$56$
Section 5 of 13
Find factors of $\ldots$
Same trick — break the bigger one down — but now with $n$'s in it. Think of factoring $ax + ay = a(x+y)$: get a common factor out the front.
(i) Factorise $(n+1)! + n!$
Break $(n+1)!$ down one step: $(n+1)! = (n+1) \cdot n!$. Now both terms have an $n!$.
$(n+1)! + n!$
$\;=\; (n+1) \cdot n! + n!$
$\;=\; n!\bigl[(n+1) + 1\bigr]$
$\;=\; n!\,(n+2)$
(ii) Factorise $(2n+1)! + (2n-1)!$
The smaller factorial here is $(2n-1)!$. Break $(2n+1)!$ down two steps so $(2n-1)!$ appears.
$(2n+1)! + (2n-1)!$
$\;=\; (2n+1)(2n)(2n-1)! + (2n-1)!$
$\;=\; (2n-1)!\bigl[(2n+1)(2n) + 1\bigr]$
$\;=\; (2n-1)!\bigl[4n^2 + 2n + 1\bigr]$
Quick check on the breakdown: $100 = 100$, $99 \cdot 100 \cdot 98! \ldots$ — actually, the safety check is $(2n+1)(2n) = 4n^2 + 2n$. Tick. Add the $+1$ from the second term: $4n^2 + 2n + 1$. Tick.
TRY-ME · Q11
Factorise $(n+2)! + (n+1)!$.
The smaller factorial is $(n+1)!$. Break $(n+2)!$ down one step.
$(n+2)! + (n+1)!$
$= (n+2)(n+1)! + (n+1)!$
$= (n+1)!\bigl[(n+2) + 1\bigr]$
$= (n+1)!\,(n+3)$
$(n+1)!\,(n+3)$
TRY-ME · Q12
Factorise $(n+1)! - n!$.
Same shape as the worked example — but watch the sign in the bracket.
$(n+1)! - n!$
$= (n+1) \cdot n! - n!$
$= n!\bigl[(n+1) - 1\bigr]$
$= n!\,(n) = n \cdot n!$
$n \cdot n!$
TRY-ME · Q13
Factorise $(2n)! + (2n-2)!$.
Smaller factorial is $(2n-2)!$. Break $(2n)!$ down two steps until $(2n-2)!$ appears.
$(2n)! + (2n-2)!$
$= (2n)(2n-1)(2n-2)! + (2n-2)!$
$= (2n-2)!\bigl[(2n)(2n-1) + 1\bigr]$
$= (2n-2)!\bigl[4n^2 - 2n + 1\bigr]$
$(2n-2)!\,(4n^2 - 2n + 1)$
Section 6 of 13
Picking a few from many
Sometimes you don't fill all positions — just the first few. Same idea: count what can go in each slot, then multiply.
(i) How many ways can the first $3$ places in a $6$-dog race be filled?
Six dogs could come first, $5$ could come second, $4$ could come third. Stop there — we only care about the top $3$.
$\underline{6} \times \underline{5} \times \underline{4}$
$= 120$ ways
(ii) How many $3$-digit numbers from $\{2,3,4,5,6,7,8\}$, each digit used only once?
Three slots, seven digits available, no repeats.
$\underline{7} \times \underline{6} \times \underline{5}$
$= 210$ numbers
TRY-ME · Q14
How many ways can the top $4$ finishers be chosen from $8$ runners?
Four slots: $1$st, $2$nd, $3$rd, $4$th. Eight runners for the first slot, then $7$, $6$, $5$.
$\underline{8} \times \underline{7} \times \underline{6} \times \underline{5}$
$= 1680$ ways
$1680$ ways
TRY-ME · Q15
How many $2$-digit numbers can be formed from $\{1,2,3,4,5,6,7,8,9\}$, each digit used only once?
Two slots, nine digits.
$\underline{9} \times \underline{8}$
$= 72$ numbers
$72$ numbers
TRY-ME · Q16
How many $3$-letter "words" (any letter combo, no real words needed) can be made from the $26$ letters of the alphabet if no letter repeats?
Three slots, $26$ then $25$ then $24$.
$\underline{26} \times \underline{25} \times \underline{24}$
$= 15{,}600$ words
$15{,}600$ words
Section 7 of 13
Odd, over $700$, both
Same set of digits $\{2,3,4,5,6,7,8\}$, $3$-digit numbers, no repeats. Now we add a condition.
Must learn
★Fill the restricted slot(s) first. Whatever the rule controls — first digit, last digit, particular seat — count that one first, then the rest.
(i) How many of these $3$-digit numbers are odd?
"Odd" restricts the last digit — it has to be one of $\{3,5,7\}$. So fill the last slot first.
$\underline{6} \times \underline{5} \times \underline{3}$ (last digit = odd)
$= 90$ odd numbers
Once $3$ digits are used in the units column, $6$ digits remain for the hundreds, then $5$ for the tens.
(ii) How many are over $700$?
"Over $700$" restricts the first digit — it must be $7$ or $8$. So fill the first slot first.
$\underline{2} \times \underline{6} \times \underline{5}$ (first digit $\in \{7,8\}$)
$= 60$ numbers
(iii) How many are over $700$ and odd?
Now two slots are restricted — first must be $\{7,8\}$, last must be $\{3,5,7\}$. These overlap on $7$, so we have to split into cases.
Case A: first digit is $7$.
Last digit must be odd, but $7$ is already used — so last $\in \{3,5\}$, giving $2$ choices. Middle is any of the $5$ remaining.
$\underline{1}_{(7)} \times \underline{5} \times \underline{2}_{(3,5)} \;=\; 10$
Case B: first digit is $8$.
Last digit is odd, $7$ still available — so last $\in \{3,5,7\}$, giving $3$ choices. Middle is any of the $5$ remaining.
$\underline{1}_{(8)} \times \underline{5} \times \underline{3}_{(3,5,7)} \;=\; 15$
Case A or Case B — so we add.
$10 + 15 \;=\; 25$ numbers
Watch out — don't just do $\underline{2} \times \underline{5} \times \underline{3} = 30$. That over-counts because when first $= 7$, only $2$ odd endings remain (not $3$).
(iv) How many numbers over $400$ can be formed from $\{2,3,4,5\}$, each digit used only once?
Trick question — "a number over $400$" could be a $4$-digit number too, not just $3$-digit. We need both cases.
Case A: $3$-digit, first digit $\in \{4,5\}$.
$\underline{2} \times \underline{3} \times \underline{2} \;=\; 12$
Case B: $4$-digit (every such number is automatically over $400$).
$\underline{4} \times \underline{3} \times \underline{2} \times \underline{1} \;=\; 24$
Total $= 12 + 24 = 36$
TRY-ME · Q17
From $\{1,2,3,4,5,6\}$, no repeats. How many $3$-digit numbers are even?
"Even" restricts the last digit. Even choices: $\{2,4,6\}$ — three options. Fill that slot first.
Last digit: $3$ choices $\{2,4,6\}$.
$\underline{5} \times \underline{4} \times \underline{3}$ (last fixed first)
$= 60$ even numbers
$60$ even numbers
TRY-ME · Q18
From $\{1,2,3,4,5,6\}$, no repeats. How many $3$-digit numbers are over $500$ and even?
Split cases by the first digit. First $\in \{5,6\}$ but $6$ is even — that overlaps with the "even last digit" condition. Case-split.
Case A: first $= 5$. Last $\in \{2,4,6\}$ → $3$ choices. Middle = $4$ left.
$1 \times 4 \times 3 = 12$
Case B: first $= 6$. Last $\in \{2,4\}$ → $2$ choices (6 used). Middle = $4$ left.
$1 \times 4 \times 2 = 8$
Total $= 12 + 8 = 20$
$20$ numbers
TRY-ME · Q19
From $\{0,1,2,3,4,5\}$, no repeats. How many $3$-digit numbers can be formed? (A number can't start with $0$.)
The first slot is restricted: $5$ choices (no $0$). The remaining two slots can use anything left — including $0$.
First digit: $\{1,2,3,4,5\}$ → $5$ choices.
$\underline{5} \times \underline{5} \times \underline{4}$ (after first, $5$ left including $0$)
$= 100$ numbers
$100$ numbers
Section 8 of 13
Codes — same digit can repeat
Up to now we've used each digit once — like a race, where the same dog can't come first and third. But a PIN code or password can repeat. The slots don't talk to each other.
(i) How many $3$-digit codes can be formed from $\{2,3,4,5,6\}$ if digits can repeat?
$\underline{5} \times \underline{5} \times \underline{5}$ (each slot has all 5 available)
$= 125$ codes
Compare with "each digit used only once": $5 \times 4 \times 3 = 60$. Repetition more than doubles the count here.
(ii) How many $3$-digit codes can be formed from digits $0$–$9$? (Standard phone-style code.)
$\underline{10} \times \underline{10} \times \underline{10}$
$= 1000$ codes
That's $000$ through $999$ — exactly $1000$, as expected.
(iii) Same — but the code can't start with $0$.
$10 \times 10 \times 10$ no — first slot only has $9$ choices
$\underline{9} \times \underline{10} \times \underline{10}$
$= 900$ codes
(iv) $3$-digit codes from $0$–$9$, no digit repeats, can't start with $0$.
Two rules — but fill the restricted slot first. First slot: $9$ choices. Then $9$ left (including $0$ now). Then $8$.
$\underline{9} \times \underline{9} \times \underline{8}$
$= 648$ codes
TRY-ME · Q20
How many $4$-character passcodes can be made from $\{A,B,C,D,E\}$ if letters can repeat?
Four slots, $5$ choices each, independent.
$5 \times 5 \times 5 \times 5 = 5^4$
$= 625$ codes
$625$ codes
TRY-ME · Q21
A $4$-digit PIN uses digits $0$–$9$ with repetition allowed. How many start with an odd digit and end with an even digit?
First slot: $5$ odd digits $\{1,3,5,7,9\}$. Last slot: $5$ even digits $\{0,2,4,6,8\}$. Middle two slots: $10$ each (repetition allowed).
$\underline{5}_{(\text{odd})} \times \underline{10} \times \underline{10} \times \underline{5}_{(\text{even})}$
$= 2500$ PINs
$2500$ PINs
TRY-ME · Q22
A car registration is $3$ letters followed by $4$ digits. Letters and digits can both repeat. How many registrations?
$26$ letters, $10$ digits, multiply across all $7$ slots.
$26 \times 26 \times 26 \times 10 \times 10 \times 10 \times 10$
$= 26^3 \times 10^4$
$= 175{,}760{,}000$ registrations
$26^3 \times 10^4 = 175{,}760{,}000$
Section 9 of 13
Permutations the formal way
All those "fill the slots" problems with no repetition have a name and a formula. Arranging $r$ objects chosen from $n$ — each used only once — is a permutation, written $\,^nP_r$.
Must learn — permutations
★If we have $n$ objects to arrange $r$ at a time (where $r \le n$, $r,n \in \mathbb{N}$), each used only once:
★$\,^nP_r = \dfrac{n!}{(n-r)!}$
(i) Use the formula on the dog race
First $3$ places, $6$ dogs: $n = 6$, $r = 3$.
$\,^{6}P_{3} \;=\; \dfrac{6!}{(6-3)!} \;=\; \dfrac{6!}{3!}$
$\;=\; \dfrac{6 \cdot 5 \cdot 4 \cdot 3!}{3!}$
$\;=\; 6 \cdot 5 \cdot 4 \;=\; 120$ ✓
Same answer as the slot method — good. The formula is the slot method, just packaged.
(ii) Use the formula: $3$-digit numbers from $\{2,3,4,5,6\}$, each digit once
$n = 5$, $r = 3$.
$\,^{5}P_{3} \;=\; \dfrac{5!}{(5-3)!} \;=\; \dfrac{5!}{2!}$
$\;=\; \dfrac{5 \cdot 4 \cdot 3 \cdot 2!}{2!}$
$\;=\; 60$ numbers
TRY-ME · Q23
Evaluate $\,^{8}P_{2}$ using the formula.
$n = 8$, $r = 2$, so $\dfrac{8!}{6!}$. Break the top down to $6!$.
$\,^{8}P_{2} = \dfrac{8!}{6!} = \dfrac{8 \cdot 7 \cdot 6!}{6!}$
$= 8 \cdot 7 = 56$
$56$
TRY-ME · Q24
Evaluate $\,^{7}P_{4}$.
$\dfrac{7!}{3!}$. Break the top down four steps.
$\,^{7}P_{4} = \dfrac{7!}{3!} = \dfrac{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3!}{3!}$
$= 7 \cdot 6 \cdot 5 \cdot 4 = 840$
$840$
Section 10 of 13
Going backwards — find $n$
Given the value of $\,^nP_r$ and $r$, find $n$. We use the formula, break the factorial down, and solve the quadratic that appears.
(i) Given $\,^{n}P_{2} = 20$, find $n$.
$\,^{n}P_{2} \;=\; \dfrac{n!}{(n-2)!} \;=\; 20$
Break $n!$ down two steps to expose $(n-2)!$.
$\dfrac{n(n-1)(n-2)!}{(n-2)!} \;=\; 20$
$n(n-1) \;=\; 20$
$n^2 - n \;=\; 20$
$n^2 - n - 20 \;=\; 0$
$(n-5)(n+4) \;=\; 0$
$n = 5$ or $n = -4$
Reject $n = -4$ — we need $n \in \mathbb{N}$ (you can't arrange $-4$ objects).
$n = 5$
TRY-ME · Q25
Solve $\,^{n}P_{2} = 30$ for $n \in \mathbb{N}$.
$n(n-1) = 30$. Form a quadratic and factorise.
$\dfrac{n!}{(n-2)!} = n(n-1) = 30$
$n^2 - n - 30 = 0$
$(n-6)(n+5) = 0$
$n = 6$ (reject $-5$)
$n = 6$
$n = 6$
TRY-ME · Q26
Solve $\,^{n}P_{3} = 60$ for $n \in \mathbb{N}$.
$n(n-1)(n-2) = 60$. You're looking for three consecutive integers that multiply to $60$. Guess and check is fine here.
$\dfrac{n!}{(n-3)!} = n(n-1)(n-2) = 60$
Try $n=5$: $5 \cdot 4 \cdot 3 = 60$. ✓
$n = 5$
$n = 5$
Section 11 of 13
When things must stay together
A new flavour of question. How many ways can $5$ boys stand in a line — given $2$ of them are twins who must always be together?
First, no condition: $5! = 120$ arrangements.
With the twins glued together, think of them as one bubble. Inside the bubble they can swap places (AB or BA = $2!$ orderings).
$\bigl(\,\boxed{AB}\,\bigr) \quad \boxed{C} \quad \boxed{D} \quad \boxed{E}$ 4 bubbles
Must learn
★Together = bubbles. Glue the "together" people into one bubble. Arrange the bubbles. Then multiply by the internal arrangements within each bubble.
(i) $5$ boys in a line, twins always together
$\underbrace{4!}_{\text{bubbles}} \times \underbrace{2!}_{\text{inside AB}}$
$\;=\; 24 \times 2$
$\;=\; 48$ ways
(ii) $a, b, c, d, e$ — how many arrangements have $a, b, c$ all together?
Now the bubble is size $3$: $\bigl(\boxed{abc}\bigr)\,\boxed{d}\,\boxed{e}$ — three bubbles in total. Inside the $abc$ bubble: $3!$ orderings.
$\underbrace{3!}_{\text{bubbles}} \times \underbrace{3!}_{\text{inside abc}}$
$\;=\; 6 \times 6$
$\;=\; 36$ ways
TRY-ME · Q27
How many ways can $6$ people sit in a row if two particular people, P and Q, must sit together?
PQ as one bubble + the other $4$ people = $5$ bubbles. Multiply by $2!$ for the bubble's internal ordering.
$5! \times 2!$
$= 120 \times 2$
$= 240$ ways
$240$ ways
TRY-ME · Q28
$7$ books on a shelf — $3$ are maths books and must be kept together. How many arrangements?
Maths bubble + $4$ other books = $5$ bubbles. Inside the maths bubble: $3!$.
$5! \times 3!$
$= 120 \times 6$
$= 720$ arrangements
$720$ arrangements
TRY-ME · Q29
$8$ people in a row — $2$ specific people A and B must sit together AND $2$ others C and D must also sit together (the two pairs separate from each other are fine).
Two bubbles: AB and CD. Plus the other $4$ people. Total $6$ bubbles. Each pair-bubble has $2!$ inside.
$6! \times 2! \times 2!$
$= 720 \times 2 \times 2$
$= 2880$ arrangements
$2880$ arrangements
Section 12 of 13
The "subtract from total" trick
If "together" is hard to count by direct slotting, the easiest way to count "not together" is to count everything, then take away the "together" cases.
Must learn
★Not together $=$ Total $-$ Together.
(i) $5$ boys in a line — twins never together
Total $\;=\; 5! \;=\; 120$
Together $\;=\; 4! \times 2! \;=\; 48$
Not together $\;=\; 120 - 48$
$\;=\; 72$ ways
(ii) Arrangements of $a,b,c,d,e$ where $a,b,c$ are not all together
Total $\;=\; 5! \;=\; 120$
Together $\;=\; 3! \times 3! \;=\; 36$
Not together $\;=\; 120 - 36$
$\;=\; 84$ ways
"Not all together" means it's fine if two of them sit beside each other, just not all three in a single block. The subtraction handles that perfectly.
TRY-ME · Q30
$6$ people in a row. How many ways can they sit if P and Q are not sitting together?
Total $= 6!$. Together $= 5! \times 2!$. Subtract.
Total $= 6! = 720$
Together $= 5! \times 2! = 240$
Not together $= 720 - 240$
$= 480$ ways
$480$ ways
TRY-ME · Q31
$7$ books on a shelf — $3$ are maths books. In how many arrangements are the $3$ maths books not all together?
Total $= 7!$. Together $= 5! \times 3!$ (from previous try-me). Subtract.
Total $= 7! = 5040$
Together $= 5! \times 3! = 720$
Not together $= 5040 - 720$
$= 4320$ arrangements
$4320$ arrangements
Section 13 of 13
Repeated letters — divide it out
When two of the things being arranged are indistinguishable, the $n!$ count over-counts. Example: how many $3$-letter words from $a, b, b$ — each letter used only once?
If the two $b$'s were distinct ($b_1$ and $b_2$), there'd be $3! = 6$ arrangements:
$a\,b_1\,b_2, \quad a\,b_2\,b_1, \quad b_1\,a\,b_2, \quad b_2\,a\,b_1, \quad b_1\,b_2\,a, \quad b_2\,b_1\,a$
But $b_1$ and $b_2$ are identical, so each pair above is really the same word. We've double-counted by a factor of $2! = 2$.
$\dfrac{3!}{2!} \;=\; \dfrac{6}{2} \;=\; 3$ true count: abb, bab, bba
Must learn
★If $n$ objects are arranged where $k$ of them are identical: divide by $k!$.
★More generally, if there are $k_1$ of one type, $k_2$ of another, etc., divide by $k_1!\,k_2!\,\cdots$
(i) $4$-letter words from $a, b, b, b$
$\dfrac{4!}{3!} \;=\; \dfrac{24}{6}$
$\;=\; 4$ words
The four words: abbb, babb, bbab, bbba.
(ii) $4$-letter words from the letters of $\text{ABBA}$
Two A's and two B's — divide by $2!$ for the A's and $2!$ for the B's.
$\dfrac{4!}{2!\,2!} \;=\; \dfrac{24}{4}$
$\;=\; 6$ words
(iii) Number of arrangements of the letters of $\text{MISSISSIPPI}$
$11$ letters total. Counts: M$\,=1$, I$\,=4$, S$\,=4$, P$\,=2$.
$\dfrac{11!}{1!\,4!\,4!\,2!}$
$= \dfrac{39{,}916{,}800}{1 \cdot 24 \cdot 24 \cdot 2}$
$= 34{,}650$ arrangements
TRY-ME · Q32
How many arrangements of the letters of $\text{BANANA}$?
$6$ letters total. B$\,=1$, A$\,=3$, N$\,=2$. Divide $6!$ by $3!\,2!$.
$\dfrac{6!}{3!\,2!} = \dfrac{720}{6 \cdot 2}$
$= 60$ arrangements
$60$ arrangements
TRY-ME · Q33
How many arrangements of the letters of $\text{STATISTICS}$?
$10$ letters total. Counts: S$\,=3$, T$\,=3$, A$\,=1$, I$\,=2$, C$\,=1$. Divide $10!$ by $3!\,3!\,2!$.
$\dfrac{10!}{3!\,3!\,2!} = \dfrac{3{,}628{,}800}{6 \cdot 6 \cdot 2}$
$= 50{,}400$ arrangements
$50{,}400$ arrangements
TRY-ME · Q34
How many arrangements of the letters of $\text{MATHSLIVE}$?
Check for repeated letters — there are none. So just $9!$.
All 9 letters distinct.
$9!$
$= 362{,}880$ arrangements
$362{,}880$ arrangements
End of Permutations
You've covered AND/OR, factorials, restrictions, codes, $^nP_r$, together-and-not-together, and identical objects. Next up: combinations.