Permutations and Combinations

Written and reviewed by Devendra Dubey, Mathematics faculty at UniDrill (M.Sc. Mathematics, Osmania University · 10 years teaching Mathematics). Based on NCERT Mathematics Class XI, Chapter 6.

How many ways can five friends sit in a row?

Try listing them and you will give up after a minute: there are 120. Now try a harder one: how many different 3-digit numbers can you make from the digits 1 to 9 without repeating a digit? Listing is hopeless, but counting takes ten seconds. This whole chapter is about counting without listing, and every formula in it grows out of one simple principle.

The fundamental principle: AND means multiply

If one job can be done in $m$ ways and, after that, a second job can be done in $n$ ways, then the two jobs together can be done in $m \times n$ ways. It extends to any number of jobs done one after another.

Why it works. Take 3 pants and 2 shirts. For each pant you have 2 shirt choices, so the outfits split into 3 groups of 2. That is $3 \times 2 = 6$ outfits. Add a third job (2 bags, 3 tiffin boxes, 2 bottles) and each earlier combination branches again: $2 \times 3 \times 2 = 12$.

The working habit this gives you: jobs one after another multiply; separate cases add. When a problem says "at least 2 flags", you do not multiply the cases, you count each case and add them.

Worked example: signals from flags. A signal is made by hoisting at least 2 of 5 different flags, one below the other, on a vertical staff. How many signals are possible?

Common wrong step: multiplying the four case counts. The cases never happen together, so they add.

Factorials and permutations: filling seats one by one

The factorial is the shorthand for "multiply all whole numbers down to 1":

$$n! = n(n-1)(n-2)\cdots 3 \cdot 2 \cdot 1, \qquad n! = n \cdot (n-1)!$$

Why $0! = 1$. Put $n=1$ in $n! = n\,(n-1)!$ and you get $1! = 1 \cdot 0!$, which forces $0! = 1$. It also makes sense in words: there is exactly one way to arrange nothing, which is to do nothing.

A permutation is an arrangement in a definite order. To arrange $r$ objects out of $n$ different ones, fill $r$ seats in turn. The first seat has $n$ choices, the second $n-1$, and so on until the $r$-th seat has $n-r+1$ choices. By the multiplication principle:

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

The fraction form appears because multiplying and dividing by $(n-r)!$ completes the product into $n!$. Two edge cases follow: $^{n}P_{n} = n!$ and $^{n}P_{0} = 1$.

If repetition is allowed, every seat has all $n$ choices, so the count is $n^{r}$. A 4-digit PIN using digits 0 to 9 has $10^{4} = 10000$ possibilities.

If some objects are identical, you must remove the double counting. Take the word ROOT. Pretend the two O's are different (O₁ and O₂) and you get $4! = 24$ arrangements. But swapping O₁ and O₂ gives the same word, so every real arrangement was counted twice:

$$\text{arrangements of ROOT} = \dfrac{4!}{2!} = 12$$

In general, if there are $n$ objects with $p_1$ of one kind, $p_2$ of a second kind, up to $p_k$ of a $k$-th kind, and the rest all different:

$$\dfrac{n!}{p_1!\,p_2!\cdots p_k!}$$

Worked example: repeated letters. In how many ways can the letters of ALLAHABAD be arranged?

Common wrong step: writing $9!$. That treats the four A's as four different letters, so every word is counted $4! \times 2! = 48$ times too often.

Pause and predict: if the first of 6 seats is reserved for a particular person, how many ways can the other 5 people fill the other 5 seats?

Check your answer: $5! = 120$. Once the first seat is taken, the problem is just "arrange 5 people in 5 seats". This idea of fixing one position and arranging the rest is behind every "starts with" and "ends with" question.

Combinations: selecting, not arranging

A combination is a selection where order does not matter. From players X, Y, Z you can form only 3 two-player teams: XY, YZ, ZX. But as arrangements there are 6 pairs, because XY and YX count separately. Every team has been counted $2!$ times, so teams = arrangements $\div\, 2!$.

That is the whole idea. Each selection of $r$ objects can be arranged in $r!$ ways, so

$$^{n}P_{r} = {}^{n}C_{r} \cdot r! \qquad\Longrightarrow\qquad {}^{n}C_{r} = \dfrac{n!}{r!\,(n-r)!}$$

with $^{n}C_{0} = {}^{n}C_{n} = 1$.

A fast check. From the letters A, B, C, D take 3: there are $^{4}P_{3} = 24$ arrangements but only $^{4}C_{3} = 4$ selections, and $24 \div 4 = 6 = 3!$. If your combination answer is not smaller than the permutation answer, something is wrong.

Pause and predict: from 7 people, in how many ways can you pick a 3-person committee, and in how many ways can you pick a president, vice president and secretary? How are the two answers related?

Check your answer: committee: $^{7}C_{3} = 35$. Three named posts: $^{7}P_{3} = 210$. The ratio is $210 \div 35 = 6 = 3!$, because the same 3 people can fill the three posts in $3!$ ways.

