Permutations and combinations

Placement essentials (aptitude, reasoning, verbal, communication, interviews, Excel, workplace) (All) · Quantitative aptitude · free study notes for exams, placements and interviews

In short

Permutations and combinations (P&C) is the mathematics of counting arrangements and selections without listing them one by one: a permutation counts ordered arrangements, a combination counts unordered groups. It rests on two simple multiplication and addition rules and expands into circular arrangements, repetitions, grouping and distribution. Every campus aptitude paper — TCS NQT, Infosys, Wipro, Capgemini, Cognizant, Accenture, bank PO and SSC — carries 2 to 5 questions on it, and it is the direct foundation of the probability section. In engineering degrees it appears in Discrete Mathematics / Mathematics-III and in GATE CS (Engineering Mathematics) as counting, pigeonhole and inclusion-exclusion.

Explained

Counting principles and factorial

Fundamental principle of multiplication (AND): if a job is done in stages with m ways for the first and n for the second, the total is m × n. Three shirts and four trousers give 12 outfits.
Fundamental principle of addition (OR): mutually exclusive choices add. Travel by 4 trains or 3 buses → 7 ways.
Decide first whether a problem is "stage after stage" (multiply) or "case or case" (add). Mixed problems usually need both.
Factorial: n! = n × (n−1) × … × 2 × 1, with 0! = 1 by definition. 1!=1, 2!=2, 3!=6, 4!=24, 5!=120, 6!=720, 7!=5040, 8!=40320, 9!=362880, 10!=3628800 — memorise up to 10!.
Factorials grow very fast, so cancel symbolically before multiplying: 10!/8! = 10 × 9 = 90, never compute both.
Exponent of a prime p in n! (de Polignac / Legendre): add ⌊n/p⌋ + ⌊n/p²⌋ + … Used for trailing zeros and divisibility of factorials.

Permutations — order matters

Linear permutation of distinct objects: nPr = n!/(n−r)! — arrange r out of n distinct objects in a row. nPn = n!.
Permutation with repetition allowed (each place filled independently): n^r. Four-digit PIN from 0-9 with repetition = 10⁴ = 10,000.
Permutation of objects not all distinct: n!/(p! q! r! …) where p, q, r are the counts of identical items.
Restricted permutations:
- Particular object always included: r × (n−1)P(r−1); always excluded: (n−1)Pr.
- Two particular objects always together: treat them as one block → (n−1)! × 2! for full arrangements.
- Never together = total − together.
- No two of a kind adjacent: arrange the others first, then place the restricted ones in the gaps (gap method). k objects in a row of m others give (m+1) gaps → (m+1)P k ways.
Rank of a word in dictionary order: count words beginning with each alphabetically earlier letter, add 1 at the end.

Circular permutations

Fixing one object kills the rotational symmetry: n distinct objects round a circle = (n−1)!
If clockwise and anticlockwise are not distinguished (garlands of flowers, necklaces of beads) = (n−1)!/2.
Round a circle choosing r from n: nPr / r.
Seating round a table with persons A and B together: treat as one unit → (n−2)! × 2!.
A square or rectangular table with numbered seats is a *linear* problem (n!) because the seats are distinguishable; only an unmarked round table loses the reference point.

Combinations — order does not matter

nCr = n!/(r!(n−r)!) = nPr / r! — selection of r from n distinct objects.
Key identities: nCr = nC(n−r); nC0 = nCn = 1; nC1 = n; Pascal's rule nCr + nC(r−1) = (n+1)Cr.
Sum of all subsets: nC0 + nC1 + … + nCn = 2ⁿ; selecting at least one = 2ⁿ − 1.
Selection from groups: choose p from m AND q from n → mCp × nCq (multiply across independent groups).
At least / at most: break into cases and add, or subtract the complement from the total — the complement is usually shorter.
Combination with repetition (objects of each type unlimited, order irrelevant): (n+r−1)C r.
Selection from identical objects: p identical of one kind, q of another, r of a third → (p+1)(q+1)(r+1) − 1 ways to choose at least one.
Number of divisors of N = p^a q^b r^c is (a+1)(b+1)(c+1) — the same selection logic applied to prime powers.

