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.
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.
- Draw the slots to be filled (places in a number, seats, positions in a word) and write the number of options under each.
- 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.
- 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.
- For "at least oneโฆ" it is often quicker to count the complement: all outcomes minus those with none.
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.
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$.
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.
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.
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$?
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.
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$.
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.
- 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.
- 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.
- Fixed places โ fill them first, then arrange the rest.
- "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.
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.)
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!$.
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?
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.
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.
- 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 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 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 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?
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$
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.
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$
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.
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$
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.
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.
- 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.
- 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$?
- Count $8$-character passwords from the $94$ characters that contain at least one digit, using the complement (all minus those with no digit).
- 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.
๐งช Self-check quiz
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