Combinatorics — Counting, Permutations, Combinations & Pigeonhole Principle
Complete Guide for GATE CS — Rule of Sum/Product, P(n,r), C(n,r), Binomial Theorem, Inclusion-Exclusion & Derangements
Last Updated: April 2026
📌 Key Takeaways
- Rule of Product: If task A can be done in m ways and task B in n ways independently, both together can be done in m × n ways.
- Permutation P(n,r): Ordered selection of r from n. P(n,r) = n!/(n−r)!. Circular permutation of n = (n−1)!
- Combination C(n,r): Unordered selection of r from n. C(n,r) = n!/(r!(n−r)!). C(n,r) = C(n, n−r).
- Binomial Theorem: (x+y)n = ∑ C(n,k) xk yn−k. Sum of all binomial coefficients = 2n.
- Pigeonhole Principle: n+1 objects in n boxes → at least one box has ≥ 2 objects. Generalized: kn+1 objects → at least one box has ≥ k+1.
- Inclusion-Exclusion: |A∪B| = |A|+|B|−|A∩B|. Alternating sum over all subset intersections for more sets.
- Derangements D(n): Permutations with no fixed points. D(n) ≈ n!/e. D(n) = (n−1)[D(n−1)+D(n−2)].
1. Basic Counting Rules
Rule of Product (Multiplication Principle)
If task A can be done in m ways and, for each way of doing A, task B can be done in n ways, then A and B together can be done in m × n ways.
Example: 3 shirts and 4 trousers → 3×4 = 12 outfits
Rule of Sum (Addition Principle)
If task A can be done in m ways and task B in n ways, and the tasks are mutually exclusive (cannot be done simultaneously), then A or B can be done in m + n ways.
Example: Travel by bus (3 routes) or train (2 routes) → 3+2 = 5 ways
1.1 Counting Subsets
| What to Count | Formula | Example (n=4) |
|---|---|---|
| All subsets of an n-element set | 2n | 2⁴ = 16 |
| Non-empty subsets | 2n − 1 | 15 |
| Subsets of size exactly r | C(n,r) | C(4,2) = 6 |
| Functions from A to B (|A|=m, |B|=n) | nm | — |
| Bijections (|A|=|B|=n) | n! | 4! = 24 |
2. Permutations
A permutation is an ordered arrangement of objects. Order matters — ABC and BAC are different permutations.
Permutation Formulas
P(n, r) = n! / (n−r)! — ordered selection of r from n distinct objects
P(n, n) = n! — all arrangements of n distinct objects
Permutations with repetition: nr — r positions each with n choices
Permutations with identical objects: n! / (n₁! × n₂! × … × nₖ!) — where n₁,n₂,…,nₖ are counts of each repeated object
Circular permutations: (n−1)! — arrangements of n objects in a circle (one position fixed)
Circular with flips (necklace): (n−1)!/2 — if clockwise = anticlockwise
2.1 Common Permutation Scenarios
| Scenario | Formula |
|---|---|
| Arrange n distinct objects in a line | n! |
| Choose and arrange r from n distinct | P(n,r) = n!/(n−r)! |
| Arrange with some kept together (treat as block) | (n−k+1)! × k! (k items in block) |
| Arrange with some never together | Total − arrangements where they ARE together |
| Arrangements of MISSISSIPPI (4S,4I,2P,1M,1) | 11!/(4!4!2!) |
3. Combinations & Binomial Theorem
A combination is an unordered selection of objects. Order does not matter — {A,B,C} and {C,A,B} are the same combination.
Combination Formula
C(n, r) = n! / (r! × (n−r)!) also written as ⁿCᵣ or nCr or C(n,r)
C(n,r) = C(n, n−r) (symmetry: choosing r to include = choosing n−r to exclude)
C(n,0) = C(n,n) = 1
C(n,1) = n
Pascal’s Identity: C(n,r) = C(n−1, r−1) + C(n−1, r)
3.1 Binomial Theorem
Binomial Theorem
(x + y)n = ∑k=0n C(n,k) × xk × yn−k
Key special cases:
(1+1)n = 2n → ∑ C(n,k) = 2n (sum of all binomial coefficients)
(1−1)n = 0 → ∑ (−1)k C(n,k) = 0 (alternating sum = 0)
(1+x)n differentiated at x=1: ∑ k×C(n,k) = n×2n−1
4. Pigeonhole Principle
Pigeonhole Principle
Basic: If n+1 objects are placed in n boxes, at least one box contains ≥ 2 objects.
Generalized: If kn+1 objects are placed in n boxes, at least one box contains ≥ k+1 objects.
Average argument: If total objects = m placed in n boxes, at least one box has ≥ ⌈m/n⌉ objects.
4.1 Classic Pigeonhole Applications
| Problem | Pigeons | Holes | Conclusion |
|---|---|---|---|
| 13 people → same birth month | 13 people | 12 months | At least 2 share a month |
| 5 points in 2×2 square → 2 within √2 | 5 points | 4 unit squares | Two points in same unit square → distance ≤ √2 |
| n+1 integers → two with same remainder mod n | n+1 integers | n remainders (0..n−1) | Two integers are congruent mod n |
| Any 10 integers → two with same last digit | 10 integers | 10 digits (0–9) | Wait — need 11 integers for guaranteed collision |
5. Inclusion-Exclusion Principle
Inclusion-Exclusion
Two sets: |A ∪ B| = |A| + |B| − |A ∩ B|
Three sets: |A ∪ B ∪ C| = |A|+|B|+|C| − |A∩B| − |B∩C| − |A∩C| + |A∩B∩C|
General (n sets): |A₁ ∪ … ∪ Aₙ| = ∑|Aᵢ| − ∑|Aᵢ∩Aⱼ| + ∑|Aᵢ∩Aⱼ∩Aₖ| − … + (−1)n+1|A₁∩…∩Aₙ|
Complement form (count “none of the properties”):
|Ā₁ ∩ Ā₂ ∩ … ∩ Āₙ| = |U| − |A₁ ∪ … ∪ Aₙ|
5.1 Surjective Functions via Inclusion-Exclusion
Number of surjective (onto) functions from A (|A|=m) to B (|B|=n):
Surjections = ∑k=0n (−1)k × C(n,k) × (n−k)m
Example: Surjections from 4-element set to 3-element set = C(3,0)×3⁴ − C(3,1)×2⁴ + C(3,2)×1⁴ = 81 − 48 + 3 = 36
6. Derangements
A derangement D(n) is a permutation of n elements in which NO element appears in its original position (no fixed points).
Derangement Formulas
D(n) = n! × ∑k=0n (−1)k / k! = n![1 − 1/1! + 1/2! − 1/3! + … + (−1)n/n!]
Recurrence: D(n) = (n−1) × [D(n−1) + D(n−2)], with D(1)=0, D(2)=1
D(n) = (n−1) × D(n−1) + (−1)n (alternative recurrence)
Probability a random permutation is a derangement → 1/e ≈ 0.368 as n→∞
| n | D(n) | n! | D(n)/n! |
|---|---|---|---|
| 1 | 0 | 1 | 0 |
| 2 | 1 | 2 | 0.500 |
| 3 | 2 | 6 | 0.333 |
| 4 | 9 | 24 | 0.375 |
| 5 | 44 | 120 | 0.367 |
| 6 | 265 | 720 | 0.368 |
7. Stars and Bars
The Stars and Bars technique counts the number of ways to distribute n identical objects into k distinct bins.
Stars and Bars Formulas
Non-negative integer solutions to x₁ + x₂ + … + xₖ = n:
Count = C(n + k − 1, k − 1) = C(n + k − 1, n)
(distribute n identical balls into k distinct boxes, each box can have 0 or more)
Positive integer solutions (each xᵢ ≥ 1):
Count = C(n − 1, k − 1) (substitute yᵢ = xᵢ − 1, then solve for non-negative)
Example: x₁+x₂+x₃ = 10, xᵢ ≥ 0 → C(12,2) = 66 solutions
Example: x₁+x₂+x₃ = 10, xᵢ ≥ 1 → C(9,2) = 36 solutions
8. Worked Examples (GATE CS Level)
Example 1 — Permutations & Circular Arrangements
Problem: (a) In how many ways can 5 students be seated in a row if two specific students must always sit together? (b) How many distinct arrangements of the word ENGINEERING exist? (c) 6 people sit at a round table; how many arrangements are possible? How many if two specific people must not sit adjacent?
(a) Two students always together:
Treat the two students (say A and B) as a single block. Now we have 4 units (the block + 3 others) to arrange: 4! ways. The two students within the block can swap: 2! ways.
Total = 4! × 2! = 24 × 2 = 48 arrangements
(b) Arrangements of ENGINEERING:
Letters: E×3, N×3, G×2, I×2, R×1 → Total letters = 11
Arrangements = 11! / (3! × 3! × 2! × 2! × 1!) = 39916800 / (6×6×2×2×1) = 39916800/144 = 277,200
(c) 6 people at a round table:
Circular permutations = (6−1)! = 5! = 120.
Now, arrangements where two specific people (A and B) ARE adjacent: treat A,B as a block → (5−1)! × 2! = 24×2 = 48.
Arrangements where A,B NOT adjacent = 120 − 48 = 72
Example 2 — Inclusion-Exclusion
Problem: In a group of 100 students: 60 study Maths, 50 study Physics, 30 study Chemistry. 20 study both Maths and Physics, 15 both Physics and Chemistry, 10 both Maths and Chemistry. 5 study all three. Find: (a) Students studying at least one subject. (b) Students studying exactly one subject. (c) Students studying none of the three.
Given: |M|=60, |P|=50, |C|=30, |M∩P|=20, |P∩C|=15, |M∩C|=10, |M∩P∩C|=5, |U|=100
(a) At least one subject (|M ∪ P ∪ C|):
|M∪P∪C| = 60+50+30 − 20−15−10 + 5 = 140 − 45 + 5 = 100
(b) Exactly one subject:
Only Maths = |M| − |M∩P| − |M∩C| + |M∩P∩C| = 60−20−10+5 = 35
Only Physics = 50−20−15+5 = 20
Only Chemistry = 30−15−10+5 = 10
Exactly one = 35+20+10 = 65 students
(c) None of the three:
None = 100 − 100 = 0 students (all 100 study at least one subject in this case)
Example 3 — Pigeonhole & Derangements
Problem: (a) What is the minimum number of students needed in a class to guarantee that at least 3 were born in the same month? (b) 4 letters are addressed to 4 people. In how many ways can all letters be misdelivered (no letter reaches its intended recipient)? (c) How many ways can 8 identical balls be distributed among 3 distinct boxes with each box having at least 1 ball?
(a) Pigeonhole — 3 born in same month:
12 months = 12 holes. We want at least one hole with ≥ 3 pigeons. Using generalized pigeonhole: need kn+1 = 2(12)+1 students.
Minimum = 2×12 + 1 = 25 students
With 24 students, it’s possible each month has exactly 2 (24/12=2). The 25th student forces some month to have 3.
(b) All 4 letters misdelivered — Derangements:
D(4) = 4![1 − 1 + 1/2 − 1/6 + 1/24] = 24[12/24 − 4/24 + 1/24] = 24[9/24] = 9 ways
Verify with recurrence: D(4) = 3×[D(3)+D(2)] = 3×[2+1] = 3×3 = 9 ✓
(c) 8 identical balls into 3 boxes, each box ≥ 1:
Use Stars and Bars with positive integers: x₁+x₂+x₃ = 8, xᵢ ≥ 1.
Solutions = C(8−1, 3−1) = C(7,2) = 7!/(2!5!) = 21 ways
9. 5 Common Mistakes in Combinatorics
Mistake 1 — Using Permutation Formula When Order Doesn’t Matter
What happens: For “select a committee of 3 from 10 people,” students compute P(10,3) = 720 instead of C(10,3) = 120.
Root cause: Not asking “does order matter here?” A committee {A,B,C} is the same regardless of the order members were listed.
Correct approach: If arrangement/sequence matters → permutation. If selection only (no order) → combination. Key question: “Is {A,B,C} different from {C,B,A}?” If no → C(n,r).
Mistake 2 — Forgetting the Outer Face in Circular Permutations
What happens: Students use n! for circular arrangements instead of (n−1)!.
Root cause: In a circle, rotations of the same arrangement are identical. Fixing one person’s position eliminates n identical rotations.
Correct approach: Circular permutations = (n−1)!. If necklace (flipping allowed) = (n−1)!/2.
Mistake 3 — Misapplying Inclusion-Exclusion by Missing Intersection Terms
What happens: For three sets, students use |A|+|B|+|C|−|A∩B∩C| and forget the pairwise intersections.
Root cause: Misremembering the formula — the triple intersection is added back, not subtracted, and all three pairwise intersections must be subtracted first.
Correct approach: |A∪B∪C| = |A|+|B|+|C| − |A∩B| − |B∩C| − |A∩C| + |A∩B∩C|. The pattern: + singles, − pairs, + triples, − quadruples, …
Mistake 4 — Confusing Stars & Bars Formulas for ≥0 vs ≥1
What happens: For x₁+x₂+x₃=10 with xᵢ≥1, students use C(10+3−1, 3−1) = C(12,2) (the ≥0 formula) and get 66 instead of 36.
Root cause: Forgetting to substitute yᵢ = xᵢ−1 when each variable must be at least 1.
Correct approach: For xᵢ≥1: substitute yᵢ=xᵢ−1 → y₁+y₂+…+yₖ = n−k (yᵢ≥0) → C(n−k+k−1, k−1) = C(n−1, k−1).
Mistake 5 — Off-by-One in Pigeonhole
What happens: To guarantee 3 people share a birth month, students say “need 2×12 = 24 people” instead of 25.
Root cause: Forgetting that with exactly kn objects, it’s still possible each box has exactly k (no box has k+1). You need kn+1 to guarantee one box has k+1.
Correct approach: To guarantee ≥(k+1) in some box with n boxes, you need ≥ kn+1 objects. The “worst case” is exactly k in each box (kn objects total). One more object breaks that balance.
10. Frequently Asked Questions
Q1. What is the difference between permutation and combination?
A permutation P(n,r) = n!/(n−r)! counts ordered arrangements — the sequence matters. Selecting president, VP, and secretary from 10 people is a permutation because ABC ≠ BAC (different roles). A combination C(n,r) = n!/(r!(n−r)!) counts unordered selections — only membership matters. Selecting a 3-person committee from 10 is a combination because {A,B,C} = {C,B,A}. The relationship: C(n,r) = P(n,r)/r!, because each unordered group of r can be arranged in r! ordered ways.
Q2. State the Pigeonhole Principle with a non-trivial example.
Basic form: placing n+1 objects into n pigeonholes forces at least one hole to contain ≥2 objects. A non-trivial example: Among any 5 integers, at least two must have the same remainder when divided by 4. Proof: there are only 4 possible remainders (0,1,2,3). With 5 integers (pigeons) and 4 remainders (holes), by pigeonhole, two integers share a remainder — meaning their difference is divisible by 4. GATE uses this in proofs about graphs (e.g., in any graph with n≥2 vertices, at least two vertices have the same degree) and in algorithm analysis (birthday problem, hash collisions).
Q3. What is the inclusion-exclusion principle?
Inclusion-Exclusion is a counting technique to find the size of the union of sets when they overlap. The formula alternates between adding and subtracting intersection sizes: |A∪B| = |A|+|B|−|A∩B| for two sets; |A∪B∪C| = |A|+|B|+|C| − |A∩B|−|B∩C|−|A∩C| + |A∩B∩C| for three sets. The intuition: adding individual sets overcounts elements in intersections, so we subtract pairwise intersections — but now elements in all three are subtracted too many times, so we add the triple intersection back. In GATE CS, this principle also counts surjective functions, derangements, and the Euler totient function φ(n).
Q4. What is a derangement and how do you count derangements of 4 elements?
A derangement of n elements is a permutation where no element is in its original position — no fixed points. The number D(n) is computed by inclusion-exclusion: D(n) = n!×∑(−1)ᵏ/k! for k=0..n. For n=4: D(4) = 4![1/0! − 1/1! + 1/2! − 1/3! + 1/4!] = 24[1 − 1 + 0.5 − 1/6 + 1/24] = 24 × 9/24 = 9. These 9 derangements represent all ways to scramble 4 items so none is in its original spot. The recurrence D(n) = (n−1)[D(n−1)+D(n−2)] often makes computation easier.