Grouping, division and distribution

Divide m+n items into two unequal groups of m and n: (m+n)!/(m! n!). If m = n and the groups are unlabelled, divide by 2!: (2n)!/(n! n! 2!).
Into k equal unlabelled groups of n each: (kn)!/((n!)^k × k!). If the groups are labelled (Group A, Group B), do not divide by k!.
Identical objects into distinct boxes (beggar / star-and-bar method): n identical items into r distinct boxes with each getting at least one = (n−1)C(r−1); allowing empty boxes = (n+r−1)C(r−1).
Distinct objects into distinct boxes, any number each = r^n.
Number of non-negative integer solutions of x₁+x₂+…+x_r = n is (n+r−1)C(r−1); positive solutions = (n−1)C(r−1).
Derangement (no object in its own place): D(n) = n!(1 − 1/1! + 1/2! − … ± 1/n!); D(2)=1, D(3)=2, D(4)=9, D(5)=44.

Geometry, digits and other standard applications

From n points, no three collinear: lines = nC2, triangles = nC3, quadrilaterals = nC4. If k of the n points are collinear, subtract kC2 − 1 from the lines and kC3 from the triangles.
Diagonals of a convex n-gon = nC2 − n = n(n−3)/2.
Handshakes among n people = nC2; if each pair exchanges two gifts or sends letters to each other, it is nP2 = n(n−1).
Rectangles on an m × n grid of squares = (m+1)C2 × (n+1)C2; squares on a chessboard-type grid = Σ k² terms.
Number formation: handle the leading digit first (it cannot be 0), then the rest; for "divisible by 5" fix the unit digit as 0 or 5 and case-split.
Pigeonhole principle (GATE favourite): n+1 objects in n boxes force at least one box with two; generalised, ⌈n/k⌉ in some box.
Inclusion-exclusion: |A∪B∪C| = ΣA − Σ(pairs) + |A∩B∩C| — used for "at least one condition violated" counting.
Limitations: these formulas assume objects are either fully identical or fully distinct and that constraints are independent; partially constrained or overlapping conditions need case-splitting or inclusion-exclusion, and large constrained problems may need recursion rather than a closed formula.

Key points

Permutation - ordered arrangement; nPr = n!/(n−r)!. Order changes the answer.
Combination - unordered selection; nCr = n!/(r!(n−r)!) = nPr/r!. Order is irrelevant.
Relation - nPr = nCr × r!; a permutation is a selection followed by an arrangement.
0! = 1 - needed so that nCn = 1 and the formulas stay consistent.
Repetition allowed - permutation becomes n^r; combination becomes (n+r−1)Cr.
Identical items - divide by the factorial of each repeat count: n!/(p!q!r!).
Circular - (n−1)! for distinct seats around an unmarked table; (n−1)!/2 for garlands and necklaces.
Together / not together - tie into one block and multiply by the internal arrangements; "never together" = total − together.
Gap method - to keep items apart, arrange the free items first and slot the restricted ones into the gaps.
Complement rule - "at least one" is almost always faster as total − none.
Subsets - a set of n elements has 2ⁿ subsets, 2ⁿ − 1 non-empty.
Equal unlabelled groups - divide by k! for k groups of the same size; never divide if the groups are named.
Star and bar - n identical into r distinct boxes: (n+r−1)C(r−1) with empties allowed, (n−1)C(r−1) without.
Geometry links - lines nC2, triangles nC3, diagonals n(n−3)/2, handshakes nC2.
Divisors - N = p^a q^b r^c has (a+1)(b+1)(c+1) divisors, a pure selection count.
Pigeonhole - with n boxes and more than n objects, some box repeats; proves existence, not count.
Derangement - D(4) = 9, D(5) = 44; nobody in their own seat.
Sanity check - nCr ≤ nPr always, and both must be whole numbers; a fractional answer means a wrong model.

Formulas and examples

