Chapter 4 ยท Permutations and Combinations

4.1 Counting Principle and Permutations

Counting without listing: the fundamental principle of counting, factorials, the number ${}^{n}P_{r}=\dfrac{n!}{(n-r)!}$ of arrangements of $r$ out of $n$ different objects, arrangements with repeated objects, restrictions, round tables and the dictionary rank of a word.

A phone's lock screen asks for a four-digit PIN. How many PINs are possible, and how long would a thief need to try them all? A university wants to print a different number plate, timetable slot or exam roll number for every one of a million people โ€” will two letters and four digits be enough? Twelve teams play a league in which only the order of the top three matters โ€” how many different podiums can there be? In every one of these questions the answer is far too large to list, yet it is easy to count once you see the structure: a choice made in stages, each stage with a known number of options.

This section builds that counting from a single principle. From it come the factorial $n!$, the number of permutations ${}^{n}P_{r}$ โ€” arrangements of $r$ objects chosen from $n$ different ones โ€” and the tools JEE Main uses again and again: digits that may not start with $0$, letters that repeat, people who must sit together or apart, round tables, and the position of a word in a dictionary. Section 4.2 then turns arrangements into selections, and Chapter 5 uses those selections to expand $(a+b)^n$.

The Fundamental Principle of Counting

Suppose a canteen offers $3$ kinds of sandwich and $4$ kinds of juice, and a "combo" is one sandwich and one juice. Draw a tree: three branches for the sandwich, and from the end of each, four branches for the juice. There are $3\times4=12$ paths through the tree, one for each combo. If instead you may take either a sandwich or a juice (not both), the choices simply sit side by side: $3+4=7$. These two observations are the whole foundation of the chapter.

๐Ÿ“ Theorem 4.1 โ€” The fundamental principle of counting

Multiplication principle. If a task is done in $k$ successive stages, the first stage can be done in $m_1$ ways, and โ€” whatever was done before โ€” the second stage can then be done in $m_2$ ways, the third in $m_3$ ways, and so on, then the whole task can be done in

$$m_1\times m_2\times\cdots\times m_k\ \text{ways.}$$

Addition principle. If a task can be done by one of $k$ methods that do not overlap (no outcome can be reached by two different methods), and the methods can be carried out in $m_1, m_2,\dots,m_k$ ways, then the task can be done in $m_1+m_2+\cdots+m_k$ ways.

Why. With two stages, the outcomes are ordered pairs (first choice, second choice). If the second stage always has $m_2$ options, the outcomes are arranged in $m_1$ rows of $m_2$ โ€” exactly the count $n(A\times B)=mn$ of a Cartesian product from Section 1.1 โ€” so there are $m_1m_2$; repeat the argument stage by stage. The addition principle is $n(A\cup B)=n(A)+n(B)$ for disjoint sets. $\blacksquare$ The key words: "and then" multiplies, "or" (with no overlap) adds. Note the phrase "whatever was done before": the number of options at a stage must not depend on the earlier choices, even though the options themselves may.

โœ๏ธ Example 1 โ€” Number plates and a canteen menu
(a) A state issues number plates with two letters (Aโ€“Z, repetition allowed) followed by a four-digit number whose first digit is not $0$. How many plates are possible? (b) How many, if the two letters must be different and the four digits must all be different? (c) A canteen has $4$ starters, $6$ main courses and $3$ desserts. A "meal" is one main course together with either a starter or a dessert. How many meals are there?
(a) Six stages: $26\times26$ for the letters, then $9$ for the first digit ($1$โ€“$9$) and $10\times10\times10$ for the rest: $676\times9000=6\,084\,000$ plates.
(b) Letters: $26\times25$. Digits: first $9$ (not $0$); second $9$ (any digit except the first, and now $0$ is allowed); third $8$; fourth $7$. Total $650\times4536=2\,948\,400$.
(c) Main course ($6$ ways) and then (starter or dessert: $4+3=7$ ways): $6\times7=42$ meals.
Check In (b) the second digit also has $9$ options: it loses the digit already used but gains $0$. The number of options is the same whatever the first digit was โ€” exactly what the multiplication principle needs.
๐Ÿงญ Problem-solving strategy โ€” counting by stages
  1. Draw the slots to be filled (places in a number, seats, positions in a word) and write the number of options under each.
  2. Fill the most restricted slot first โ€” the first digit that cannot be $0$, the last digit that must be even, the seat reserved for a particular person.
  3. If the number of options for a slot depends on an earlier choice (for example, whether $0$ has already been used), split into cases that do not overlap and add them.
  4. For "at least oneโ€ฆ" it is often quicker to count the complement: all outcomes minus those with none.
