IN REVIEW

In review — free for everyone. While a book is in review you are one of its reviewers: read it, use it, and tell us what is wrong. When the reports settle, the Class 11 pass is ₹999 for the year and this book’s PDF is ₹299.

One question decides everything

◆FRAME

Three friends — Asha, Bilal and Chen — and two things to do with them.

FIRST, pick two of them to be joint captains. List the possibilities. Asha and Bilal. Asha and Chen. Bilal and Chen. Three ways.

Is “Bilal and Asha” a fourth? No. That is the same pair said in a different order, and the pair is what was asked for.

SECOND, pick one to be captain and one to be vice-captain. List again. Asha as captain with Bilal deputy is one outcome; Bilal as captain with Asha deputy is another, because the two people now hold different jobs. Working through all of them gives six ways, not three.

Same three people, same “choose two”, and the answers differ by a factor of two.

What separated them was one question: DOES ORDER MATTER?

When it does, each arrangement is its own outcome and you are counting PERMUTATIONS. When it does not, only the group counts and you are counting COMBINATIONS.

Every formula in this chapter is an answer to that question. Getting the question wrong does not give an approximately right count. It gives one that is wrong by a definite factor, and nothing in the working looks amiss.

Read the problem for the question first and reach for a formula second.

Nothing changes between each row and the line under it except the order, so the order is the only thing that can be causing the different verdict. Take the habit rather than the two examples: before reaching for any formula in this chapter, decide which of these two systems the problem is describing. Every wrong answer ahead comes from answering that question wrongly, not from the arithmetic.
Read the lower row across and every chip of the upper row appears in it twice, once each way round. That doubling is the factor of two the frame names, and it is visible here rather than asserted. Count both rows for yourself before reading on — the rest of the chapter is four formulas for doing this counting when the lists are too long to write out.

↑ Back to top

Multiplying choices across stages

●KEY-TERM

The FUNDAMENTAL PRINCIPLE OF COUNTING, also called the multiplication principle, sits underneath everything else in the chapter.

It says this. Suppose one task can be done in $m$ ways. Suppose that, after it is done, a second task can be done in $n$ ways. Then the two together can be done in $m \times n$ ways.

The reason is worth seeing rather than accepting. Each of the $m$ ways of doing the first task opens up the full set of $n$ ways of doing the second. So there are $n$ outcomes hanging off the first choice, $n$ more off the second, and so on through all $m$ of them. Adding $n$ to itself $m$ times is $m \times n$.

The principle extends to as many stages as you like. Three tasks in succession with $m$, $n$ and $p$ choices give $m \times n \times p$ outcomes. Multiply the choices available at each stage and you have the total.

The words to listen for are AND THEN. This task AND THEN that one. That phrasing is what allows the multiplication.

Count the stages, count the choices at each, multiply. Most counting problems are this principle in a disguise.

Every stage fans each cycle that already exists into as many new ones as it offers, so the tiers run 4, then 12, then 24. Adding the stages would give 9. When a problem has three or more steps, count the fan-out at each and multiply.
A 3-by-4 grid of dots, one per shirt-and-trousers outfit: 12 dots in all.

A café offers 4 starters and 5 mains. How many starter-and-main meals are possible?

Two stages: choose a starter, and then choose a main.

Stage one has 4 choices. Whichever starter you took, stage two still has all 5 mains available — picking a starter does not remove a main from the menu.

So the count is $4 \times 5 = 20$.

If listing feels safer, list the first row. Starter 1 pairs with main 1, main 2, main 3, main 4, main 5 — five meals. Starter 2 does the same, another five. Four starters at five meals each is twenty meals.

Notice what is NOT being asked. Nobody is choosing between having a starter and having a main. Both are taken, one after the other, which is exactly the AND THEN the multiplication principle needs.

Twenty meals out of nine dishes. Multiplying stages grows a menu much faster than adding dishes does.

The multiplication is drawn rather than asserted: every starter reaches every main, so the twenty lines on the page are the twenty meals. Cover the fan and the same question returns as arithmetic — how many lines would a fifth starter add? Five more, because a starter’s line count is set by the stage after it, not by the stage it is in.

↑ Back to top

Adding choices across alternatives

▲CONCEPT

Not every count multiplies. The other case is when the choices are ALTERNATIVES rather than stages.

The ADDITION PRINCIPLE covers it. Say a task can be done in one of several MUTUALLY EXCLUSIVE ways. A first method gives $m$ outcomes, a second gives $n$, and no outcome is reachable by both. Then the total is $m + n$.

The distinction is a matter of words in the problem, and there are two to listen for.

AND THEN means stages. Do this, then do that, and both happen. That multiplies.

EITHER-OR means alternatives. Do this or do that, but not both. That adds.

The phrase “mutually exclusive” is doing real work in the statement. If an outcome can be reached both ways, adding counts it twice and the total comes out too big. The two lists have to be genuinely separate before their sizes may be added.

Getting this backwards is not a near miss. Four starters and five mains gives 20 meals but only 9 single dishes, and those two numbers answer completely different questions.

Ask whether both things happen or only one. Both happen means multiply. Only one means add.

The two brackets are each club’s own honest count, and they cover chips 4 and 5 twice between them. That is the whole of the mutually-exclusive condition, and it is why the rule is stated with a condition attached rather than as plain arithmetic. Use it as a check: before adding two counts, look for an item that both counts would claim.

A student will read ONE book, chosen either from a shelf of 3 novels or from a shelf of 2 biographies. How many choices are there?

Test the two conditions before counting.

