Chapter 6 · Permutations and Combinations

6.1 The Fundamental Principle of Counting

If one job can be done in $m$ ways and, after it, a second job in $n$ ways, the two together can be done in $m\times n$ ways. This one principle counts PINs, number plates, outfits and routes without listing a single one of them.

Your UPI PIN has 4 digits. How many different PINs are possible? You could start listing them — 0000, 0001, 0002, … — but you would still be writing a week later. A 6-digit PIN is even worse. Yet the answers, $10\,000$ and $1\,000\,000$, take a few seconds to find once you see the pattern: each digit can be chosen in $10$ ways whatever the other digits are, so the choices multiply.

This chapter is about counting without listing. The whole subject rests on two simple rules. The multiplication principle (the fundamental principle of counting) handles jobs done in stages, one after another — "first this, and then that". The addition principle handles jobs that split into separate cases — "this way or that way". In this section we state both carefully, learn to draw the tree diagrams and "slots" that make them visible, and use them on digits, codes, routes and passwords. Sections 6.2 and 6.3 build permutations and combinations on top of them.

Counting by Listing — and Why It Stops Working

Start with a problem small enough to list. Riya has $3$ shirts — red, blue and white — and $2$ pairs of trousers — black and grey. How many different outfits (one shirt with one pair of trousers) can she wear?

A tree diagram organises the list. From a starting point draw one branch for each shirt; from the end of each shirt branch draw one branch for each pair of trousers. Every path from the start to the end of the tree is one outfit:

ShirtTrousersOutfit
redblack / grey(red, black), (red, grey)
blueblack / grey(blue, black), (blue, grey)
whiteblack / grey(white, black), (white, grey)

There are $6$ outfits — and $6=3\times2$. That is no accident: each of the $3$ shirt branches carries the same number, $2$, of trouser branches, so the tree has $3$ groups of $2$ leaves. Notice also that the outfits are ordered pairs (shirt, trousers) — the Cartesian product of Section 2.1, which has $n(A)\times n(B)$ elements.

📘 Definition 6.1 — Arrangements, words and codes

An arrangement of length $r$ from a set of symbols is an ordered list of $r$ symbols from that set: a first symbol, a second symbol, …, an $r$-th symbol. Two arrangements are different if they differ in at least one position, so $\text{AB}\ne\text{BA}$.

  • The arrangement is with repetition if the same symbol may be used more than once (like the digits of a PIN: $7737$ is allowed), and without repetition if every symbol may be used at most once.
  • An arrangement of letters is called a word, whether or not it means anything: $\text{OSER}$ is a word made from the letters of $\text{ROSE}$. An arrangement of digits or other symbols is often called a code.

The Multiplication Principle

📐 Theorem 6.1 — Fundamental principle of counting (two stages)

Suppose a first event can occur in $m$ different ways and, whichever way it occurs, a second event can then occur in $n$ different ways. Then the two events, in that order, can occur together in $$m\times n$$ different ways.

Proof. Label the ways of the first event $1,2,\dots,m$. For each of them, the second event has $n$ ways — they may be different ways for different first choices, but there are always $n$ of them. Put the outcomes in a table with $m$ rows (one per way of the first event) and $n$ entries in each row. Every combined outcome appears exactly once in the table: in the row of its first event, at the position of its second event. A table of $m$ rows with $n$ entries each has $m\times n$ entries. $\blacksquare$

📐 Theorem 6.2 — Fundamental principle of counting (any number of stages)

If a job is done in $k$ successive stages, the first stage can be done in $n_1$ ways, and — whatever choices were made earlier — the second can be done in $n_2$ ways, the third in $n_3$ ways, …, the $k$-th in $n_k$ ways, then the whole job can be done in $$n_1\times n_2\times n_3\times\cdots\times n_k$$ ways.