โœ๏ธ Example 2 โ€” Four-digit numbers with different digits
Using the digits $0,1,2,\dots,9$, with no digit repeated, how many four-digit numbers can be formed? How many of them are (a) even, (b) divisible by $5$?
Find the number of even ones (a) before you open the solution:
All First digit $9$ ways (not $0$), then $9$, $8$, $7$: $9\times9\times8\times7=4536$.
(a) Case 1 Last digit $0$: the other three places use any three of the remaining nine digits in order: $9\times8\times7=504$.
(a) Case 2 Last digit $2,4,6$ or $8$ ($4$ ways). First digit: not $0$ and not the last digit โ€” $8$ ways. Middle two: $8\times7$. Total $4\times8\times8\times7=1792$.
(a) Even numbers: $504+1792=2296$.
(b) Last digit $0$: $504$. Last digit $5$: first digit $8$ ways (not $0$, not $5$), then $8\times7$: $448$. Total $952$.
Check Odd numbers by the same method: last digit $1,3,5,7,9$ ($5$ ways), first $8$, then $8\times7$: $2240$; and $2296+2240=4536$ โœ“. There are slightly more even than odd numbers because $0$ may end a number but not start it.

A student chooses one book to read โ€” one of $5$ novels or one of $3$ biographies โ€” and then one of $4$ pens to write a review. In how many ways can this be done?

Factorials and Permutations โ€” the Meaning of ${}^{n}P_{r}$

The most important special case of the multiplication principle is arranging different objects in a row. Placing $n$ different books on a shelf: $n$ choices for the first place, $n-1$ for the second, and so on down to $1$. This product appears so often that it has its own name.

๐Ÿ“˜ Definition 4.1 โ€” Factorial

For a natural number $n$, $n$ factorial is $n!=n(n-1)(n-2)\cdots2\cdot1$. We also define $0!=1$. Thus $1!=1$, $2!=2$, $3!=6$, $4!=24$, $5!=120$, $6!=720$, $7!=5040$, and $n!=n\cdot(n-1)!$ for every $n\ge1$.

๐Ÿ“˜ Definition 4.2 โ€” Permutation; the number ${}^{n}P_{r}$

A permutation of $r$ objects chosen from $n$ different objects is an arrangement of $r$ of them in a definite order (in a row of $r$ places). The number of such permutations, with no object used twice, is written ${}^{n}P_{r}$ or $P(n,r)$, for $0\le r\le n$. "Arrangement" means order matters: $ABC$ and $BAC$ are different permutations of the same three letters.

๐Ÿ“ Theorem 4.2 โ€” Counting permutations

For integers $0\le r\le n$:

$${}^{n}P_{r}=n(n-1)(n-2)\cdots(n-r+1)=\frac{n!}{(n-r)!},\qquad {}^{n}P_{n}=n!,\qquad {}^{n}P_{0}=1.$$

If repetition is allowed (each of the $r$ places may be filled by any of the $n$ objects), the number of arrangements is $n^r$.

Proof. Fill the $r$ places in turn. The first can take any of the $n$ objects, the second any of the remaining $n-1$, โ€ฆ, the $r$-th any of the remaining $n-r+1$. By Theorem 4.1 the count is the product of these $r$ numbers. Multiplying and dividing by $(n-r)!=(n-r)(n-r-1)\cdots1$ gives $\dfrac{n!}{(n-r)!}$. With repetition, every place has $n$ options: $n\cdot n\cdots n=n^r$. $\blacksquare$ Why $0!=1$? Putting $r=n$ in the formula gives ${}^{n}P_{n}=\dfrac{n!}{0!}$, which must equal $n!$; so $0!=1$ is the only choice that keeps the formula true. You met ${}^{n}P_{r}$ already in Section 1.2: it is the number of one-one functions from an $r$-element set to an $n$-element set.

๐Ÿ“ Theorem 4.3 โ€” Two recurrences for ${}^{n}P_{r}$

For $1\le r\le n$ (and, in the second, $r\le n-1$):

$${}^{n}P_{r}=n\cdot{}^{n-1}P_{r-1},\qquad {}^{n}P_{r}={}^{n-1}P_{r}+r\cdot{}^{n-1}P_{r-1}.$$

Proof by counting. First identity: choose the object for the first place ($n$ ways), then arrange $r-1$ of the remaining $n-1$ objects in the other places. Second identity: fix one particular object $X$. Arrangements that do not use $X$ are arrangements of $r$ of the other $n-1$ objects: ${}^{n-1}P_{r}$. Arrangements that use $X$: choose its place ($r$ ways), then fill the other $r-1$ places from the other $n-1$ objects: $r\cdot{}^{n-1}P_{r-1}$. Every arrangement is of exactly one kind; add. $\blacksquare$ Check with $n=5$, $r=3$: $60=24+3\times12$ โœ“.