Are the options mutually exclusive? Yes. No book is both a novel and a biography, so the two shelves share nothing.

Do both happen? No. The student takes one book, not one from each shelf.

So this is either-or, and the counts add: $3 + 2 = 5$.

Listing confirms it. Novel 1, novel 2, novel 3, biography 1, biography 2 — five books, and the student can end up with any one of them.

Compare it with the café. There a meal needed a starter AND THEN a main, so $4 \times 5 = 20$. Here the reader takes one book from EITHER shelf, so $3 + 2 = 5$.

Change the question to one novel and then one biography, both to be read, and it multiplies again: $3 \times 2 = 6$.

The same two shelves give 5 or 6 depending only on the connecting word. Read the word.

The tell is that there is only one row. A multiplying question needs two stages to pair off against each other, and there is no second stage here — one book leaves the shelf, and the five boxes are already the five ways it can happen. The gap does the rest of the work: no book is on both shelves, so no choice is counted twice.

↑ Back to top

Factorials

●KEY-TERM

Arranging things produces one particular kind of product often enough to earn its own symbol.

For a positive integer $n$, $n!$ — read “n factorial” — is the product of every integer from $n$ down to 1: $n! = n \times (n-1) \times (n-2) \times \ldots \times 2 \times 1$.

Where it comes from is the multiplication principle. To arrange $n$ distinct objects in a row, there are $n$ choices for the first place. One object has now been used, so the second place has $n-1$ choices, the third has $n-2$, and so on down to a single choice for the last. Multiply them all and you have $n!$.

Factorials grow ferociously. $5! = 120$, ten factorial is already 3,628,800, and twenty factorial passes two quintillion.

One value is set by convention rather than by the product: $0! = 1$. Not 0. That looks arbitrary and it is not. With $0! = 1$ the permutation and combination formulas keep working in the case where nothing is left over to arrange; fixing it at 0 would put a zero in a denominator and break them.

*$n!$ is the multiplication principle applied to arranging everything. The shrinking choices are where each factor comes from.*

Worked example

Evaluate $5!$ and simplify $5!/3!$

  1. $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$
    the first is direct.
  2. $5! = 5 \times 4 \times 3!$
    for $5!/3!$, do not evaluate both and divide — write the top so the bottom appears inside it.
  3. $(5 \times 4 \times 3!)/3! = 5 \times 4 = 20$
    the $3!$ cancels top and bottom, leaving only the top factors.
  4. $5!/(5-2)! = 5 \times 4$
    the general shape worth keeping: $n!/(n-k)!$ always cancels down to the top $k$ factors of $n!$ — this is exactly why the permutation formula in the next section is written as a ratio of factorials, the ratio already cancelled. Never evaluate two factorials in order to divide them — split the larger until the smaller appears, then cancel.
Neither factorial is ever worked out. The three dotted columns are the whole of 3 factorial sitting inside 5 factorial, and once they leave, the two chips still standing are the answer. The survivors are always a run from the top down, which is why 5 factorial over 3 factorial has exactly two factors and not three.

↑ Back to top

Permutations: order matters, nothing repeats

▲CONCEPT

Now the first of the two main formulas.

The number of PERMUTATIONS of $n$ distinct objects taken $r$ at a time — order matters, nothing repeats — is $P(n,r) = n!/(n-r)!$.

Build it from the multiplication principle and it stops looking like something to memorise. You are filling $r$ ordered positions from $n$ objects. The first position has $n$ choices. That object is now used up, so the second has $n-1$. The third has $n-2$. The last one, the $r$-th, has $n-r+1$.

Multiply those $r$ shrinking factors and you have the count. Writing it as $n!/(n-r)!$ is that same product expressed compactly — the division cancels everything below the $r$-th factor, which is exactly the part you did not want.

Two conditions are built into the formula and both matter. DISTINCT: the objects are all different from one another. NO REPEATS: once an object is used, it is gone.

The formula is shorthand for shrinking choices. If you forget it, count the positions and multiply down.

The first role can be filled three ways. Whichever candidate takes it is then unable to take the second, so every branch splits into two and not three. Three times two is six, and the six leaves are the six ordered arrangements themselves — the formula is a count of the paths through this tree.
Worked example

Count ways to choose a president and secretary from 6

  1. $6 \times 5 = 30$
    count directly: president and secretary are distinct posts (order matters) and one person cannot hold both (no repeats) — a permutation. 6 choices for president, then 5 remaining choices for secretary.
  2. $P(6,2) = 6!/4! = 6 \times 5 = 30$
    the formula agrees — the cancellation reproduces the direct count exactly, which is what it is for. When a problem names the roles, order matters: named roles are the clearest signal that you want $P(n,r)$.
The second row is drawn, not asserted, and it is the first row one chip lighter. That single missing box is the whole difference between 6 times 5 and 6 times 6, and it is why an ordered choice without repetition always falls by one at each step.

↑ Back to top

When repetition is allowed

▲CONCEPT

Drop the no-repeats condition and the count changes completely.

If repetition IS allowed — the same object may be used in more than one position — then filling $r$ ordered positions from $n$ objects gives $n^r$ ways.

The reason is that nothing gets used up. The first position has $n$ choices. The second still has all $n$, because whatever went first is still available. So does the third, and every position after it. Multiplying $n$ by itself $r$ times gives $n^r$.

Put the two cases side by side and the difference is plain. Without repetition the choices shrink: $n$, then $n-1$, then $n-2$. With repetition they do not move: $n$, then $n$, then $n$.

The gap widens fast. From 10 objects in 3 ordered positions, $P(10,3) = 720$ but $10^3 = 1000$.