Proof. Treat the first two stages as a single stage. By Theorem 6.1 it can be done in $n_1n_2$ ways, and the number of ways for each later stage still does not depend on how it was done. Now we have $k-1$ stages. Repeat the argument: combine the new first stage with the third stage ($n_1n_2\times n_3$ ways), and so on, until one stage with $n_1n_2\cdots n_k$ ways is left. $\blacksquare$

Corollary. The number of arrangements of length $r$ made from $n$ different symbols with repetition allowed is $n\times n\times\cdots\times n=n^r$.

The important hypothesis is the phrase "whatever choices were made earlier". The choices at a stage may change with earlier choices (if you used the digit $7$ first, it is not available second), but the number of choices must not. When it does change — for instance when a first digit of $0$ is forbidden only in some cases — split the problem into cases (the addition principle, below) or fill the restricted positions first.

🧭 Problem-solving strategy — The slot method
  1. Draw one box ("slot") for each stage of the job — for a 4-digit number, four boxes.
  2. Fill the most restricted slot first (a first digit that cannot be $0$, a last digit that must be even, a letter that must be a vowel).
  3. Write in each slot the number of choices left for it, given the slots already filled. Check that this number does not depend on which choices were made before.
  4. Multiply the numbers in the slots (Theorem 6.2). If a slot's count would depend on earlier choices, split into cases and add.
✏️ Example 1 — Outfits
Riya (above) also has $4$ pairs of shoes. How many outfits of one shirt, one pair of trousers and one pair of shoes can she wear? If she refuses to wear the white shirt with the grey trousers, how many are left?
Stages Shirt ($3$ ways), then trousers ($2$ ways), then shoes ($4$ ways). The number of choices at each stage is the same whatever was chosen before.
Multiply $3\times2\times4=24$ outfits.
Restriction The forbidden shirt–trousers pair can be worn with each of the $4$ pairs of shoes, so it spoils $1\times4=4$ outfits. Left: $24-4=20$.
Check Count shirt–trousers pairs first: $3\times2-1=5$ allowed pairs, each with $4$ pairs of shoes: $5\times4=20$ ✓.
✏️ Example 2 — Words with and without repetition
(a) How many 4-letter words, with or without meaning, can be made from the letters of $\text{ROSE}$ if no letter is repeated?
(b) How many if letters may be repeated?
(c) How many 3-letter words can be made from the $26$ letters of the English alphabet if no letter is repeated?
(a) Slots First letter: $4$ choices. Whichever is used, $3$ letters are left for the second place, then $2$, then $1$: $4\times3\times2\times1=24$ words.
(b) Each of the $4$ places can be any of the $4$ letters: $4\times4\times4\times4=4^4=256$ words (Corollary of Theorem 6.2).
(c) $26\times25\times24=15\,600$ words.
Check Words with repetition include those without, so (b) must be larger than (a): $256\gt24$ ✓. The $256-24=232$ extra words are those with at least one repeated letter, such as $\text{ROOS}$.
✏️ Example 3 — PINs and number plates
(a) How many 4-digit PINs are there? (A PIN may start with $0$.)
(b) How many 4-digit PINs have all four digits different?
(c) A state issues vehicle numbers in which a fixed state code and district code are followed by a two-letter series (letters A–Z, repetition allowed) and a number from $0001$ to $9999$. How many vehicles can one district register?
(a) $10$ choices for each digit: $10^4=10\,000$ PINs.
(b) $10\times9\times8\times7=5040$ PINs.
(c) Stages Series: $26\times26=676$ letter pairs. Number: $9999$ choices ($0000$ is not used). Total $676\times9999=6\,759\,324$ vehicles.
Check $676\times10\,000-676=6\,760\,000-676=6\,759\,324$ ✓ — about $6.76$ million, which is why busy districts run out of series and start new ones.
Interactive 1 — The Counting Tree

Choose how many shirts, trousers and pairs of shoes there are. The tree grows one stage at a time: every branch of a stage carries the same number of branches at the next stage. Then a purple path walks through every outfit in turn while the counter ticks. The final count always equals the product of the stage counts.