nPr = n! / (n − r)! — ordered arrangements of r out of n distinct objects (n, r whole numbers, r ≤ n)
nCr = n! / (r! (n − r)!) — unordered selections; nPr = nCr × r!
Arrangements of n items with repeats p, q, r … = n! / (p! q! r! …)
Permutations with repetition allowed = n^r ; selections with repetition = (n + r − 1)C r
Circular arrangements = (n − 1)! ; garland / necklace = (n − 1)! / 2
Division into k equal unlabelled groups of n = (kn)! / ((n!)^k × k!)
Identical n objects into r distinct boxes: at least one each = (n − 1)C(r − 1); empties allowed = (n + r − 1)C(r − 1)
Total subsets of an n-set = 2ⁿ ; diagonals of an n-gon = n(n − 3)/2 ; handshakes = nC2
Exponent of prime p in n! = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + …
Derangements D(n) = n! (1 − 1/1! + 1/2! − … ± 1/n!)

Example 1 — arrangements of a word with repeats (MISSISSIPPI). Letters: M-1, I-4, S-4, P-2; total n = 11.

Total arrangements = 11!/(4! 4! 2! 1!) = 39,916,800/(24 × 24 × 2) = 39,916,800/1,152 = 34,650.
Now, no two S together: arrange the other 7 letters (M, 4 I, 2 P) = 7!/(4! 2!) = 5,040/48 = 105 ways; these create 8 gaps, choose 4 for the S's = 8C4 = 70.
Answer = 105 × 70 = 7,350 arrangements with no two S adjacent.

Example 2 — committee selection with a condition. A placement committee of 5 is to be formed from 7 boys and 4 girls, with at least 2 girls.

2 girls: 4C2 × 7C3 = 6 × 35 = 210
3 girls: 4C3 × 7C2 = 4 × 21 = 84
4 girls: 4C4 × 7C1 = 1 × 7 = 7
Total = 210 + 84 + 7 = 301. (Check: all committees = 11C5 = 462; with 0 or 1 girl = 7C5 + 4C1 × 7C4 = 21 + 140 = 161; 462 − 161 = 301. ✔)

Example 3 — number formation. How many 4-digit numbers using digits 1-7 without repetition are (a) possible, (b) even, (c) divisible by 5?

(a) 7P4 = 7 × 6 × 5 × 4 = 840.
(b) Even → unit digit ∈ {2, 4, 6} = 3 choices; remaining three places from the other 6 digits = 6P3 = 120 → 3 × 120 = 360.
(c) Divisible by 5 → unit digit must be 5 (no 0 available) = 1 way; rest = 6P3 = 120 → 120.

Example 4 — circular seating and distribution. (a) Eight friends sit round an unmarked circular table; two of them, A and B, insist on sitting together.

Treat A-B as one unit → 7 units round the circle = (7−1)! = 720; internal order 2! = 2 → 1,440 ways. (All arrangements = 7! = 5,040, so "never together" = 5,040 − 1,440 = 3,600.)

(b) Distribute 10 identical certificates among 4 students so that each gets at least one: (10−1)C(4−1) = 9C3 = 84 ways; allowing some to get none: (10+4−1)C(4−1) = 13C3 = 286 ways.

Example 5 — rank of a word and trailing zeros. (a) Rank of MANIT among all arrangements of its 5 distinct letters (alphabetical order A, I, M, N, T):

Words starting with A: 4! = 24; with I: 4! = 24 → 48 words before any M-word.
M-A-: next letter from {I, N, T}; before N comes I → M-A-I-: 2! = 2 words. So 48 + 2 = 50 words precede.
M-A-N-I-T is the first with that prefix → rank = 50 + 1 = 51.

(b) Trailing zeros in 100!: ⌊100/5⌋ + ⌊100/25⌋ = 20 + 4 = 24 zeros.

Situation	Use	Formula	Example value
Arrange 3 of 5 distinct books	Permutation	5P3	60
Pick 3 of 5 books to gift (identical gifting)	Combination	5C3	10
3-letter codes from 5 letters, repeats allowed	Repetition	5³	125
5 people round an unmarked table	Circular	4!	24
5 beads in a necklace	Circular, reflection same	4!/2	12
6 students into 2 unlabelled groups of 3	Equal groups	6!/(3!3!2!)	10
6 students into Team A and Team B of 3	Labelled groups	6!/(3!3!)	20