Notice too that $r$ may now exceed $n$. You cannot arrange 5 distinct objects in 7 positions without repeats, but you can perfectly well build a 7-character code from 5 symbols.

*Ask whether a used object comes back. If it does, the choices stay level and the answer is $n^r$.*

A 4-by-4 grid of two-digit codes, with the four repeated-digit codes crossed out on the diagonal.
Worked example

Count 3-digit codes from 0-9 with repetition

  1. $10 \times 10 \times 10 = 10^3 = 1000$
    order matters (149 is not 941) and repetition is allowed (777 is legal) — the $n^r$ case, with $n=10$ digits and $r=3$ positions; using a digit does not consume it, so every position keeps all 10 choices.
  2. codes $000$ to $999$
    that is exactly 1000 codes — a satisfying check in itself.
  3. $P(10,3) = 10 \times 9 \times 8 = 720$
    compare the no-repeats version — the 280 codes lost are precisely the ones with a repeated digit. Repetition allowed keeps every position at full strength, which is what turns a shrinking product into a power.
The point of the picture is that there is nothing to notice: the second and third rows are copies of the first, because using a digit does not remove it. Compare it with the two-row figure on page 9, where the second row really is one chip lighter. A count is a power when the rows are copies and a falling product when they are not, and the rows are the thing to look at.

↑ Back to top

When the objects are not all different

▲CONCEPT

The third case: the objects being arranged are not all different.

Arranging $n$ objects in a row gives $n!$ — but only if they are all distinguishable. When some repeat, $n!$ OVERCOUNTS, and it is worth seeing why rather than patching it afterwards.

Suppose two of the objects are identical copies. The count $n!$ treats them as separate, so it counts an arrangement once with the first copy in a given slot and again with the second copy there. On the page those two arrangements look exactly the same. One outcome has been counted twice.

Every arrangement is overcounted by the same factor, and that uniformity is what makes the fix clean: divide it out once, at the end.

If the repeated items come in groups of sizes $p$, $q$, $r$ and so on, the number of genuinely distinct arrangements is $n!/(p! q! r!)$.

Each factorial underneath is the number of ways the copies inside one group could be shuffled among themselves without changing anything visible. Dividing removes exactly those, and nothing else.

Count as if everything were distinct, then divide out the swaps that made no difference.

Six tagged arrangements of A, D1, D2 collapsing by colour into the three visible words ADD, DAD, DDA.
Worked example

Count distinct arrangements of LEVEL

  1. $5! = 120$
    five letters, with L appearing twice and E appearing twice — if all five were different, this would be the answer, but 120 is too big since they are not.
  2. $2! \times 2! = 4$
    the two L’s could swap, and the two E’s could swap, without changing what is written on the page — every genuinely distinct word has been counted 4 times over.
  3. $5!/(2! \times 2!) = 120/4 = 30$
    divide out the overcounting — LEVEL has 30 distinct arrangements, not 120. The V needs no division, and that is consistent rather than an exception: it appears once, and $1! = 1$ changes nothing, so one factorial per repeated group, sized to that group, is all any word needs; unrepeated letters are already counted correctly.
Two coloured groups above and two division lines below, paired off one for one. That pairing is the rule people mean when they say "divide by each repeated letter’s own factorial", and it is why the lone V contributes nothing to the denominator. Stopping after one division gives 60 — the answer that has cleared the L’s and still counts every word twice for its E’s.
LEVEL has two repeats of size two, so both of its divisions are by 2 and the rule can be misread as halving once per repeated letter. Here the two divisors are 2 and 6, and the word is chosen for exactly that reason. Before dividing, write the repeat sizes down: the denominator is built from those sizes, not from how many letters are repeated.

↑ Back to top

Combinations: dividing the order back out

▲CONCEPT

Back to the frame’s question, and the other answer to it.

A COMBINATION counts SELECTIONS, where order does not matter. The number of ways to choose $r$ objects from $n$ distinct objects is $C(n,r) = n!/(r!(n-r)!)$.

That formula is not new work. It is $P(n,r)$ with one extra division, and here is the whole argument.

Start with the ordered count, $P(n,r) = n!/(n-r)!$. Take any one group of $r$ objects. How many times did $P(n,r)$ count that group? Once for every ordering of those $r$ objects among themselves, which is $r!$ times.

So the ordered count is exactly $r!$ times too big for an unordered question. Divide by $r!$ and you have

$C(n,r) = P(n,r)/r! = n!/(r!(n-r)!) \cdot$

The $r!$ in the denominator is the entire difference between the two formulas. It is there for a stated reason: it removes the orderings the question said it did not care about.

A combination is a permutation with the ordering divided back out. Remember the reason and the formula follows from it.

Each circle on the right is one selection, and the two chips feeding it are the two orders that selection can be written in. Nothing has been thrown away — the same six arrangements are still there — but they have been grouped, two to a group, because swapping two names does not change who was chosen. Dividing by two is exactly that grouping.
Worked example

Count 3-person committees from 6 people

  1. $C(6,3) = 6!/(3! \times 3!) = 720/36 = 20$
    the word committee is the signal: members hold no distinct titles, so a committee of three particular people is the same committee however you list them — order does not matter, a combination; apply the formula with $n=6$, $r=3$.
  2. $P(6,3) = 6 \times 5 \times 4 = 120$
    compare against the ordered count — six times larger, and six is not a coincidence: it is $3!$, the number of orders one committee of three could be listed in.
  3. $P(n,r)/r! = C(n,r)$
    that relationship is a good check on any combination answer. Committee, team, group, selection: no titles and no order means $C(n,r)$; named roles mean $P(n,r)$.
