Chapter 4 ยท Introduction

Chapter 4 โ€” Permutations and Combinations

How many ways? Arrangements, where order matters, and selections, where it does not โ€” the fundamental principle of counting, ${}^{n}P_{r}$ and ${}^{n}C_{r}$, and the techniques that turn a counting question into a short calculation.

Shuffle an ordinary pack of $52$ playing cards well. The order you are holding has almost certainly never existed before in the history of the world, and will never exist again. That sounds like an exaggeration until you count: the number of possible orders is $52!$, a number with $68$ digits. If every person who has ever lived had shuffled a pack once a second since the beginning of the universe, they would not have come remotely close to producing every order even once. Counting can reveal facts that no amount of listing ever could.

The mathematics of counting โ€” combinatorics โ€” was developed by gamblers, astronomers and code-makers, from the Indian mathematicians who counted metres in poetry and the possible flavours from a set of spices, to Pascal and Fermat working out how to share the stakes of an unfinished game. Today it underlies probability and statistics, the design of passwords and error-correcting codes, the scheduling of tournaments and timetables, and the analysis of algorithms. In JEE Main it appears directly in one or two questions every year, and it is the engine of the binomial theorem (Chapter 5) and of probability (Chapter 13). Section 4.1 builds everything from the fundamental principle of counting and counts arrangements (permutations); Section 4.2 counts selections (combinations) and applies them to committees, geometry, groups and distributions.