stage counts—
paths counted—
product—
current outfit—

The Addition Principle: Either–Or

Sometimes a job is not done in stages but in one of several separate ways. To travel from Chennai to Bengaluru you might go through Vellore or take a direct highway; a 3-digit even number ends in $0$ or in some other even digit. When the cases do not overlap, their counts add.

📐 Theorem 6.3 — Addition principle

Suppose every way of doing a job falls into exactly one of $k$ cases — no way belongs to two cases — and case $1$ can happen in $m_1$ ways, case $2$ in $m_2$ ways, …, case $k$ in $m_k$ ways. Then the job can be done in $$m_1+m_2+\cdots+m_k$$ ways.

Reason. The cases are disjoint sets whose union is the set of all ways. For disjoint sets $n(A\cup B)=n(A)+n(B)$ (Section 1.3), and the same holds for any number of disjoint sets. $\blacksquare$

Two habits follow from the two principles. Read "and then" (stages) as multiply and "or" (separate cases) as add. And when a condition says "at least one", it is often quicker to count everything and subtract the arrangements that break the condition: $$\#(\text{at least one}) = \#(\text{all}) - \#(\text{none}).$$ This is the addition principle used backwards: "all" splits into the disjoint cases "none" and "at least one".

✏️ Example 4 — Digits with a forbidden zero
Using the digits $0,1,2,3,4,5$, how many 3-digit numbers (from $100$ to $999$) can be formed (a) if digits may be repeated, (b) if no digit is repeated, (c) that are even, with no digit repeated?
(a) Hundreds digit: $5$ choices (not $0$). Tens and units: $6$ each. $5\times6\times6=180$.
(b) Hundreds: $5$ (not $0$). Tens: $5$ (any digit except the one used, and $0$ is now allowed). Units: $4$. $5\times5\times4=100$.
(c) Cases Fill the units slot first: it must be $0$, $2$ or $4$. But the hundreds slot has $5$ choices if the units digit is $0$ and only $4$ choices otherwise (it can be neither $0$ nor the units digit) — the count depends on the earlier choice, so split into cases.
Units $=0$: hundreds $5$, tens $4$: $5\times4=20$.
Units $=2$ or $4$: $2$ choices; hundreds $4$; tens $4$: $2\times4\times4=32$.
(c) Add The cases do not overlap: $20+32=52$ even numbers. Check: the odd ones (units $1$, $3$ or $5$) number $3\times4\times4=48$, and $52+48=100$, the answer to (b) ✓.
✏️ Example 5 — Roads and routes
There are $3$ roads from Chennai to Vellore, $4$ roads from Vellore to Bengaluru, and $2$ direct highways from Chennai to Bengaluru that do not pass through Vellore.
(a) In how many ways can a driver go from Chennai to Bengaluru?
(b) In how many ways can she go from Chennai to Bengaluru through Vellore and come back through Vellore, if she does not use any road twice?
(a) Cases Through Vellore: Chennai–Vellore and then Vellore–Bengaluru: $3\times4=12$ routes. Direct: $2$ routes. A route is either through Vellore or direct, never both.
(a) Add $12+2=14$ routes.
(b) Stages Out: $3$ then $4$. Back: Bengaluru–Vellore on one of the $3$ unused roads, then Vellore–Chennai on one of the $2$ unused roads. $3\times4\times3\times2=72$ round trips.
Check Group the choices by road pair instead: the two Chennai–Vellore roads (out, back) form an ordered pair of different roads, $3\times2=6$ ways; the two Vellore–Bengaluru roads, $4\times3=12$ ways; and $6\times12=72$ ✓. Without the "no road twice" rule there would be $12\times12=144$ round trips.
Interactive 2 — Routes: Multiply Along, Add Across