Count the lower row rather than trusting the factorial: six chips, and every one of them is the same three people. That is why the ordered count has to be divided, and by exactly six. Every other committee behaves identically, which is what makes one division at the end enough for all twenty.

↑ Back to top

Two identities that follow for free

▲CONCEPT

Two identities drop out of what a combination counts, and neither needs the formula to be proved.

SYMMETRY: $C(n,r) = C(n, n-r)$.

Choosing which $r$ objects to INCLUDE settles, at the same moment, which $n-r$ objects to LEAVE OUT. One decision described from either end, so the two counts must be equal. It is also useful in practice: $C(20,18)$ is awkward, and $C(20,2)$ is the same number in one line.

PASCAL’S RULE: $C(n,r) + C(n, r-1) = C(n+1, r)$.

Take the $n+1$ objects and fix attention on one of them. Every selection of $r$ objects either leaves that one out or takes it in. There is no third case, and no selection is in both groups.

Leaving it out means choosing all $r$ from the remaining $n$, which is $C(n,r)$ ways. Taking it in means choosing the other $r-1$ from the remaining $n$, which is $C(n, r-1)$ ways.

The two groups are mutually exclusive, so by the addition principle their counts add to the total, $C(n+1, r)$.

Both identities are counting arguments, not algebra. Pascal’s rule is also what builds Pascal’s triangle, which the next chapter runs on.

Ten selections of 2 from A to E, split into the four that use A and the six that do not.
Worked example

Check the symmetry identity and Pascal’s rule on real numbers

  1. $C(10,7) = C(10,3)$
    computing $C(10,7)$ head-on is doable but fiddly — use the symmetry identity instead, since $n-r=10-7=3$.
  2. $C(10,3) = (10 \times 9 \times 8)/(3 \times 2 \times 1) = 720/6 = 120$
    choosing 7 to include is the same count as choosing the 3 to leave out, and this direction is much the shorter calculation.
  3. $C(9,3)+C(9,2) = 84+36 = 120$
    Pascal’s rule, with $n=9$, $r=3$: the left side.
  4. $C(10,3) = 120$
    the right side, computed just above — they agree. When r is more than half of n, switch to $C(n,n-r)$ first: the answer is identical and the arithmetic is smaller.
There is one cut in the picture and no second act anywhere, which is the whole content of the identity: the two brackets are two names for the same decision. In practice, read the row from whichever end is shorter. When r is more than half of n, that end is always the leaving-out one.

↑ Back to top

Two questions, four formulas

■RECAP

Everything in this chapter answers the frame’s question, plus one more that came up along the way.

QUESTION ONE: does order matter? QUESTION TWO: can items repeat?

Before either, there are the two principles that combine counts. Successive stages MULTIPLY — this and then that. Mutually exclusive alternatives ADD — this or that, not both.

Then the formulas, all four settled by those two questions.

Order matters, no repetition: $P(n,r) = n!/(n-r)!$. Shrinking choices, written as a ratio.

Order matters, repetition allowed: $n^r$. Choices that never shrink, because nothing is used up.

Order matters, objects not all distinct: $n!/(p! q! r!)$, dividing out the swaps among identical copies that changed nothing visible.

Order does not matter: $C(n,r) = n!/(r!(n-r)!)$, which is $P(n,r)$ with the irrelevant orderings divided back out.

That last division is the source of everything on the combination side, symmetry and Pascal’s rule included.

Answer the two questions in words before writing any formula. The formula is then forced, and there is nothing left to guess.

Nobody loses marks for not knowing the four formulas. They lose them for reaching for the wrong one, which is a reading problem, not a memory problem. The crossing lines are the figure’s way of refusing to be a list: each description lands on one formula and only one, and which one is settled by two questions — does order matter, and can anything repeat.

↑ Back to top

Two traps this chapter sets

✕MISCONCEPTION

THE TRAP. Choosing 2 co-captains from 5 people, and choosing a captain and a vice-captain from 5 people, are the same problem. Both just pick 2 people out of 5, so both are $C(5,2)$.

THE REALITY. They differ by a factor of two. Co-captains give $C(5,2) = 10$. Captain and vice-captain give $P(5,2) = 20$.

The number chosen is identical in both, and it is not what decides anything.

CO-CAPTAINS is one unnamed, unordered pair. Two particular people as co-captains is the same outcome whichever way round you name them, because there is nothing to tell the two versions apart.

CAPTAIN AND VICE-CAPTAIN is two distinct posts. One person as captain with the other as deputy is a different arrangement from the reverse. Any pair can fill the two named posts in $2! = 2$ ways, and that 2 is exactly the ratio between the two answers.

So the deciding evidence is in the WORDS of the problem, not its numbers. Look for titles, ranks, positions, an order of finishing, a first and a second.

If the outcomes have names attached, order matters. If they are just a group, it does not.

Only the first chip is shown splitting, and that is the argument: whatever happens to 12 happens to all ten, so the answer doubles rather than needing a fresh count. The tell in a problem is whether the two seats have names. Co-captains, jury members, a hand of cards — no names, so C. Captain and vice, first and second prize, president and secretary — names, so P.
✕MISCONCEPTION

THE TRAP. LEVEL has 5 letters, so its letters can be arranged in $5! = 120$ distinct ways.

THE REALITY. 30, not 120. The count is $5!/(2! \times 2!)$, because L appears twice and E appears twice.