Where it is used

IT services hiring (TCS, Infosys, Wipro, HCL, Cognizant, Capgemini, Accenture): quantitative aptitude rounds and online assessments; counting questions also appear as coding problems on subsets, permutations and backtracking.
Banking and government exams (IBPS PO/Clerk, SBI, RBI Grade B, SSC CGL, CAT, GATE): P&C plus probability is a fixed scoring block; GATE CS tests counting, pigeonhole, recurrence and inclusion-exclusion.
Software engineering: test-case design (pairwise/combinatorial testing), password-space and key-space sizing in security, hash and index design, generating permutations in algorithms (next_permutation, N-Queens, travelling salesman brute force).
Analytics and operations: number of possible route, shift or roster combinations in workforce management; A/B and multivariate experiment design; SKU-variant counting in retail and e-commerce catalogues.
Telecom, transport and identifiers: sizing of mobile number series, vehicle registration formats (for example a two-letter state code, two-digit RTO number and a four-digit series), PAN and IFSC-style alphanumeric code spaces, UPI PIN and OTP strength.
Quality, genetics and lottery-style problems: sampling plans and inspection lots, cryptographic brute-force estimates, and state-lottery or tambola combination counts.

Interview questions

Q: What exactly is the difference between a permutation and a combination? A: A permutation counts arrangements where order matters; a combination counts selections where it does not. nPr = nCr × r!, because each selection of r objects can be ordered in r! ways.
Q: Why is 0! defined as 1? A: There is exactly one way to arrange nothing, and the definition keeps nCn = n!/(n!·0!) = 1 and the binomial expansion consistent.
Q: Why is circular arrangement (n−1)! and not n!? A: A circle has no fixed starting point, so each linear arrangement repeats n times by rotation; fixing one person removes that duplication.
Q: When do you divide a garland count by 2? A: When flipping the arrangement gives the same object — garlands, necklaces, bangles — because clockwise and anticlockwise orders are indistinguishable.
Q: How many ways can 6 people be split into two groups of 3? A: 10 if the groups are unnamed, 6!/(3!3!2!); 20 if they are named Team A and Team B, 6!/(3!3!).
Q: A password is 8 characters from 62 alphanumerics. How large is the key space? A: 62⁸ ≈ 2.18 × 10¹⁴ with repetition allowed — that is a permutation with repetition, not a combination.
Q: How many diagonals does a decagon have? A: n(n−3)/2 = 10 × 7/2 = 35.
Q: 12 people at a meeting shake hands once with everyone. How many handshakes? A: 12C2 = 66, because a handshake is an unordered pair.
Q: How many ways can 20 identical laptops be given to 4 branches, each getting at least one? A: 19C3 = 969, by the star-and-bar rule (n−1)C(r−1).
Q: State the pigeonhole principle and give one use. A: If more than n objects go into n boxes, some box holds at least two; it proves, for example, that in any group of 13 people two share a birth month.
Q: What is a derangement, and how many derangements do 4 letters in 4 envelopes have? A: An arrangement where no object sits in its own place; D(4) = 9.
Q: How many trailing zeros in 50!? A: ⌊50/5⌋ + ⌊50/25⌋ = 10 + 2 = 12.

Common mistakes

Using nCr where order matters (ranks, seats, codes, prizes of different value) or nPr where it does not (teams, committees, handshakes).
Forgetting to divide by the factorials of repeated letters, so arrangements of words like BALLOON or SUCCESS come out too large.
Treating a round table with numbered or distinguishable seats as circular — with marked seats it is n!, not (n−1)!.
Dividing by k! for labelled groups, or failing to divide for equal unlabelled groups.
Allowing 0 in the leading position of a number, which inflates digit-formation answers.
Adding when the stages must multiply, or double-counting overlapping cases instead of using inclusion-exclusion or the complement.
Mixing "at least" with "exactly" — "at least 2 girls" means summing all cases from 2 upward, not just the 2-girl case.