Set the number of roads on each leg. The highlighted route runs through every possibility in turn. Routes through Vellore pair one red road with one blue road — stages, so multiply. Green direct highways are a separate case — so add.

through Vellore—
direct—
total—
route now—
✏️ Example 6 — "At least one" by subtraction
(a) How many 4-digit PINs have at least one repeated digit?
(b) How many 3-digit numbers (from $100$ to $999$) contain the digit $7$ at least once?
(c) How many positive divisors does $72$ have?
(a) All PINs: $10^4=10\,000$. PINs with no repeated digit: $5040$ (Example 3). At least one repeat: $10\,000-5040=4960$.
(b) All 3-digit numbers: $9\times10\times10=900$. With no $7$ at all: hundreds $8$ choices (not $0$, not $7$), tens $9$, units $9$: $8\times9\times9=648$. At least one $7$: $900-648=252$.
(c) Stages $72=2^3\times3^2$. A divisor is $2^a\,3^b$ with $a\in\{0,1,2,3\}$ ($4$ choices) and $b\in\{0,1,2\}$ ($3$ choices), and different pairs $(a,b)$ give different divisors. So there are $4\times3=12$ divisors.
Check (c) Listing: $1,2,3,4,6,8,9,12,18,24,36,72$ — twelve ✓. In (b), counting directly by cases (exactly one, two or three sevens) gives $225+26+1=252$ ✓, but takes far longer.
⚠️ Common mistakes with the counting principles

1. Adding instead of multiplying (or the reverse). Stages done one after another ("a shirt and then trousers") multiply. Separate, non-overlapping cases ("by train or by bus") add.

2. Forgetting that a number cannot start with $0$. $0473$ is a PIN, but it is not a 4-digit number. Fill the first slot first.

3. Filling slots in the wrong order. For "even numbers without repetition", if you fill the hundreds digit first, the number of choices for the units digit depends on what you used. Fill the restricted slot first, and split into cases when a count still changes.

4. Overlapping cases. The addition principle needs disjoint cases. "Numbers starting with $7$" and "numbers ending with $7$" overlap ($717$ is in both), so their counts cannot simply be added.

5. Letters into letterboxes. $4$ different letters posted into $3$ letterboxes: each letter chooses a box, so the answer is $3^4=81$, not $4^3=64$. Ask "who is choosing?" — the choosers are the stages.

Exercises

I
Stages that multiply.
  • 1 A thali offers a choice of $4$ curries, $3$ kinds of bread and $2$ desserts. How many different thalis with one item of each kind are possible?
  • 2 How many 6-digit UPI PINs are there? (A PIN may start with $0$.)
  • 3 How many 6-digit PINs have no repeated digit?
  • 4 A coin is tossed $5$ times and the sequence of heads and tails is recorded. How many sequences are possible?
  • 5 A die is rolled $3$ times and the ordered results are recorded. How many outcomes are possible?
  • 6 How many 3-letter words can be formed from the letters of $\text{PLANET}$ (a) with no letter repeated (b) with repetition allowed?
  • 7 In how many ways can a test of $10$ true/false questions be answered, if every question is answered?
  • 8 A test has $6$ multiple-choice questions, each with $4$ options. In how many ways can a student answer all of them, choosing one option per question?
1 $4\times3\times2=24$ thalis.
2 $10^6=1\,000\,000$ PINs.
3 $10\times9\times8\times7\times6\times5=151\,200$ PINs.
4 $2$ outcomes per toss: $2^5=32$ sequences.
5 $6^3=216$ outcomes.
6 (a) $6\times5\times4=120$ (b) $6^3=216$.
7 $2^{10}=1024$ ways.
8 $4^6=4096$ ways.
II
Numbers and digits. A "3-digit number" means a number from $100$ to $999$; in general a number does not start with $0$.
  • 1 How many 3-digit numbers can be formed from the digits $1$–$9$ if repetition is allowed?
  • 2 How many if no digit is repeated?
  • 3 Use the counting principle to find how many 4-digit numbers there are altogether.
  • 4 How many 4-digit numbers have all their digits different?
  • 5 How many 4-digit numbers can be formed from the digits $1,2,3,4,5$, with no digit repeated, that are divisible by $5$?
  • 6 How many 3-digit even numbers can be formed from the digits $1,2,3,4,5,6$ if digits may be repeated?
  • 7 How many 3-digit numbers divisible by $5$ can be formed from the digits $0,1,2,3,4,5$ with no digit repeated?
  • 8 How many odd numbers between $3000$ and $5000$ have four different digits?
