Permutations and combinations for NDA

Permutations and combinations is the chapter where candidates most often know the formulas and still get the answer wrong. The difficulty is almost never the arithmetic. It is deciding what is being counted: does order matter, are repeats allowed, is anything forced together or kept apart? Once that is settled, most NDA questions take three or four lines.

The same thinking powers probability, where "favourable cases ÷ total cases" is usually two counting problems.

Typical question types are:

• evaluating nPr and nCr, or finding n from an equation in them;
• arrangements of the letters of a word, with repeated letters or restrictions;
• forming numbers from given digits, with or without repetition;
• people around a table, or beads on a necklace;
• committees with conditions such as "at least two women";
• counting lines, triangles and diagonals from points.

The counting principle

• Multiplication rule: if one task can be done in m ways and, after it, a second in n ways, the two together can be done in m × n ways.
• Addition rule: if a task can be done in m ways or in n other ways (not both), it can be done in m + n ways.

Every formula below is these two rules applied repeatedly.

Permutations: order matters

n! = n × (n − 1) × … × 2 × 1, with 0! = 1.

• Arrangements of r objects chosen from n distinct objects: nPr = n!/(n − r)!. The first place has n choices, the next n − 1, and so on for r places.
• All n distinct objects in a row: n!.
• With repetition allowed, r places from n objects: nʳ.
• n objects where one kind repeats p times, another q times and so on: n!/(p! q! …). Swapping identical letters gives no new arrangement, so we divide out those swaps.

Restrictions

• Together: glue the items into one block, arrange the blocks, then multiply by the arrangements inside the block.
• Never together: total arrangements minus arrangements with them together (for two items). For larger groups, place the other items first and put the restricted ones in the gaps.
• Numbers from digits: fill the restricted place first. The first digit cannot be 0, and an even number must end in an even digit.

Circular arrangements

• n distinct people around a table: (n − 1)!. Fixing one person removes the rotations that look the same.
• Beads on a necklace or flowers on a garland, where turning it over gives the same arrangement: (n − 1)!/2, for n ≥ 3.

Combinations: order does not matter

nCr = n!/(r!(n − r)!) = nPr/r!. Each selection of r objects can be arranged in r! orders, so the number of selections is the arrangements divided by r!.

Properties that save time:

• nCr = nC(n − r). So 10C8 = 10C2 = 45.
• If nCx = nCy, then x = y or x + y = n.
• nCr + nC(r − 1) = (n + 1)Cr (Pascal's rule).
• Selecting any number of objects, at least one, from n distinct objects: 2ⁿ − 1.

Geometry counts from n points, no three collinear:

If m of the points are collinear, triangles become nC3 − mC3, and lines become nC2 − mC2 + 1.

Permutation or combination?

Worked NDA-style MCQs

Q1. How many four-digit numbers can be formed from the digits 0 to 9 if no digit is repeated?
(a) 5,040 (b) 4,536 (c) 4,500 (d) 3,024

The first digit has 9 choices (not 0). The second has 9 (0 is now allowed, one digit is used), then 8, then 7. 9 × 9 × 8 × 7 = 4,536. Answer: (b).

Q2. The number of arrangements of the letters of DEFENCE is:
(a) 5,040 (b) 2,520 (c) 840 (d) 420

Seven letters, with E three times: 7!/3! = 5,040/6 = 840. Answer: (c).

Q3. In how many arrangements of the letters of CADET are the two vowels not together?
(a) 48 (b) 72 (c) 96 (d) 120

All arrangements: 5! = 120. Treat A and E as one block: 4 units give 4! = 24, and the block can be AE or EA, so 48. Not together: 120 − 48 = 72. Answer: (b).

Q4. A committee of 5 is chosen from 6 men and 4 women. In how many ways can it include at least 2 women?
(a) 120 (b) 180 (c) 186 (d) 246

Total 10C5 = 252. No woman: 6C5 = 6. Exactly one woman: 4C1 × 6C4 = 4 × 15 = 60. At least two: 252 − 66 = 186. Direct check: 4C2 × 6C3 + 4C3 × 6C2 + 4C4 × 6C1 = 120 + 60 + 6 = 186. Answer: (c).

Q5. There are 10 points in a plane, of which exactly 4 are collinear, and no other three are collinear. How many triangles can be formed?
(a) 120 (b) 116 (c) 112 (d) 104

10C3 − 4C3 = 120 − 4 = 116. Three collinear points make no triangle. Answer: (b).

Q6. If nC8 = nC6, then nC2 is:
(a) 91 (b) 105 (c) 78 (d) 182

Since 8 ≠ 6, 8 + 6 = n, so n = 14. 14C2 = (14 × 13)/2 = 91. Answer: (a).

Common mistakes

• Forgetting that 0 cannot lead in a number. Fill the first place before the others.
• Not dividing for repeated letters. COMMITTEE has repeated M, T and E; each needs its own factorial in the denominator.
• Using (n − 1)! for a necklace. If the object can be flipped, divide by 2 as well.
• Adding two "at least" cases twice. Use the complement, or list the cases once each.
• Multiplying when you should add. "Two men or three women" is an addition of two cases.

Practice set

1. 10P3 equals: (a) 120 (b) 360 (c) 720 (d) 1,000
2. If nP2 = 56, then n is: (a) 7 (b) 8 (c) 9 (d) 14
3. The number of arrangements of the letters of ACADEMY is: (a) 5,040 (b) 2,520 (c) 1,260 (d) 720
4. From 9 cadets, 4 are to be chosen so that one particular cadet is always included. The number of ways is: (a) 126 (b) 70 (c) 56 (d) 84
5. The number of diagonals of a 12-sided polygon is: (a) 66 (b) 54 (c) 48 (d) 60
6. How many three-digit even numbers can be formed from 1, 2, 3, 4, 5 without repetition? (a) 12 (b) 24 (c) 36 (d) 60
7. The number of ways to make a garland of 6 different flowers is: (a) 120 (b) 720 (c) 60 (d) 360
8. 7C3 + 7C2 equals: (a) 56 (b) 35 (c) 70 (d) 21

Answers:

1. (c) 720. 10 × 9 × 8.
2. (b) 8. n(n − 1) = 56 = 8 × 7.
3. (b) 2,520. Seven letters with A twice: 7!/2!.
4. (c) 56. The fixed cadet is in; choose 3 more from the other 8: 8C3.
5. (b) 54. 12 × 9/2.
6. (b) 24. The units digit is 2 or 4 (2 ways); the other two places take 4 × 3 = 12 ways.
7. (c) 60. (6 − 1)!/2 = 120/2.
8. (a) 56. By Pascal's rule, 8C3.

What to do next

• For every question you practise, write "order matters: yes or no" before you calculate.
• Solve 30 questions from old NDA papers on this chapter, timed at 75 seconds each.
• Take these counting skills into probability, and see nCr again in the binomial theorem.