What goes wrong is invisible in the arithmetic. $5!$ is the count for five DISTINGUISHABLE objects, and it silently treats the two copies of L as if you could tell them apart. Under that assumption swapping them makes a new arrangement. On the page it makes the same word.

The same applies to the two copies of E. Between them, every genuinely distinct arrangement gets counted $2! \times 2! = 4$ times over, which is where the factor of 4 between 120 and 30 comes from.

The rule to carry: any repeated item needs its group’s factorial divided out, however small the repeat. Even a single repeated pair halves the answer.

The habit that catches it is a count taken before the formula. Write the letters out, note which ones appear more than once, and put a factorial underneath for each.

*A repeated letter is easy to miss because nothing in $5!$ complains. Check for repeats first, every time.*

The tags are the assumption 5! makes without saying so — that you could tell one L from the other. Take the tags off and the four rows are one row, which is the whole reason a repeat has to be divided out. The size of the division is on the page too: each repeat group contributes its own factorial, so a letter appearing three times would fold 3! = 6 listings into one, not 3.

↑ Back to top

Practice set

Exercise 6.1 — Fundamental and addition principles
  1. practice A restaurant menu offers 5 starters, 4 mains, and 3 desserts. How many different 3-course meals can be ordered, one item from each course?
  2. practice A student may travel from town A to town B by one of 3 different buses or one of 2 different trains, not both in the same trip. In how many ways can the trip be made?
Answers
  1. $5 \times 4 \times 3 = 60$
  2. $3+2=5$
Both of Exercise 6.1's answers are one line of arithmetic. The marks go on knowing which line to write, and that is settled by a word in the question, not by a number: and, each, then join stages into one outcome and multiply; or, either, not both offer alternatives and add. The usual slip on the second question is 3 × 2 = 6 — a count of bus-and-train pairs, and the question says no trip uses both.
Exercise 6.2 — Factorials and P(n,r)
  1. practice Evaluate $8!/6!$.
  2. practice How many ways can a chairperson and a treasurer, two distinct named roles, be chosen in order from 7 candidates, with no one holding both posts?
    1. $42$
    2. $49$
    3. $21$
    4. $7$
Answers
  1. $8 \times 7 = 56$
  2. $42$
Exercise 6.3 — Repetition allowed and non-distinct objects
  1. practice How many 4-digit codes can be formed from the digits 0-9 if digits may repeat?
  2. practice How many 3-letter strings can be formed from the 26 letters of the alphabet if letters may repeat?
  3. practice How many distinct arrangements does the word “STATISTICS” have?
  4. practice How many distinct arrangements does the word “APPLE” have?
    1. $60$
    2. $120$
    3. $24$
    4. $30$
Answers
  1. $10^4 = 10000$
  2. $26^3 = 17576$
  3. $10!/(3! \times 3! \times 2!) = 50400$
  4. $60$
Exercise 6.4 — Combinations
  1. practice How many 4-person committees can be formed from 9 people?
  2. practice If $C(n,2) = 21$, find $n$.
    1. $7$
    2. $6$
    3. $8$
    4. $5$
  3. practice Use the symmetry identity to evaluate $C(12,10)$ without expanding $12!$ directly.
Answers
  1. $C(9,4) = 126$
  2. $7$
  3. $C(12,10) = C(12,2) = 66$
Exercise 6.4 is small combinations, and every one of them is already sitting in this array — so read the answer off it, then check the value you worked out by formula against it. The three tinted discs are the reason the array can be trusted and extended: an entry is the two above it added, which is Pascal’s rule, so a row past n equals 6 costs one line of addition rather than a fresh calculation.
Each pair is filed under its smaller member, so no pair can appear in two rows and none can be missed. The row lengths then have to fall by one, which is why the answer to any C(n,2) question is a triangular number and why the top row is one shorter than the number of people. Reach for the staircase when a question gives you the count and asks for n.
Miscellaneous — practice set
  1. practice A cricket team of 11 is to be chosen from 15 players. In how many ways can this be done?
  2. practice In how many ways can the letters of the word “BANANA” be arranged?
  3. practice A committee needs a president and a secretary, two distinct named roles, chosen from 6 members, with no one holding both roles. Which count applies?
    1. $P(6,2)$
    2. $C(6,2)$
    3. $6^2$
    4. $6!$
Answers
  1. $C(15,11) = C(15,4) = 1365$
  2. $6!/(3! \times 2!) = 60$
  3. $P(6,2)$

↑ Back to top

Chapter-end problems

Chapter-end problems — graded set
  1. board-easy A person owns 5 shirts and 3 ties. In how many ways can one shirt and one tie be worn together?
  2. board-easy A student may choose one fruit from 4 apples or 3 mangoes. In how many ways?
  3. board-easy Evaluate $5!$.
  4. board-easy Evaluate $7!/5!$.
  5. board-easy Find $P(6,2)$, the number of ways to fill 2 ordered posts from 6 people.
  6. board-easy A flag has 3 stripes, top, middle and bottom, each a different colour chosen from 5 available colours. How many flags are possible?
  7. board-easy How many 3-letter codes (repetition allowed) can be formed from 4 letters?
  8. board-easy In how many ways can the letters of the word LEVEL be arranged?
  9. board-easy Find $C(6,2)$, the number of 2-person selections from 6 people.
  10. board-easy Which of these equals $C(10,8)$?
    1. $45$
    2. $90$
    3. $36$
    4. $56$
  11. board-standard How many 4-digit numbers can be formed from the digits 1–9, no digit repeated?