Check: list the numbers and count them
numbers found (by listing)—
smallest / largest—
1 $9^3=729$.
2 $9\times8\times7=504$.
3 First digit $9$ choices, each other digit $10$: $9\times10^3=9000$ (indeed $1000$ to $9999$).
4 First digit $9$ (not $0$), second $9$ (now $0$ is allowed, but not the first digit), third $8$, fourth $7$: $9\times9\times8\times7=4536$.
5 Units digit must be $5$ ($1$ way); the other three places from the remaining $4$ digits: $4\times3\times2=24$.
6 Units digit $2$, $4$ or $6$: $3$ ways; hundreds and tens $6$ each: $6\times6\times3=108$.
7 Units $0$: hundreds $5$, tens $4$: $20$. Units $5$: hundreds $4$ (not $0$, not $5$), tens $4$: $16$. Total $20+16=36$.
8 The first digit is $3$ or $4$. First digit $3$: units digit odd but not $3$ — $1,5,7,9$, $4$ ways; middle digits $8\times7$: $4\times56=224$. First digit $4$: units digit $1,3,5,7,9$, $5$ ways; middle $8\times7$: $280$. Total $224+280=504$.
III
Either–or, and "at least one".
  • 1 A shelf has $5$ different maths books and $7$ different physics books. In how many ways can you choose (a) one book (b) one maths book and one physics book?
  • 2 A student can go from home to college by one of $2$ bus routes or one of $3$ metro routes. In how many ways can she make the round trip if she does not come back by the route she went by?
  • 3 A password has $5$ characters, each a lowercase letter (a–z) or a digit (0–9), with repetition allowed. How many passwords contain at least one digit?
  • 4 How many 3-character codes made of digits (000 to 999) have at least one repeated digit?
  • 5 How many 3-digit numbers contain at least one $0$?
  • 6 How many positive divisors does $360=2^3\times3^2\times5$ have?
  • 7 How many positive integers less than $1000$ can be written using only the digits $1,2,3$ (repetition allowed)?
  • 8 A ship signals by hoisting $1$, $2$ or $3$ flags, one above another, chosen from $5$ different flags (no flag used twice in one signal). How many signals are possible?
1 (a) Maths or physics: $5+7=12$. (b) Maths and then physics: $5\times7=35$.
2 $2+3=5$ routes to college; back by any of the other $4$: $5\times4=20$.
3 All: $36^5=60\,466\,176$. No digit (letters only): $26^5=11\,881\,376$. At least one digit: $48\,584\,800$.
4 All: $10^3=1000$; all different: $10\times9\times8=720$. At least one repeat: $280$.
5 All: $900$; no $0$ anywhere: $9^3=729$. At least one $0$: $171$.
6 Divisors $2^a3^b5^c$ with $a$: $4$ choices, $b$: $3$, $c$: $2$: $4\times3\times2=24$.
7 1-digit: $3$; 2-digit: $3^2=9$; 3-digit: $3^3=27$. Total $3+9+27=39$.
8 One flag: $5$; two: $5\times4=20$; three: $5\times4\times3=60$. Total $85$ signals.
IV
Applications and modelling.
  • 1 Indian mobile numbers have $10$ digits, and the first digit is $6$, $7$, $8$ or $9$. How many such numbers are possible?
  • 2 A cricket franchise designs a jersey with a body colour and a different sleeve colour, both chosen from $5$ team colours. How many designs are possible?
  • 3 A code uses sequences of dots and dashes of length $1$, $2$, $3$ or $4$. How many different symbols can it represent?
  • 4 Modelling. A payment network gives every transaction a new $12$-digit ID ($000\ldots0$ allowed). If it handles $1.4\times10^{10}$ transactions per month, roughly how many months will it take to use up all the IDs? State your assumption.
  • 5 In how many ways can $4$ different letters be posted into $3$ letterboxes (any box may receive any number of letters)?
  • 6 How many functions are there from $A=\{1,2,3\}$ to $B=\{a,b\}$? (Section 2.3: each element of $A$ must be given exactly one image in $B$.)