Multiply / addโ†’$n!$โ†’${}^{n}P_{r}$โ†’Repeated objectsโ†’Round tables, rankโ†’${}^{n}C_{r}$โ†’Pascal's ruleโ†’Conditions, geometryโ†’Stars and bars
๐ŸŽฏ By the end of this chapter you canโ€ฆ
  • use the multiplication and addition principles, filling the most restricted place first and splitting into cases when the options depend on earlier choices;
  • work with factorials and with ${}^{n}P_{r}=\tfrac{n!}{(n-r)!}$, including arrangements with repetition ($n^r$) and equations in $n$ and $r$;
  • count arrangements of objects that are not all different, $\tfrac{n!}{p_1!\,p_2!\cdots}$, and arrangements with "together", "never together" and fixed-place conditions;
  • count circular arrangements, $(n-1)!$ and $\tfrac{(n-1)!}{2}$, and find the rank of a word in dictionary order;
  • use ${}^{n}C_{r}=\tfrac{n!}{r!(n-r)!}$ with its properties (symmetry, Pascal's rule) and decide whether a problem asks for a selection or an arrangement;
  • count selections with conditions ("at least", "at most", particular objects included or excluded), all selections, and divisors of a number;
  • count lines, triangles, diagonals and parallelograms, allowing for collinear points;
  • divide objects into groups, and count integer solutions of $x_1+\cdots+x_k=n$ by stars and bars;
  • solve JEE Main multiple-choice and numerical-answer problems on the whole unit.

A computer lists every possible order of $20$ students in a queue, at one billion orders per second. Roughly how long does it take?

Set $n=20$. The readouts show $20!\approx2.43\times10^{18}$ orders, and at $10^9$ per second that is about $2.4\times10^{9}$ seconds โ€” roughly $77$ years. Compare $n^2=400$ and $2^n\approx10^6$ in the bars: the factorial outgrows every power. Move to $n=13$ and the same list takes only about $6$ seconds; at $n=25$ it would take about $490$ million years. That is why we count arrangements with formulas instead of listing them.
Teaser โ€” The Factorial Explosion

How fast does the number of arrangements $n!$ grow? The bars compare $n^2$, $2^n$ and $n!$ on a logarithmic scale โ€” each grid step is ten times the one before. The readouts say how long a computer that lists one billion arrangements per second would need to list all $n!$ of them. Press Play to let $n$ grow, or jump straight to a shuffled pack of cards.

20
$n!$โ€”
digits in $n!$โ€”
time to list at $10^9$/sโ€”

Sections in this chapter

๐ŸŽฏ Chapter mixed test JEE Main ยท MCQJEE Main ยท Numerical

Eight problems that mix both sections, in no particular order โ€” just as they come in the paper, where nothing tells you whether a question wants arrangements or selections. Answer each one and press Submit (NTA marking: $+4$ correct, $-1$ wrong, $0$ unanswered), or press โฑ Take as a timed test for the real-exam experience: $8$ questions at the JEE Main pace of $2.4$ minutes each, with the NTA question palette.

E1. JEE Main ยท MCQ The number of arrangements of the letters of the word $\text{ARRANGE}$ in which the two $R$'s are not next to each other is (A) $900$ (B) $1260$ (C) $360$ (D) $720$

All A and R twice each, N, G, E once: $\dfrac{7!}{2!\,2!}=1260$.
R's together Glue $RR$: $6$ objects with A twice: $\dfrac{6!}{2!}=360$.
Answer (A) $1260-360=900$.
โฑ Shortcut Gap method: arrange A, A, N, G, E in $\tfrac{5!}{2!}=60$ ways; choose $2$ of the $6$ gaps for the alike R's: ${}^{6}C_{2}=15$; $60\times15=900$.

E2. JEE Main ยท Numerical Find the number of four-digit numbers whose digits are strictly increasing from left to right (for example $1358$). Give the answer to the nearest integer.

Idea Choose any $4$ different digits; there is exactly one way to write them in increasing order. A selection, not an arrangement.
No zero If $0$ were chosen it would have to come first, which is not allowed; so choose from $1$โ€“$9$: ${}^{9}C_{4}$.
Answer $126$.

E3. JEE Main ยท MCQ Five boys and five girls sit around a round table so that boys and girls alternate. The number of ways is (A) $2\cdot5!\cdot5!$ (B) $4!\cdot4!$ (C) $4!\cdot5!$ (D) $5!\cdot5!$

Boys Seat the boys round the table: $(5-1)!=4!$ ways. This fixes the circle.
Girls The $5$ gaps between boys are now distinguishable seats: $5!$ ways.
Answer (C) $4!\cdot5!=2880$.
โฑ Shortcut Only the first group seated round a table gets $(n-1)!$; once the circle is fixed, everything else is a row.

E4. JEE Main ยท Numerical Three vertices of a regular $12$-sided polygon are chosen. Find the number of choices for which the three vertices form a right-angled triangle. Give the answer to the nearest integer.

Geometry The vertices lie on a circle; a triangle inscribed in a circle has a right angle exactly when one side is a diameter.
Count $12$ vertices form $6$ diametrically opposite pairs; each diameter combines with any of the other $10$ vertices: $6\times10$.
Answer $60$.

E5. JEE Main ยท MCQ A committee of $4$ is chosen from $5$ married couples so that no couple serves together. The number of committees is (A) $210$ (B) $120$ (C) $60$ (D) $80$

Couples The $4$ members come from $4$ different couples: ${}^{5}C_{4}=5$ ways to choose the couples.
Partners From each chosen couple take the husband or the wife: $2^4=16$.
Answer (D) $5\times16=80$.
โฑ Shortcut (A) ${}^{10}C_{4}$ ignores the condition. Choosing "units" first (couples), then one member from each unit, is a pattern worth remembering.

E6. JEE Main ยท Numerical Find the number of five-digit numbers divisible by $4$ that use each of the digits $0,1,2,3,4$ exactly once. Give the answer to the nearest integer.

Endings Last two digits (different, from $0$โ€“$4$) divisible by $4$: $04, 12, 20, 24, 32, 40$.
Endings with 0 $04$, $20$, $40$: the other three digits are non-zero, $3!=6$ each: $18$.
Endings without 0 $12$, $24$, $32$: the remaining three digits include $0$, which cannot lead: $3!-2!=4$ each: $12$.
Answer $18+12=30$.

E7. JEE Main ยท MCQ The number of ordered triples $(x,y,z)$ of positive integers with $xyz=30$ is (A) $9$ (B) $27$ (C) $10$ (D) $6$

Primes $30=2\cdot3\cdot5$. Each of the three primes goes to exactly one of $x$, $y$, $z$ (a variable that gets none of them is $1$).
Count $3$ choices for each prime: $3\times3\times3$.
Answer (B) $27$.
โฑ Shortcut For $N=p^aq^b\cdots$ the number of ordered triples is ${}^{a+2}C_{2}\cdot{}^{b+2}C_{2}\cdots$ (stars and bars for each exponent); here $3\cdot3\cdot3$.

E8. JEE Main ยท Numerical In how many ways can $10$ identical balls be placed in $4$ different boxes so that no box is empty? Give the answer to the nearest integer.

Model Positive integer solutions of $x_1+x_2+x_3+x_4=10$.
Stars and bars ${}^{10-1}C_{4-1}={}^{9}C_{3}$.
Answer $84$.
โœ… Before you start
This chapter needs very little algebra but a clear head about sets. From Section 1.1: the number of elements of a Cartesian product, $n(A\times B)=n(A)\,n(B)$, which is the multiplication principle in disguise; the $2^n$ subsets of an $n$-element set; and the counting formula $n(A\cup B)=n(A)+n(B)-n(A\cap B)$, which is behind every "complement" argument. From Section 1.2: the counts $n^m$ of all functions and $n(n-1)\cdots(n-m+1)$ of one-one functions โ€” you will meet them again as $n^r$ and ${}^{n}P_{r}$. Comfort with cancelling fractions of factorials ($\tfrac{10!}{8!}=90$) and with small powers will make the calculations quick. If you have not yet read the welcome page, start there: it explains how the quick checks, predictions, speed drills and Exam corners in every section work.