Two identities that save time

Symmetry. Choosing $r$ objects to take is the same as choosing $n-r$ objects to leave behind, so

$$^{n}C_{r} = {}^{n}C_{n-r}$$

This lets you compute large-looking values quickly: $^{12}C_{9} = {}^{12}C_{3} = \dfrac{12 \cdot 11 \cdot 10}{6} = 220$. It also gives the rule for equations: if $^{n}C_{a} = {}^{n}C_{b}$ then either $a = b$ or $a + b = n$. For instance $^{n}C_{9} = {}^{n}C_{8}$ cannot have $a=b$, so $n = 9 + 8 = 17$.

Pascal's identity. Pick $r$ people from $n+1$ people, and single out one person, say Riya. Either Riya is in the group (choose the other $r-1$ from the remaining $n$) or she is not (choose all $r$ from the remaining $n$). Adding the two cases:

$$^{n}C_{r} + {}^{n}C_{r-1} = {}^{n+1}C_{r}$$

It is also how Pascal's triangle is built, which you will use in the next chapter.

Beyond the textbook. For the exam: use $^{n}C_{r}$ whenever order does not matter, and $^{n}P_{r}$ when it does. In reality: a "combination lock" is actually a permutation lock, because the order of the digits matters. Lottery draws, on the other hand, are true combinations: choosing 6 numbers from 49 gives $^{49}C_{6} = 13983816$ equally likely tickets, and the order in which the balls come out is irrelevant.

Choosing the right method: three questions

Before you write any formula, ask: does order matter? can items repeat? are some items identical? The table turns the answers into a formula.

Number problems: watch the first digit

When forming numbers, the first place cannot be 0 (otherwise the number has fewer digits). Fix the restricted place first, then fill the rest.

Worked example: 3-digit numbers. How many 3-digit numbers can be formed from the digits 0, 1, 2, 3, 4, 5 (i) with no repetition, and (ii) with repetition allowed?

Common wrong step: starting with $6 \times 5 \times 4 = 120$. That counts numbers like 053, which are not 3-digit numbers.

For divisibility conditions, fix the last digit first: a number is divisible by 5 if it ends in 0 or 5, and by 2 if it ends in an even digit. Then fill the remaining places.

Together, never together, no two together

Letter and seating problems with conditions come in three flavours. Each has a standard move.

Worked example: TRIANGLE. The letters of TRIANGLE (8 distinct letters, 3 vowels I, A, E and 5 consonants) are arranged. Find the number of arrangements (i) with the vowels together, (ii) with the vowels never together, and (iii) with no two vowels adjacent.

Common wrong step: stopping at $6! = 720$ in part (i). That forgets that the vowels can swap places within their block.

Notice that (ii) and (iii) are different. "Never together" only forbids all three vowels from sitting in one block, while "no two adjacent" forbids any pair of vowels from touching.

Selections with conditions: split into cases

For committees and teams, break the problem into cases by the condition, count each with $^{n}C_{r}$, and add. "At least" means a sum over several cases, or total minus the unwanted cases.

Worked example: committee with at least 2 women. A committee of 5 is chosen from 6 men and 4 women. In how many ways can it include at least 2 women?

Common wrong step: choosing 2 women first and then any 3 more people from the remaining 8, giving $6 \times 56 = 336$. A committee with 3 women is counted several times, once for each way of calling two of them "the first two".

Cards follow the same pattern. A pack has 52 cards in 4 suits of 13, with 12 face cards. Choosing any 4 cards gives $^{52}C_{4} = 270725$. All four of one suit: $4 \times {}^{13}C_{4} = 4 \times 715 = 2860$. Four face cards: $^{12}C_{4} = 495$.

Worked example: solving an equation. If $^{n}P_{5} = 42 \cdot {}^{n}P_{3}$, find $n$.

Common wrong step: leaving both roots as answers. In permutation equations the unknown must be a whole number at least as large as $r$.

Beyond the textbook. For the exam: $^{n}C_{r}$ counts selections of $r$ items from $n$. In reality: the same number counts handshakes and matches. At a party of 12 where everyone shakes hands once with everyone else, the number of handshakes is $^{12}C_{2} = 66$, because each handshake is a selection of 2 people. The identity $\sum {}^{n}C_{r} = 2^{n}$ says the same thing in a different way: each of $n$ people is either in the group or out of it, giving $2^{n}$ groups of every size together.

Exam traps

Formula sheet

60-second revision

Where this chapter connects

• Previous: Linear Inequalities closes the algebra block; counting begins a new strand of discrete mathematics.
• Next: Binomial Theorem shows that $^{n}C_{r}$ are exactly the coefficients in the expansion of $(a+b)^n$.
• Same strand: Probability uses counting to find the number of favourable and total outcomes, and Sets gives the idea of subsets behind $2^n$.
• Class XII link: Probability relies on the same counting rules for conditional events and the binomial distribution.