Answers
  1. $15$
  2. $7$
  3. $120$
  4. $42$
  5. $30$
  6. $60$
  7. $64$
  8. $30$
  9. $15$
  10. $45$
  11. $3024$
Item 12 hangs its condition on the thousands slot; item 21 hangs one on the units slot (must be even) and item 25 on the units slot again (must be 5). Find the conditioned slot and fill it before counting anything, and what is left is an ordinary ordered choice.
Chapter-end problems — graded set (continued)
  1. board-standard How many 4-digit numbers greater than 5000 can be formed from $1,2,3,5,7$, no digit repeated?
  2. board-standard In how many ways can 5 different books be arranged in a row on a shelf?
  3. board-standard 3 boys and 2 girls sit in a row with the 2 girls always together. In how many ways?
  4. board-standard In how many ways can the letters of the word APPLE be arranged?
  5. board-standard In how many ways can a committee of 4 be chosen from 10 people?
    1. $210$
    2. $5040$
    3. $120$
    4. $105$
  6. board-standard A cricket team of 11 is chosen from 15 players, with 2 particular players always included. In how many ways?
  7. board-standard How many diagonals does a hexagon (6 sides) have?
    1. $9$
    2. $15$
    3. $6$
    4. $12$
  8. board-standard Using Pascal’s rule, find $C(7,2)$ from $C(6,2)$ and $C(6,1)$.
  9. board-standard In how many ways can the letters of the word MISSISSIPPI be arranged?
  10. board-standard How many 3-digit even numbers can be formed from digits 1–6, no digit repeated?
    1. $60$
    2. $90$
    3. $36$
    4. $20$
  11. board-standard In how many ways can a president, secretary and treasurer be chosen from 8 candidates?
  12. JEE In how many ways can the letters of the word ARRANGE be arranged?
  13. JEE From 5 men and 6 women, a committee of 5 is formed with at least 3 women. In how many ways?
  14. JEE How many 5-digit numbers divisible by 5 can be formed from digits 1–9, no digit repeated?
  15. JEE 10 people sit in a row with 4 particular people always together. In how many ways?
  16. JEE How many diagonals does a polygon with 12 sides have?
    1. $54$
    2. $66$
    3. $33$
    4. $132$
  17. JEE In how many ways can 12 different books be split between 2 named students, 6 each?
  18. JEE A test has 10 questions; a student must answer exactly 8, with questions 1 and 2 compulsory. In how many ways can the other 6 be chosen?
  19. JEE Find $n$ if $P(n,4) = 20 \times P(n,2)$.
Answers
  1. $48$
  2. $120$
  3. $48$
  4. $60$
  5. $210$
  6. $715$
  7. $9$
  8. $21$
  9. $34650$
  10. $60$
  11. $336$
  12. $1260$
  13. $281$
  14. $1680$
  15. $120960$
  16. $54$
  17. $924$
  18. $28$
  19. $n=7$
The same shortcut carries to every C(n,r) problem in this exercise set: check whether r or n−r is smaller and rewrite in those terms before multiplying anything out. C(12,10) becomes C(12,2), and C(14,11) becomes C(14,3) — both trade most of their factors away for exactly the same count, the same trade this bar makes at every point except the centre.
The usual wrong answer to this problem is C(15,11), and the picture shows why it is wrong rather than merely different: the two green chips are not being chosen. Whenever a problem fixes some members in advance, subtract them from BOTH numbers before doing anything else — from the seats and from the candidates.

↑ Back to top

JEE-application problems

The bank does not tell you which formula an item wants, so the first move on every item is deciding what is being counted — and here it is not diagonals. It is pairs of corners, of which a diagonal is one kind and a side is the other. Once the objects are pairs, the count is C(n,2) and the word diagonal is a condition to subtract, never a new formula to remember: C(n,2) − n for any n-sided polygon.
JEE-application problems — from the item bank
  1. A game show gives gold, silver and bronze rankings to 3 of 8 finalists. In how many ways can this be done?
    1. 336
    2. 56
    3. 512
    4. 24
    Check your answer
    1. ✓ 336 — (A) $P(8,3) = 8!/5! = 8 \times 7 \times 6 = 336$ — three named ranks, order matters.
    2. 56 — 56 is $C(8,3)$ — gold, silver and bronze are three different posts, so order matters.
    3. 512 — 512 is $8^3$ — this uses each finalist only once, not with repetition.
    4. 24 — 24 is $8 \times 3$ — the three posts do not shrink the choices this way.
  2. In how many ways can a class of 10 elect a president and a vice-president?
    1. 90
    2. 45
    3. 100
    4. 19
    Check your answer
    1. ✓ 90 — (A) $P(10,2) = 10!/8! = 10 \times 9 = 90$ — two named posts, order matters.
    2. 45 — 45 is $C(10,2)$ — president and vice-president are different posts, so order matters.
    3. 100 — 100 is $10^2$ — the same student cannot hold both posts.
    4. 19 — 19 is $10+9$ — the two stages combine by multiplying, not adding.