1 $4\times10^9=4\,000\,000\,000$ numbers.
2 Body $5$, then sleeves $4$: $20$ designs.
3 $2+2^2+2^3+2^4=2+4+8+16=30$ symbols.
4 There are $10^{12}$ IDs. Assuming the monthly rate stays at $1.4\times10^{10}$: $\dfrac{10^{12}}{1.4\times10^{10}}\approx71.4$, so about $71$ months — roughly $6$ years. (Real traffic grows every year, so it would be sooner.)
5 Each letter chooses one of $3$ boxes: $3^4=81$ ways.
6 Each of the $3$ elements of $A$ chooses its image in $2$ ways: $2^3=8$ functions.
🎯 Exam corner Board · 1 markBoard · 2 marksBoard · 3 marksBoard · Case studyJEE Main

How this is examined: Board papers ask for numbers or codes formed from given digits or letters, with or without repetition (1–3 marks), often with a divisibility or "even" condition. JEE rarely asks the principle on its own — it is the first step of almost every counting and probability problem, so speed with slots and cases matters.

E1. Board · 1 mark The number of 3-letter codes that can be made from the letters A, B, C, D, E if no letter is repeated is (A) $125$   (B) $60$   (C) $10$   (D) $15$

Idea Three slots: $5\times4\times3=60$.
Trap (A) $=5^3$ allows repetition; (C) $=10$ counts only the choice of letters, ignoring their order (that will be ${}^5C_3$ in Section 6.3).
Answer (B).

E2. Board · 2 marks How many 4-digit numbers can be formed from the digits $1,2,3,4,5$ if (i) repetition of digits is allowed (ii) repetition is not allowed?

(i) Each of the $4$ places: $5$ choices. $5^4=625$. (1 mark)
Answer (ii) $5\times4\times3\times2=120$. (No digit is $0$, so no first-digit restriction is needed.) (1 mark)

E3. Board · 3 marks How many 3-digit even numbers can be formed from the digits $0,1,2,3,4,5,6$ if no digit is repeated?

Cases The units digit is $0$, $2$, $4$ or $6$; the hundreds digit cannot be $0$, so its number of choices depends on whether $0$ is already used. Split. (1 mark)
Count Units $0$: hundreds $6$, tens $5$: $30$. Units $2,4$ or $6$: $3$ ways; hundreds $5$ (not $0$, not the units digit); tens $5$: $3\times5\times5=75$. (1½ marks)
Answer $30+75=105$. (½ mark)

E4. Board · Case study A school gives every student an ID made of $2$ capital letters (A–Z) followed by $3$ digits (0–9), for example $\text{KB}\,407$. (i) How many IDs are possible? (1 mark) (ii) How many IDs have two different letters? (1 mark) (iii) How many IDs have two different letters, three different digits and an odd last digit? (2 marks)

(i) $26^2\times10^3=676\times1000=676\,000$. (1 mark)
(ii) $26\times25\times10^3=650\,000$. (1 mark)
Answer (iii) Letters: $650$ ways. Digits: fill the last (odd) digit first — $5$ ways — then the other two from the remaining $9$ digits: $9\times8$. Digits: $5\times9\times8=360$. Total $650\times360=234\,000$. (2 marks)

