UPSC NDA & NA · Module 36 · basic depth · 8 min
Counting: permutations and combinations
What UPSC NDA & NA asks from this chapter
Syllabus lines this chapter covers:
- Paper I: Mathematics · Concept of set, operations on sets, Venn diagrams. De Morgan laws, Cartesian product, relation, equivalence relation. Representation of real numbers on a line. Complex numbers— basic properties, modulus, argument, cube roots of unity. Binary system of numbers. Arithmetic, Geometric and Harmonic progressions. Quadratic equations with real coefficients. Solution of linear inequations of two variables by graphs. Permutation and Combination. Binomial theorem and its applications. Logarithms and their applications.
UPSC NDA & NA questions from this module are being sorted into our bank.
Cut to basic depth for UPSC NDA & NA. 46 deeper paragraphs are in the full chapter.
Start from zero: a tree of choices
You have 3 shirts and 4 trousers. How many different outfits can you wear? For each shirt you can pick any of the 4 trousers, so there are 4 + 4 + 4 = 3 × 4 = 12 outfits. Add 2 pairs of shoes and every outfit splits two ways again, giving 24.
That is the multiplication principle: when one choice is followed by another, multiply the number of ways. If instead you go to a town by one of 3 buses or one of 2 trains, you make only one choice, so there are 3 + 2 = 5 ways. "And then" means multiply; "or" means add.
Every formula in this chapter grows from these two rules. Permutations and combinations are just quick ways to apply them when the choices are many.
Why this topic exists. Counting tells you how many passwords, vehicle numbers, committee options or schedules are possible. Planners use it to judge whether a code system has enough numbers, or how many ways a duty roster can be drawn up.
The counting principle at work
Codes with repetition. A 3-digit lock code uses digits 0 to 9, and digits may repeat. Each place has 10 choices, so there are 10 × 10 × 10 = 1,000 codes. A 4-letter code from the 26 letters with repetition allows 26⁴ = 4,56,976 codes.
Codes without repetition. If the digits must all be different, the first place has 10 choices, the second 9 and the third 8. So there are 10 × 9 × 8 = 720 codes. Each place loses one choice because one digit has been used up.
Restricted places first. How many 4-digit even numbers can be made from the digits 1 to 6 with no repetition? Fill the restricted place first: the last digit must be 2, 4 or 6, which is 3 ways. The remaining three places then take 5 × 4 × 3 ways, so there are 3 × 60 = 180 numbers.
Routes. If 3 roads go from A to B and 4 from B to C, a trip from A to C through B has 3 × 4 = 12 routes. If the return trip may not reuse any road, there are 3 unused roads from C to B and 2 from B to A, so the round trips number 12 × 3 × 2 = 72.
Why it matters. Many counting questions need nothing beyond this principle. Always handle the most restricted place first, because its choices do not depend on the others.
Arrangements: when order matters
Everyone in a row. Five people can stand in a row in 5 × 4 × 3 × 2 × 1 ways. This product is written 5! and read "5 factorial"; it equals 120. In general, n different things can be lined up in n! ways, and by agreement 0! = 1.
Some of them in order. To fill r ordered places from n people, multiply n × (n − 1) × … for r factors. This is written P(n, r) = n! ÷ (n − r)!. Choosing a president and a secretary from 8 members gives P(8, 2) = 8 × 7 = 56, because the two posts are different.
Letters that repeat. The word BANANA has 6 letters, but the three A's are identical and so are the two N's. Swapping the A's among themselves gives no new word, so divide by 3! and by 2!: 720 ÷ (6 × 2) = 60 arrangements. The word LEVEL gives 5! ÷ (2! × 2!) = 30.
Round a table. For people round a circular table, only their order relative to each other matters, since turning everyone one seat gives the same seating. Fix one person and arrange the rest: 6 people can sit in (6 − 1)! = 120 ways. The seating chapter uses the same idea.
Why it matters. Arrangement questions are the commonest kind in this topic. Most mistakes come from forgetting to divide for repeated letters or for turning a circle.
Selections: when order does not matter
From arranging to choosing. Picking a committee of 3 from 8 people is different from picking a president, secretary and treasurer. Arranging 3 of 8 gives 8 × 7 × 6 = 336, but each committee has been counted 3! = 6 times, once for each order of the same three people. So the number of committees is 336 ÷ 6 = 56.
The formula. Choosing r from n gives C(n, r) = n! ÷ (r! × (n − r)!). Choosing r to take is the same as choosing n − r to leave, so C(n, r) = C(n, n − r); for example C(10, 8) = C(10, 2) = 45. Use whichever is smaller to calculate.
Handshakes, lines and triangles. If 10 people each shake hands once with every other, each handshake is a choice of 2 people, so there are C(10, 2) = 45 handshakes. Nine points with no three on a line give C(9, 2) = 36 straight lines. Seven such points give C(7, 3) = 35 triangles, because any three points that are not in a line make a triangle.
Teams from groups. To choose 2 men from 5 and 2 women from 4, choose each group separately and multiply: C(5, 2) × C(4, 2) = 10 × 6 = 60 teams. The multiplication principle joins the two selections.
Why it matters. Committees, teams and handshakes are classic selection questions. The key test is simple: if swapping two chosen items gives the same result, order does not matter and you must use C.
Quick revision
- "And then" multiplies; "or" adds.
- Fill the most restricted place first.
- n things in a row: n!; r of n in order: P(n, r) = n! ÷ (n − r)!.
- Choose r of n: C(n, r) = n! ÷ (r! × (n − r)!); C(n, r) = C(n, n − r).
- Repeated letters: divide n! by the factorial of each repeat count.
- Round a table: (n − 1)!.
- Together: glue, then multiply by the inside arrangements.
- Never together or at least one: total minus the opposite case.
- Handshakes and lines: C(n, 2); triangles from points: C(n, 3).