Run the product on to 1 and you have written 9 factorial, 362880 — which is exactly the wrong answer the ranking item below offers. The stopping rule is something you can count rather than recall: r factors, starting at n.
336 and 6720 are the same calculation stopped after only one of the two divisions, and 40320 is it stopped before either. Both denominator factorials apply, in either order, and 56 is the only corner that has taken both.
JEE-application problems — continued
  1. In how many ways can the top 5 finishers (1st through 5th) be ranked among 9 runners?
    1. 126
    2. 59049
    3. 15120
    4. 362880
    Check your answer
    1. 126 — 126 is $C(9,5)$ — a 1st-to-5th ranking is ordered, not a plain selection.
    2. 59049 — 59049 is $9^5$ — each runner can finish in only one position.
    3. ✓ 15120 — (C) $P(9,5) = 9!/4! = 9 \times 8 \times 7 \times 6 \times 5 = 15120$.
    4. 362880 — 362880 is $9!$ — the product should stop after 5 falling factors, not run to 1.
  2. A cricket board fills 4 distinct roles (captain, vice-captain, wicketkeeper, all-rounder) from 7 shortlisted players. In how many ways?
    1. 840
    2. 35
    3. 2401
    4. 28
    Check your answer
    1. ✓ 840 — (A) $P(7,4) = 7!/3! = 7 \times 6 \times 5 \times 4 = 840$ — four named roles, order matters.
    2. 35 — 35 is $C(7,4)$ — captain, vice-captain, wicketkeeper and all-rounder are four distinct roles.
    3. 2401 — 2401 is $7^4$ — each shortlisted player can fill at most one role.
    4. 28 — 28 is $7 \times 4$ — the four roles do not shrink the choices this way.
  3. In how many ways can a jury of 4 be selected from 12 candidates?
    1. 11880
    2. 495
    3. 330
    4. 220
    Check your answer
    1. 11880 — 11880 is $P(12,4)$ — a jury has no titles, so order does not matter here.
    2. ✓ 495 — (B) $C(12,4) = 12!/(4! \times 8!) = 495$ — a jury has no distinct titles, a combination.
    3. 330 — 330 is $C(11,4)$ — the question has 12 candidates, not 11.
    4. 220 — 220 is $C(12,3)$ — the question asks for a jury of 4, not 3.
  4. A librarian selects 3 books to donate from a shelf of 9. In how many ways?
    1. 84
    2. 504
    3. 56
    4. 36
    Check your answer
    1. ✓ 84 — (A) $C(9,3) = 9!/(3! \times 6!) = 84$ — a selection of books, no order.
    2. 504 — 504 is $P(9,3)$ — donated books form a set, with no order among them.
    3. 56 — 56 is $C(8,3)$ — the shelf holds 9 books, not 8.
    4. 36 — 36 is $C(9,2)$ — the librarian donates 3 books, not 2.
  5. In how many ways can a debate team of 5 be picked from 15 students?
    1. 360360
    2. 2002
    3. 3003
    4. 1365
    Check your answer
    1. 360360 — 360360 is $P(15,5)$ — a debate team carries no ranked posts, so order does not matter.
    2. 2002 — 2002 is $C(14,5)$ — the question has 15 students, not 14.
    3. ✓ 3003 — (C) $C(15,5) = 15!/(5! \times 10!) = 3003$ — a team, no ranking among its members.
    4. 1365 — 1365 is $C(15,4)$ — the team needs 5 members, not 4.
  6. In how many ways can a student choose 6 questions to answer from a paper of 10?
    1. 151200
    2. 84
    3. 252
    4. 210
    Check your answer
    1. 151200 — 151200 is $P(10,6)$ — the chosen questions form a set, not an ordered list.
    2. 84 — 84 is $C(9,6)$ — the paper has 10 questions, not 9.
    3. 252 — 252 is $C(10,5)$ — the student answers 6 questions, not 5.
    4. ✓ 210 — (D) $C(10,6) = 10!/(6! \times 4!) = 210$ — which questions are chosen, not their order.
  7. A 4-digit PIN uses digits 0–9, with repetition allowed. How many PINs are possible?
    1. 10000
    2. 5040
    3. 210
    4. 100000
    Check your answer
    1. ✓ 10000 — (A) $10^4 = 10000$ — every position has all 10 digits again, unused or not.
    2. 5040 — 5040 is $P(10,4)$ — a PIN may reuse the same digit in different positions.
    3. 210 — 210 is $C(10,4)$ — a PIN is an ordered string of digits, not a set.
    4. 100000 — 100000 is $10^5$ — the PIN has 4 digits, not 5.
  8. A 3-symbol code is formed from 5 symbols, with repetition allowed. How many codes are possible?
    1. 60
    2. 125
    3. 10
    4. 625
    Check your answer
    1. 60 — 60 is $P(5,3)$ — a code may reuse the same symbol in different positions.
    2. ✓ 125 — (B) $5^3 = 125$ — every position has all 5 symbols again, unused or not.
    3. 10 — 10 is $C(5,3)$ — a code is an ordered string, not a set of symbols.
    4. 625 — 625 is $5^4$ — the code has 3 symbols, not 4.
  9. In how many ways can the letters of BANANA be arranged?
    1. 60
    2. 720
    3. 120
    4. 360
    Check your answer
    1. ✓ 60 — (A) $6!/(3! \times 2!) = 720/12 = 60$ — 6 letters, A repeated 3 times, N repeated 2 times.
    2. 720 — 720 is plain $6!$ — BANANA repeats A three times and N twice, both must be divided out.
    3. 120 — 120 is $6!/3!$ — the 2 repeated Ns still need their own $2!$ in the divisor.
    4. 360 — 360 is $6!/2!$ — the 3 repeated As still need their own $3!$ in the divisor.
  10. In how many ways can the letters of STATISTICS be arranged?
    1. 3628800
    2. 100800
    3. 302400
    4. 50400
    Check your answer
    1. 3628800 — 3628800 is plain $10!$ — STATISTICS repeats S, T and I, all must be divided out.
    2. 100800 — 100800 is $10!/3!$ — S, T and I each repeat and each needs its own factorial.
    3. 302400 — 302400 is $10!/(3! \times 2!)$ — this is missing the divisor for the second repeated letter.
    4. ✓ 50400 — (D) $10!/(3! \times 3! \times 2!) = 50400$ — 10 letters, S and T each 3 times, I twice.
  11. In how many ways can the letters of COMMITTEE be arranged?
    1. 45360
    2. 362880
    3. 90720
    4. 181440
    Check your answer
    1. ✓ 45360 — (A) $9!/(2! \times 2! \times 2!) = 45360$ — 9 letters, C, M and T each repeated twice.
    2. 362880 — 362880 is plain $9!$ — COMMITTEE repeats C, M and T, all must be divided out.
    3. 90720 — 90720 is $9!/(2! \times 2!)$ — this is missing the divisor for the third repeated letter.
    4. 181440 — 181440 is $9!/2!$ — two more repeated letters still need their own $2!$ each.
  12. How many diagonals does a 9-sided polygon have?
    1. 36
    2. 27
    3. 9
    4. 54
    Check your answer
    1. 36 — 36 is $C(9,2)$ alone — every side is also a vertex pair and must be removed.
    2. ✓ 27 — (B) $C(9,2) - 9 = 36 - 9 = 27$ — all vertex pairs, minus the 9 sides.
    3. 9 — 9 is the number of sides, not the number of diagonals.
    4. 54 — 54 doubles the correct count — recheck the subtraction, not a multiplication.
  13. Given $C(14,3) = 364$, find $C(14,11)$ without recomputing the factorial.
    1. 165
    2. 728
    3. 364
    4. 1001
    Check your answer
    1. 165 — 165 is $C(11,3)$ — this swaps the roles of the chosen and left-out counts.
    2. 728 — 728 doubles the correct value — the symmetry gives an equal count, not double.
    3. ✓ 364 — (C) $C(14,11) = C(14,3) = 364$ — choosing 11 to include settles 3 to leave out.
    4. 1001 — 1001 is $C(14,4)$ — the left-out count here is $14-11=3$, not 4.
  14. A student picks one elective from 5 arts, 4 science or 3 commerce subjects. In how many ways?
    1. 60
    2. 12
    3. 9
    4. 17
    Check your answer
    1. 60 — 60 is $5 \times 4 \times 3$ — only one elective is chosen, not one from each group.
    2. ✓ 12 — (B) $5+4+3 = 12$ — one elective from mutually exclusive groups, so the counts add.
    3. 9 — 9 is $5+4$ — the 3 commerce subjects were left out of the total.
    4. 17 — 17 is $5+4 \times 3$ — every alternative must simply be added, not multiplied.
  15. From 6 men and 5 women, a committee of 4 is formed with at least 2 women. In how many ways?
    1. 150
    2. 330
    3. 265
    4. 215
    Check your answer
    1. 150 — 150 covers only the exactly-2-women case — the 3-women and 4-women cases still count.
    2. 330 — 330 is $C(11,4)$ — this drops the gender constraint entirely.
    3. 265 — 265 is “at most 2 women” — the question asks for “at least” 2.
    4. ✓ 215 — (D) $C(5,2)C(6,2)+C(5,3)C(6,1)+C(5,4)C(6,0) = 150+60+5 = 215$ — sum every women-count from 2 up.
  16. Evaluate $8!/(5! \times 3!)$.
    1. 56
    2. 336
    3. 6720
    4. 40320
    Check your answer
    1. ✓ 56 — (A) $8!/(5! \times 3!) = 40320/720 = 56$ — both denominator factorials apply together.
    2. 336 — 336 is $8!/5!$ — the $3!$ in the denominator was never applied.
    3. 6720 — 6720 is $8!/3!$ — the $5!$ in the denominator was never applied.
    4. 40320 — 40320 is plain $8!$ — neither denominator factorial was applied.
  17. Find $n$ if $P(n,2) = 110$.
    1. 10
    2. 12
    3. 11
    4. 55
    Check your answer
    1. 10 — 10 does not satisfy $n(n-1)=110$ exactly — check: $10 \times 9 = 90$, not 110.
    2. 12 — 12 overshoots — check: $12 \times 11 = 132$, not 110.
    3. ✓ 11 — (C) $P(n,2) = n(n-1) = 110$, and $11 \times 10 = 110$, so $n=11$.
    4. 55 — 55 comes from halving 110, not from factoring $n(n-1)=110$.
  18. A team of 5 is chosen from 12 players with 3 particular players always included. In how many ways?
    1. 792
    2. 36
    3. 126
    4. 66
    Check your answer
    1. 792 — 792 is $C(12,5)$ — this ignores that 3 seats are already filled.
    2. ✓ 36 — (B) 3 seats are fixed; the remaining 2 come from the 9 players left, $C(9,2) = 36$.
    3. 126 — 126 is $C(9,5)$ — the team size must shrink by 3 as well, to 2 remaining seats.
    4. 66 — 66 is $C(12,2)$ — the pool must shrink by the 3 fixed players, to 9 remaining.
The committee item’s usual wrong answer is 150, and the bar shows why it is so easy to stop there: the exactly-2-women case really is most of the answer. It is still not the answer. "At least 2" reads as 2, or 3, or 4, and because the three cases cannot overlap their counts simply add.
Every item in this set carries its own worked arithmetic; none of them shows the part that actually costs marks under time, which is deciding what is being asked in the first ten seconds. That is all this map is. Note the two items sharing one endpoint: an elective from three shelves and a polygon’s diagonals are the same move, one by adding cases and one by subtracting them.

↑ Back to top