E5. JEE Main Numerical answer. Using each of the digits $1,2,3,4,5$ exactly once, how many 5-digit numbers divisible by $4$ can be formed?

Idea A number is divisible by $4$ exactly when the number formed by its last two digits is. With distinct digits from $1$–$5$, the possible endings are $12$, $24$, $32$, $52$ ($44$ repeats a digit).
Count For each of the $4$ endings, the remaining $3$ digits fill the first three places in $3\times2\times1=6$ ways: $4\times6=24$.
Answer $24$.

E6. JEE Main The number of even positive divisors of $N=2^4\times3^3\times5$ is (A) $40$   (B) $32$   (C) $24$   (D) $30$

Idea A divisor is $2^a3^b5^c$ with $0\le a\le4$, $0\le b\le3$, $0\le c\le1$. It is even exactly when $a\ge1$: $4$ choices for $a$, $4$ for $b$, $2$ for $c$.
Trap (A) $=5\times4\times2$ counts all divisors, odd ones included.
⏱ Fast route Even divisors = all − odd $=40-(4\times2)=32$.
Answer (B) $4\times4\times2=32$.
🔬 Research–Teaching NexusMini project · about 45 minutes

Research question. How long would a computer need to guess your password by trying every possibility? Which matters more — making a password longer, or using more kinds of characters?

Why it matters. Attackers who steal a file of scrambled passwords test guesses at enormous speed — around $10^{10}$ guesses per second is realistic for one powerful graphics card. The number of possible passwords is a pure counting problem: with an alphabet of $s$ symbols and length $L$, Theorem 6.2 gives $s^L$ passwords.

What to do.

  1. Make a spreadsheet with alphabets of size $s=10$ (digits), $26$ (lowercase), $62$ (upper- and lowercase letters and digits) and $94$ (all keyboard symbols), and lengths $L=4,6,8,10,12$.
  2. Compute $s^L$ in each cell, and the worst-case time to try them all at $10^{10}$ guesses per second. Convert the times to sensible units (seconds, hours, days, years).
  3. Compare: is it better to go from $8$ to $10$ lowercase letters, or from lowercase to all $94$ symbols at length $8$?
  4. Survey $10$ classmates (anonymously!) about the type of password they use — length and kinds of characters only — and estimate the time to crack each type.

Tools: A spreadsheet app (use the power function, e.g. =26^8)

Hand in: Your table, a one-paragraph recommendation for a strong but memorable password, and the reasoning from the counting principle behind it.

Going further. A "passphrase" of $4$ words chosen at random from a list of $7776$ words has $7776^4$ possibilities. How does it compare with an $8$-character password from all $94$ symbols?

Instructor note: at $10^{10}$ guesses/s, $26^8\approx2.09\times10^{11}$ takes about $21$ s; $62^8\approx2.18\times10^{14}$ about $6.1$ hours; $94^8\approx6.10\times10^{15}$ about $7.1$ days; $26^{10}\approx1.41\times10^{14}$ about $3.9$ hours — so length and alphabet both matter, and each extra character multiplies the time by $s$. $7776^4\approx3.66\times10^{15}$, comparable to $94^8$ but far easier to remember.

🧪 Self-check quiz

0/5 correct

Q1. With $3$ shirts and $4$ pairs of trousers, the number of different outfits (one shirt and one pair of trousers) is

Q2. The number of 4-digit PINs (which may start with $0$) with all digits different is

Q3. A job can be done either by machine A in $5$ ways or by machine B in $3$ ways, and no way uses both machines. The number of ways of doing the job is

Q4. In how many ways can $3$ different letters be posted into $4$ letterboxes?

Q5. How many 3-digit numbers have at least one repeated digit?

← Chapter 6 — Permutations and Combinations6.2 Permutations →