A useful fact about $n!$. The power of a prime $p$ that divides $n!$ is $\left\lfloor\tfrac np\right\rfloor+\left\lfloor\tfrac n{p^2}\right\rfloor+\left\lfloor\tfrac n{p^3}\right\rfloor+\cdots$ (Legendre's formula): among $1,2,\dots,n$ there are $\lfloor n/p\rfloor$ multiples of $p$, each giving one factor $p$; the $\lfloor n/p^2\rfloor$ multiples of $p^2$ each give one more, and so on. For example $30!$ contains $5^{6+1}=5^7$ and many more factors $2$, so it ends in exactly $7$ zeros.

List all arrangements of $3$ letters chosen from $A,B,C,D$ (no repetition) in dictionary order. How many of them begin with $A$?

Set $n=4$, $r=3$, repetition not allowed. The readouts show ${}^{4}P_{3}=4\times3\times2=24$ arrangements, and the list falls into $4$ colour blocks โ€” one for each first letter โ€” of $6$ each. Once the first letter is fixed, the other two places are an arrangement of $2$ letters from the remaining $3$: ${}^{3}P_{2}=6$. That is the first recurrence of Theorem 4.3: ${}^{4}P_{3}=4\cdot{}^{3}P_{2}$. $24$ counts all the arrangements, and $12$ would be ${}^{4}P_{2}$.
Interactive 1 โ€” Slot Lab: Watch ${}^{n}P_{r}$ Being Counted

Choose $n$ letters and $r$ places. The slots at the top show how many letters are still available for each place; below, every arrangement is listed in dictionary order and coloured by its first letter. Press Play to list them one by one and watch the count grow in equal blocks. Switch on repetition to compare ${}^{n}P_{r}$ with $n^r$. (For large cases the lab lists only the block that starts with $A$.)

43
formulaโ€”
arrangementsโ€”
per first letterโ€”
listed so farโ€”
โœ๏ธ Example 3 โ€” Working with factorials and ${}^{n}P_{r}$
(a) Evaluate ${}^{7}P_{3}$, ${}^{6}P_{6}$, ${}^{10}P_{0}$ and $\dfrac{12!}{10!}$. (b) Find $n$ if ${}^{n}P_{4}=20\cdot{}^{n}P_{2}$. (c) Find $n$ if ${}^{2n}P_{3}=100\cdot{}^{n}P_{2}$. (d) Show that $1+1\cdot1!+2\cdot2!+\cdots+n\cdot n!=(n+1)!$.
(a) ${}^{7}P_{3}=7\cdot6\cdot5=210$; ${}^{6}P_{6}=6!=720$; ${}^{10}P_{0}=1$; $\dfrac{12!}{10!}=12\cdot11=132$ (cancel, never multiply out).
(b) ${}^{n}P_{4}=n(n-1)(n-2)(n-3)={}^{n}P_{2}\,(n-2)(n-3)$. So $(n-2)(n-3)=20=5\times4$, giving $n-2=5$, $n=7$ (the other root, $n=0$, is not allowed since $n\ge4$).
(c) ${}^{2n}P_{3}=2n(2n-1)(2n-2)=4n(n-1)(2n-1)$ and ${}^{n}P_{2}=n(n-1)$. Dividing (allowed, $n\ge2$): $4(2n-1)=100$, so $2n-1=25$ and $n=13$.
(d) Since $k\cdot k!=(k+1)k!-k!=(k+1)!-k!$, the sum $\sum_{k=1}^{n}k\cdot k!$ telescopes to $(n+1)!-1!$. Adding the $1$ in front gives $(n+1)!$. $\blacksquare$
Check (b) ${}^{7}P_{4}=840$ and $20\cdot{}^{7}P_{2}=20\cdot42=840$ โœ“. (d) with $n=3$: $1+1+4+18=24=4!$ โœ“.

A club of $8$ members elects a president, a secretary and a treasurer (three different people). The number of ways is

Permutations of Objects that are not all Different

How many different "words" can be made from the letters of $\text{TOOT}$? Pretend for a moment that the letters are all different: $T_1,O_1,O_2,T_2$, which can be arranged in $4!=24$ ways. Now erase the labels. The arrangements $T_1O_1O_2T_2$, $T_1O_2O_1T_2$, $T_2O_1O_2T_1$ and $T_2O_2O_1T_1$ all become the same word $\text{TOOT}$: each word was counted once for every way of labelling its $O$'s ($2!$) and its $T$'s ($2!$). So there are $\dfrac{24}{2!\,2!}=6$ words: TOOT, TOTO, TTOO, OTTO, OTOT, OOTT.

๐Ÿ“ Theorem 4.4 โ€” Arrangements with identical objects

The number of arrangements in a row of $n$ objects of which $p_1$ are alike of one kind, $p_2$ alike of a second kind, โ€ฆ, $p_k$ alike of a $k$-th kind (and the rest all different) is

$$\frac{n!}{p_1!\,p_2!\cdots p_k!}.$$

Proof. Let $N$ be the number of distinct arrangements. Label the alike objects so that all $n$ become different; there are now $n!$ arrangements. Each distinct arrangement gives rise to exactly $p_1!$ labelled ones by permuting the labels of the first kind among their positions, and independently $p_2!$ for the second kind, and so on. So $N\cdot p_1!\,p_2!\cdots p_k!=n!$. $\blacksquare$ This is the division principle: if every outcome you want has been counted exactly $m$ times, divide by $m$.

โœ๏ธ Example 4 โ€” The letters of REFERENCE
Consider the arrangements of all the letters of the word $\text{REFERENCE}$. (a) How many are there? (b) How many begin and end with $E$? (c) In how many are all four $E$'s together?
Find (c) before you open the solution:
Letters R, E, F, E, R, E, N, C, E: $9$ letters, with $E$ four times, $R$ twice, and $F$, $N$, $C$ once each.
(a) $\dfrac{9!}{4!\,2!}=\dfrac{362880}{48}=7560$.
(b) Put an $E$ in the first and last places (one way, the $E$'s being alike). The middle $7$ places hold R, R, E, E, F, N, C: $\dfrac{7!}{2!\,2!}=1260$.
(c) Glue $EEEE$ into one block. Now arrange $6$ objects โ€” the block, R, R, F, N, C โ€” with $R$ twice: $\dfrac{6!}{2!}=360$. The block itself can be arranged in only $1$ way, because its letters are alike.
Check In a random arrangement the chance that it begins and ends with $E$ is $\tfrac49\cdot\tfrac38=\tfrac16$, and $7560\div6=1260$ โœ“.

The number of different arrangements of the letters of the word $\text{LEVEL}$ is

Restricted Arrangements, Round Tables and Dictionary Rank

Most JEE Main questions on permutations add a condition: some people must sit together, some must not, some must occupy fixed places, or the arrangement is round. Four techniques deal with almost all of them.

๐Ÿงญ Problem-solving strategy โ€” restrictions
  1. Together โ†’ glue. Tie the objects that must be together into one block, arrange the blocks, then multiply by the number of arrangements inside the block.
  2. Never two together โ†’ gaps. Arrange the other objects first; they create gaps (one more gap than objects, counting both ends). Place the restricted objects in different gaps.
  3. Fixed places โ†’ fill them first, then arrange the rest.
  4. "Not all together" โ†’ complement: total minus "all together". (Careful: "not all together" and "no two together" are different conditions.)

Around a round table there is no first seat: if everybody moves one seat to the right, every person has the same neighbours as before, and we regard the arrangement as unchanged. Only the positions of the people relative to one another count.

๐Ÿ“˜ Definition 4.3 โ€” Circular permutation

A circular permutation of $n$ different objects is an arrangement of them around a circle, two arrangements being the same if one can be turned into the other by a rotation. (The seats are not numbered.)

Figure 4.1 โ€” Four different rows, one circular arrangement. Each table is the previous one turned one seat clockwise: everyone has the same left and right neighbours, so the four rows ABCD, DABC, CDAB, BCDA give only one arrangement around the table.
๐Ÿ“ Theorem 4.5 โ€” Circular permutations

The number of circular permutations of $n$ different objects is $\dfrac{n!}{n}=(n-1)!$. If, in addition, clockwise and anticlockwise arrangements are regarded as the same (beads on a necklace or flowers in a garland, which can be turned over) and $n\ge3$, the number is $\dfrac{(n-1)!}{2}$.

Proof. Cut a circular arrangement at any one of its $n$ places and read clockwise: you get a row. The $n$ cuts give $n$ different rows (Figure 4.1), and every row arises from exactly one circular arrangement. So $n!=n\times(\text{number of circular arrangements})$. A necklace can also be flipped; for $n\ge3$ flipping gives a different circular arrangement (the order of neighbours is reversed), so each necklace corresponds to exactly $2$ circular arrangements. $\blacksquare$ An equivalent and very practical way to think: seat one person anywhere to fix the circle, then arrange the other $n-1$ in a row. If the seats are numbered, or one seat is special (a head of the table, a window), the arrangement is linear again: $n!$.

โœ๏ธ Example 5 โ€” Boys and girls, in a row and round a table
Four boys and three girls are to be seated. In how many ways can they sit (a) in a row with all three girls together; (b) in a row with no two girls next to each other; (c) in a row with boys and girls alternating; (d) around a round table with all three girls together?
Find (b) before you open the solution:
(a) Glue The three girls form one block: arrange $5$ objects (block + $4$ boys) in $5!=120$ ways, and the girls inside the block in $3!=6$ ways: $720$.
(b) Gaps Boys first: $4!=24$ ways, giving the pattern $\_\,B\,\_\,B\,\_\,B\,\_\,B\,\_$ with $5$ gaps. The three girls go into three different gaps, in order: ${}^{5}P_{3}=60$. Total $24\times60=1440$.
(c) With $4$ boys and $3$ girls in $7$ seats the only alternating pattern is $BGBGBGB$. Boys in their seats $4!$, girls in theirs $3!$: $24\times6=144$.
(d) Glue the girls: $5$ units around the table, $(5-1)!=24$ ways; girls inside the block $3!=6$ ways: $144$.
Check In a row, "all three girls together" ($720$) and "no two girls together" ($1440$) do not add up to $7!=5040$: the remaining $2880$ arrangements have exactly two girls side by side. Always read which condition is asked.

Dictionary rank. Arrange all the "words" formed from the letters of a given word in alphabetical (dictionary) order. Where does the given word come? Go along the word from left to right. At each position, count the words that agree with it so far but have a smaller letter in this position โ€” each smaller letter still available fixes this position and leaves the rest free, contributing (number of arrangements of the remaining letters). Add up all these counts: that is the number of words before the given word, and its rank is one more. With repeated letters, count each distinct smaller letter once, and use Theorem 4.4 for the remaining letters.

All the arrangements of the letters of $\text{ZEBRA}$ are listed in dictionary order. In which position does $\text{ZEBRA}$ itself appear?

Choose the word ZEBRA and press Play. Position 1: the letters $A$, $B$, $E$, $R$ all come before $Z$, each starting $4!=24$ words: $96$. Position 2 ($Z$ fixed, letter $E$): $A$ and $B$ are smaller, $2\times3!=12$, total $108$. Position 3 ($ZE$ fixed, letter $B$): $A$ is smaller, $2!=2$, total $110$. Position 4 ($ZEB$ fixed, letter $R$): $A$ is smaller, $1$, total $111$. So $111$ words come before ZEBRA and its rank is $112$. $96$ stops after the first letter, and $111$ forgets the final $+1$. ZEBRA is not last: words such as ZRBEA come after it.
Interactive 2 โ€” Rank Lab: Where is the Word in the Dictionary?

Pick a word (or type your own, up to $9$ letters; repeated letters are allowed). The tiles on the right show the letters in alphabetical order. Press Play or Step: at each position the lab finds the letters that are still available and smaller than the letter of the word, counts the words each of them starts, and adds them to the running total. The rank is the total plus one.

all arrangementsโ€”
words before (so far)โ€”
rankโ€”
โœ๏ธ Example 6 โ€” Hard example: the rank of SUMMIT
All the arrangements of the letters of the word $\text{SUMMIT}$ are written in dictionary order. (a) How many arrangements are there? (b) What is the rank of $\text{SUMMIT}$? (c) What is the last word in the list?
Find the rank (b) before you open the solution:
(a) Six letters with $M$ twice: $\dfrac{6!}{2!}=360$. Alphabetical order of the letters: $I, M, M, S, T, U$.
Position 1 Letter $S$. Smaller letters available: $I$ and $M$. Words starting with $I$: the rest M, M, S, T, U give $\tfrac{5!}{2!}=60$. Words starting with $M$: the rest I, M, S, T, U are all different, $5!=120$. Running total $180$.
Position 2 $S$ fixed, letter $U$; remaining I, M, M, T, U. Smaller: $I$ (rest M, M, T, U: $\tfrac{4!}{2!}=12$), $M$ (rest I, M, T, U: $4!=24$), $T$ (rest I, M, M, U: $12$). Total $48$, running total $228$.
Positions 3โ€“6 $SU$ fixed, letter $M$; remaining I, M, M, T: smaller $I$ gives $\tfrac{3!}{2!}=3$ โ†’ $231$. $SUM$ fixed, letter $M$; remaining I, M, T: smaller $I$ gives $2!=2$ โ†’ $233$. $SUMM$ fixed, letter $I$, remaining I, T: nothing smaller. Last letter: nothing.
(b) $233$ words come before SUMMIT, so its rank is $234$.
(c) The last word has its letters in reverse alphabetical order: $\text{UTSMMI}$, rank $360$.
Check A computer listing of all $360$ arrangements puts SUMMIT at position $234$ โœ“ โ€” and Interactive 2 does the same count step by step.
โš ๏ธ JEE Main traps

1. Multiply or add? "And then" multiplies; "or" adds, and only when the cases do not overlap. Listing a few outcomes from each case shows quickly whether they overlap.

2. Zero cannot lead. Fill the first digit before the others; when another restriction (even, divisible by $5$) also involves $0$, split into "last digit $0$" and "last digit not $0$".

3. Divide only for identical objects. Repeated letters: divide by $p!$ for each repeated letter. People, books, digits in different places are never identical โ€” do not divide for them.

4. Round tables. $(n-1)!$ only when the seats are unlabelled; a numbered or special seat makes it $n!$. Divide by $2$ only for necklaces and garlands (which can be turned over), never for people at a table.

5. Dictionary rank. The sum counts the words before the word: add $1$. With a repeated letter, a smaller letter that occurs twice is still counted once at each position.

๐Ÿš€ Beyond JEE Main (JEE Advanced) โ€” derangements

Not in the JEE Main 2026 list; derangement counts appear in JEE Advanced problems. A derangement of $n$ objects is a permutation in which no object stays in its own place โ€” for example, $n$ letters put into $n$ addressed envelopes so that every letter is in a wrong envelope. Using inclusionโ€“exclusion (Section 1.1) on the sets "object $i$ is in its own place", the number of derangements is

$$D_n=n!\left(1-\frac1{1!}+\frac1{2!}-\frac1{3!}+\cdots+\frac{(-1)^n}{n!}\right),$$

so $D_2=1$, $D_3=2$, $D_4=9$, $D_5=44$. As $n$ grows, $D_n/n!$ approaches $1/e\approx0.368$: if a class of $30$ students hands in homework and the papers are returned at random, the chance that nobody gets their own paper back is about $37\%$.

Six different beads are threaded on a circular string to make a necklace. The number of different necklaces is

Exercises

Digits are $0$โ€“$9$ and letters are Aโ€“Z unless a part says otherwise. "Word" means any arrangement of letters, meaningful or not.

I
The fundamental principle of counting.
  • 1 A restaurant offers $5$ soups, $8$ main courses and $4$ desserts. How many three-course meals (one of each) are possible?
  • 2 How many three-digit numbers have all their digits odd?
  • 3 A test has $8$ multiple-choice questions with $4$ options each. In how many ways can it be answered if every question must be answered? If a question may also be left blank?
  • 4 How many five-letter passwords can be made from the $26$ capital letters if no letter is repeated?
  • 5 How many numbers from $100$ to $999$ have three different digits?
  • 6 In how many ways can $5$ letters be posted in $3$ letter boxes?
  • 7 Four roads join town $A$ to town $B$, three roads join $B$ to $C$, and two roads join $A$ directly to $C$. In how many ways can one travel from $A$ to $C$? In how many ways can one go from $A$ to $C$ through $B$ and come back through $B$ without using any road twice?
  • 8 How many four-digit numbers have at least one repeated digit?
  • 9 How many positive integers less than $1000$ can be written using only the digits $1,2,3,4,5$ (repetition allowed)?
1 $5\times8\times4=160$.
2 Each digit is one of $1,3,5,7,9$: $5^3=125$.
3 $4^8=65\,536$; with "blank" as a fifth option, $5^8=390\,625$.
4 ${}^{26}P_{5}=26\cdot25\cdot24\cdot23\cdot22=7\,893\,600$.
5 First digit $9$ (not $0$), second $9$, third $8$: $648$.
6 Each letter independently goes into one of $3$ boxes: $3^5=243$. (Not $5^3$: it is the letters that make the choices.)
7 Via $B$: $4\times3=12$, or directly: $2$; total $14$. Round trip: $A\to B$ $4$, $B\to C$ $3$, $C\to B$ $2$ (not the road just used), $B\to A$ $3$: $4\times3\times2\times3=72$.
8 Complement: all four-digit numbers $9000$ minus those with different digits $4536$ (Example 2): $4464$.
9 One-digit $5$, two-digit $5^2=25$, three-digit $5^3=125$ (no $0$ is available, so no leading-zero problem): $155$.
II
Factorials and ${}^{n}P_{r}$.
  • 1 Evaluate $\dfrac{7!}{5!}$ and $\dfrac{10!}{8!\,2!}$.
  • 2 Evaluate ${}^{9}P_{4}$.
  • 3 Find $n$ if ${}^{n}P_{3}=210$.
  • 4 Find $r$ if ${}^{10}P_{r}=720$.
  • 5 Find $n$ if ${}^{n}P_{4}=12\cdot{}^{n}P_{2}$.
  • 6 Show that $2\cdot4\cdot6\cdots(2n)=2^n\,n!$ and hence that $\dfrac{(2n)!}{n!}=2^n\cdot\big(1\cdot3\cdot5\cdots(2n-1)\big)$.
  • 7 Find the largest $k$ such that $2^k$ divides $20!$, and the number of zeros at the end of $50!$.
  • 8 Verify the identity ${}^{n}P_{r}={}^{n-1}P_{r}+r\cdot{}^{n-1}P_{r-1}$ for $n=6$, $r=3$.
  • 9 How many one-one functions are there from $\{1,2,3\}$ to $\{a,b,c,d,e\}$?
1 $\dfrac{7!}{5!}=7\cdot6=42$; $\ \dfrac{10!}{8!\,2!}=\dfrac{10\cdot9}{2}=45$.
2 $9\cdot8\cdot7\cdot6=3024$.
3 $n(n-1)(n-2)=210=7\cdot6\cdot5$: $n=7$.
4 $10\cdot9\cdot8=720$: $r=3$.
5 $(n-2)(n-3)=12=4\cdot3$: $n=6$.
6 Take a factor $2$ out of each of the $n$ even numbers: $2\cdot4\cdots(2n)=2^n(1\cdot2\cdots n)=2^n n!$. Then $(2n)!=\big(1\cdot3\cdots(2n-1)\big)\big(2\cdot4\cdots2n\big)=\big(1\cdot3\cdots(2n-1)\big)2^n n!$; divide by $n!$. $\blacksquare$
7 Legendre: $\lfloor20/2\rfloor+\lfloor20/4\rfloor+\lfloor20/8\rfloor+\lfloor20/16\rfloor=10+5+2+1=18$. Zeros of $50!$: factors $5$ are scarcer than factors $2$: $\lfloor50/5\rfloor+\lfloor50/25\rfloor=10+2=12$.
8 ${}^{6}P_{3}=120$; ${}^{5}P_{3}+3\cdot{}^{5}P_{2}=60+3\cdot20=120$ โœ“.
9 The images of $1,2,3$ must be different: ${}^{5}P_{3}=5\cdot4\cdot3=60$.
III
Repeated objects, restrictions and round tables.
  • 1 How many words can be formed from all the letters of $\text{PEPPER}$?
  • 2 How many words can be formed from all the letters of $\text{ASSESSMENT}$?
  • 3 How many seven-digit numbers can be formed using all of the digits $1,1,2,2,2,3,3$?
  • 4 How many seven-digit numbers can be formed using all of the digits $0,1,1,2,2,2,3$?
  • 5 In how many arrangements of the letters of $\text{DAUGHTER}$ (a) are the three vowels together, (b) are no two vowels next to each other?
  • 6 In how many ways can $5$ boys and $5$ girls stand in a row so that boys and girls alternate?
  • 7 In how many ways can $6$ people stand in a row if two particular people, $A$ and $B$, must not stand next to each other?
  • 8 In how many ways can $8$ people sit around a round table? In how many, if two particular people must sit next to each other?
  • 9 How many different necklaces can be made from $7$ different beads?
  • 10 How many arrangements of the letters of $\text{ORANGE}$ begin with a vowel?
1 P three times, E twice, R once: $\dfrac{6!}{3!\,2!}=60$.
2 $10$ letters: S four times, E twice, A, M, N, T once: $\dfrac{10!}{4!\,2!}=75\,600$.
3 $\dfrac{7!}{2!\,3!\,2!}=\dfrac{5040}{24}=210$ (no $0$, so every arrangement is a seven-digit number).
4 All arrangements $\dfrac{7!}{2!\,3!}=420$; those starting with $0$: arrange the other six, $\dfrac{6!}{2!\,3!}=60$. Answer $420-60=360$.
5 (a) Glue A, U, E: $6!\times3!=4320$. (b) Consonants D, G, H, T, R first: $5!=120$; $6$ gaps; vowels in three different gaps: ${}^{6}P_{3}=120$. Total $14\,400$.
6 Patterns $BGBG\ldots$ or $GBGB\ldots$ ($2$ ways), then $5!$ for the boys and $5!$ for the girls: $2\times120\times120=28\,800$.
7 All rows $6!=720$; with $A$, $B$ together $5!\times2=240$; answer $480$.
8 $(8-1)!=5040$. Together: glue the two into one unit, $7$ units round the table $6!=720$, times $2$ for their order: $1440$.
9 $\dfrac{(7-1)!}{2}=360$.
10 First letter O, A or E ($3$ ways), then the other five letters in $5!$ ways: $360$.
IV
Ranks, sums of numbers and harder arrangements.
  • 1 The letters of $\text{MASTER}$ are arranged in all possible ways and the words are listed in dictionary order. Find the rank of $\text{MASTER}$.
  • 2 Find the rank of $\text{COFFEE}$ among the arrangements of its letters in dictionary order.
  • 3 All five-digit numbers with different digits formed from $1,2,3,4,5$ are listed in increasing order. In which position is $35142$?
  • 4 Find the sum of all four-digit numbers formed by the digits $1,2,3,4$ (each used once).
  • 5 How many numbers greater than $40\,000$ can be formed using each of the digits $1,2,4,5,7$ exactly once?
  • 6 In how many ways can three married couples stand in a row if each husband stands next to his wife?
  • 7 How many arrangements of the letters of $\text{CALCULATOR}$ are there? In how many of them are the four vowels together?
1 Order A, E, M, R, S, T. Position 1 (M): A, E smaller, $2\times5!=240$. Position 2 (A): none. Position 3 (S; remaining E, R, S, T): E, R, $2\times3!=12$ โ†’ $252$. Position 4 (T; remaining E, R, T): $2\times2!=4$ โ†’ $256$. Position 5 (E): none. Rank $257$.
2 Order C, E, E, F, F, O. Position 1 (C): none. Position 2 (O; remaining E, E, F, F, O): $E$ gives $\tfrac{4!}{2!}=12$, $F$ gives $12$ โ†’ $24$. Position 3 (F; remaining E, E, F, F): $E$ gives $\tfrac{3!}{2!}=3$ โ†’ $27$. Position 4 (F; remaining E, E, F): $E$ gives $2$ โ†’ $29$. Then nothing. Rank $30$.
3 Numbers starting $1$ or $2$: $2\times4!=48$. Starting $3$, second digit $1,2,4$: $3\times3!=18$ โ†’ $66$. Starting $351$, fourth digit $2$: $1$ โ†’ $67$. Position $68$.
4 There are $4!=24$ numbers; each digit stands in each place $3!=6$ times. Each place contributes $6(1+2+3+4)=60$ units of its place value: sum $60\times1111=66\,660$.
5 Five-digit numbers above $40\,000$ start with $4$, $5$ or $7$: $3\times4!=72$.
6 Glue each couple: $3!$ orders of the couples, $2$ orders inside each couple: $6\times2^3=48$.
7 C, L, A twice each; U, T, O, R once: $\dfrac{10!}{2!\,2!\,2!}=453\,600$. Vowels A, A, U, O as one block: $7$ units (block, C, C, L, L, T, R) give $\dfrac{7!}{2!\,2!}=1260$; inside the block $\dfrac{4!}{2!}=12$. Total $15\,120$.
๐ŸŽฏ Exam corner JEE Main ยท MCQJEE Main ยท Numerical

E1. JEE Main ยท MCQ The number of five-digit numbers divisible by $4$ that can be formed from the digits $1,2,3,4,5$, each used exactly once, is (A) $18$ (B) $24$ (C) $30$ (D) $36$

Test A number is divisible by $4$ exactly when the number formed by its last two digits is. Two-digit endings from different digits of $\{1,\dots,5\}$ divisible by $4$: $12, 24, 32, 52$ โ€” four endings.
Count For each ending the other three digits fill the first three places in $3!=6$ ways: $4\times6$.
Answer (B) $24$.
โฑ Shortcut Fix the restricted places (the last two) first. $44$ is not allowed (repeated digit) and $20$, $40$ need a $0$.

E2. JEE Main ยท Numerical Find the number of arrangements of the letters of the word $\text{BALLOONS}$ in which the two $L$'s are together but the two $O$'s are not together. Give the answer to the nearest integer.

L's together Glue $LL$: $7$ objects (LL, B, A, O, O, N, S) with $O$ twice: $\dfrac{7!}{2!}=2520$.
Both pairs together Glue $LL$ and $OO$: $6$ different objects, $6!=720$.
Answer $2520-720=1800$.
โฑ Shortcut Gap method gives the same: arrange LL, B, A, N, S in $5!=120$ ways, choose $2$ of the $6$ gaps for the alike O's: $15$; $120\times15=1800$.

E3. JEE Main ยท MCQ Six people sit around a round table. The number of arrangements in which two particular people, $P$ and $Q$, are not next to each other is (A) $48$ (B) $96$ (C) $120$ (D) $72$

All $(6-1)!=120$.
Together Glue $P$ and $Q$: $5$ units round the table, $4!=24$, times $2$: $48$.
Answer (D) $120-48=72$.
โฑ Shortcut Seat $P$ anywhere. $Q$ has $5$ seats left, of which $2$ are next to $P$: $3$ choices; the other four people sit in $4!$ ways: $3\times24=72$.

E4. JEE Main ยท Numerical The letters of the word $\text{MANGO}$ are arranged in all possible ways and the words are listed as in a dictionary. Find the rank of the word $\text{MANGO}$. Give the answer to the nearest integer.

Order A, G, M, N, O.
Count Position 1 (M): A, G smaller, $2\times4!=48$. Position 2 (A): none. Position 3 (N; remaining G, N, O): G smaller, $2!=2$ โ†’ $50$. Position 4 (G; remaining G, O): none.
Answer $50+1=51$.

E5. JEE Main ยท MCQ The number of four-digit numbers greater than $3000$ that can be formed from the digits $0,2,3,5,7$ with no digit repeated is (A) $72$ (B) $96$ (C) $60$ (D) $48$

First digit A four-digit number above $3000$ must start with $3$, $5$ or $7$ (a number starting with $3$ is at least $3020\gt3000$).
Rest The other three places: any $3$ of the remaining $4$ digits in order, ${}^{4}P_{3}=24$.
Answer (A) $3\times24=72$.
โฑ Shortcut (B) $96$ is the number of all four-digit numbers from these digits ($4\times4\times3\times2$) โ€” it ignores the condition "greater than $3000$".

E6. JEE Main ยท Numerical Find the sum of all three-digit numbers that can be formed from the digits $1,3,5,7$ with no digit repeated. Give the answer to the nearest integer.

How many ${}^{4}P_{3}=24$ numbers.
Each place Fix a digit in, say, the units place; the other two places are filled in ${}^{3}P_{2}=6$ ways. So each of the four digits appears $6$ times in each place, and each place sums to $6(1+3+5+7)=96$.
Answer $96\times(100+10+1)=96\times111=10656$.
โฑ Shortcut Sum $=\dfrac{\text{(number of numbers)}\times\text{(sum of digits)}}{\text{(number of digits available)}}\times111\ldots1=\dfrac{24\times16}{4}\times111$.
๐Ÿ”ฌ Researchโ€“Teaching NexusResearch-tutored ยท optional, about 45 minutes

Research question. Do the password rules that websites and banks impose ("at least one capital, one digit, one symbol, no repeated characters") actually make passwords harder to guess โ€” and by how much?

Why it matters. An attacker who has stolen a database of hashed passwords can test billions of guesses per second on ordinary graphics hardware. The only defence is a search space so large that trying everything takes years. Security agencies in many countries now recommend long passphrases over short "complex" passwords, and counting shows why.

What to do.

  1. Count the search space of: a $4$-digit PIN; a $6$-digit PIN; an $8$-character password of lower-case letters; an $8$-character password from the $94$ printable keyboard characters; a passphrase of $4$ words chosen from a list of $7776$ words.
  2. Now impose a rule: "exactly $8$ characters, no character used twice". Use ${}^{n}P_{r}$. By what factor does the rule shrink the search space compared with $n^r$?
  3. Count $8$-character passwords from the $94$ characters that contain at least one digit, using the complement (all minus those with no digit).
  4. At $10^{10}$ guesses per second, how long does an exhaustive search of each space take? Put the results in a table, in seconds and in years.

Tools: A calculator or spreadsheet (use powers of $10$ for the large numbers); optionally a few lines of Python.

Hand in: Your table, the factor from step 2, and a short paragraph recommending a password policy for your school's online portal, justified by your counts.

Going further. Real users do not choose uniformly at random: they prefer words, names and years. How would this change your conclusions? Look up the idea of password "entropy", measured in bits as $\log_2$ of the size of the search space.

Instructor note: the key numbers are $10^4$, $10^6$, $26^8\approx2.1\times10^{11}$, $94^8\approx6.1\times10^{15}$ and $7776^4\approx3.7\times10^{15}$; the no-repeat rule multiplies the $94$-character space by ${}^{94}P_8/94^8\approx0.74$, i.e. it reduces it. Students usually expect "more rules = safer"; the counts show that length matters far more than rules, which is a good discussion of the multiplication principle.

๐Ÿงช Self-check quiz

0/5 correct

Q1. The value of $0!$ is

Q2. If ${}^{n}P_{2}=56$, then $n$ equals

Q3. The number of different arrangements of the letters of $\text{NOON}$ is

Q4. In how many ways can $5$ friends sit around a round table (seats not numbered)?

Q5. The number of three-letter codes that can be made from the $26$ letters if letters may be repeated is