Unit 2: Combinatorics
Discrete Structures & Optimization notes · PTU syllabus (PGCA1917)
On this page
Unit summary
Counting underlies probability, algorithm analysis and cryptography. This unit covers the basic counting principles, permutations and combinations, the inclusion–exclusion principle, recurrence relations, generating functions and the pigeonhole principle with applications.
After this unit you can
- Apply the sum and product rules
- Compute permutations and combinations
- Use inclusion–exclusion and the pigeonhole principle
- Solve recurrence relations and use generating functions
PTU syllabus topics
- Basic counting principles
- permutations and combinations
- inclusion-exclusion principle
- recurrence relations
- generating functions
- pigeonhole principle and applications
Permutations
nPr = n! / (n − r)!
Combinations
nCr = n! / [r! (n − r)!]
Inclusion-exclusion
n(A ∪ B ∪ C) = Σ n(A) − Σ n(A ∩ B) + n(A ∩ B ∩ C)
Pigeonhole principle
n + 1 items in n boxes: some box has two or more
Topic 1
Basic counting principles
Sum rule
If a task can be done in one of m ways or one of n other ways (no overlap), there are m + n ways
Choose one elective from 5 IT or 3 management electives: 8 ways
Product rule
If a task has two stages with m and n ways, there are m × n ways
A password of 2 letters then 3 digits: 26² × 10³ = 6,76,000
Topic 2
Permutations and combinations
Permutations of n distinct objects taken r
P(n, r) = n! ÷ (n − r)!
Combinations
C(n, r) = n! ÷ (r! (n − r)!)
Permutations with repetition allowed
nʳ
Permutations of a multiset
n! ÷ (n1! n2! … nk!)
Combinations with repetition
C(n + r − 1, r)
Circular permutations
(n − 1)!
Example
Ways to choose a captain and vice-captain from 11: P(11, 2) = 110. Ways to choose a 3-member committee from 10: C(10, 3) = 120. Arrangements of MISSISSIPPI: 11! ÷ (4! 4! 2!) = 34,650.
- Pascal's identity: C(n, r) = C(n − 1, r − 1) + C(n − 1, r); binomial theorem: (x + y)ⁿ = Σ C(n, r) xⁿ⁻ʳ yʳ.
Topic 3
The inclusion–exclusion principle
Two sets
n(A ∪ B) = n(A) + n(B) − n(A ∩ B)
Three sets
n(A ∪ B ∪ C) = n(A) + n(B) + n(C) − n(A ∩ B) − n(A ∩ C) − n(B ∩ C) + n(A ∩ B ∩ C)
Example
Integers from 1 to 100 divisible by 2, 3 or 5: 50 + 33 + 20 − 16 − 10 − 6 + 3 = 74.
- Derangements: permutations with no element in its original place: Dn = n! (1 − 1/1! + 1/2! − … + (−1)ⁿ/n!); D4 = 9.
Topic 4
Recurrence relations
- Recurrence relation: an equation defining each term of a sequence using earlier terms, with initial conditions.
Linear homogeneous with constant coefficients
an = c1 an−1 + c2 an−2
Arithmetic
an = an−1 + d gives an = a0 + nd
Geometric
an = r an−1 gives an = a0 rⁿ
Tower of Hanoi
Hn = 2Hn−1 + 1, H1 = 1, giving Hn = 2ⁿ − 1
Divide and conquer
T(n) = 2T(n/2) + n gives O(n log n)
- Solving linear homogeneous recurrences: form the characteristic equation r² − c1 r − c2 = 0; distinct roots r1, r2 give an = A r1ⁿ + B r2ⁿ; repeated root r gives an = (A + Bn) rⁿ; use initial conditions to find A and B.
Example
an = 5an−1 − 6an−2, a0 = 1, a1 = 4: r² − 5r + 6 = 0, r = 2, 3; an = A·2ⁿ + B·3ⁿ; A + B = 1, 2A + 3B = 4 → B = 2, A = −1; an = 2·3ⁿ − 2ⁿ.
Topic 5
Solving linear recurrence relations
- 1Write the characteristic equation (aₙ = c1 aₙ₋₁ + c2 aₙ₋₂ gives r² − c1 r − c2 = 0)
- 2Find the roots
- 3Distinct roots r1, r2: aₙ = A r1ⁿ + B r2ⁿ
- 4Repeated root r: aₙ = (A + Bn) rⁿ
- 5Use initial conditions to find A and B
Example
aₙ = 5aₙ₋₁ − 6aₙ₋₂, a0 = 1, a1 = 4. r² − 5r + 6 = 0 → r = 2, 3. aₙ = A·2ⁿ + B·3ⁿ; A + B = 1, 2A + 3B = 4 → B = 2, A = −1. So aₙ = 2·3ⁿ − 2ⁿ.
- Algorithm analysis: T(n) = 2T(n/2) + n (merge sort) gives O(n log n); T(n) = T(n − 1) + 1 gives O(n).
Topic 6
Generating functions
- The generating function of a sequence a0, a1, a2, … is G(x) = a0 + a1x + a2x² + … — a power series used to count and to solve recurrences.
1, 1, 1, …
1 ÷ (1 − x)
1, a, a², …
1 ÷ (1 − ax)
C(n, 0), C(n, 1), …, C(n, n)
(1 + x)ⁿ
1, 2, 3, 4, …
1 ÷ (1 − x)²
Example
Ways to pick 4 fruits from apples, bananas and oranges with unlimited supply: coefficient of x⁴ in 1 ÷ (1 − x)³ = C(4 + 2, 2) = 15.
Topic 7
The pigeonhole principle
- If n + 1 or more objects are put into n boxes, at least one box holds two or more. Generalised: if N objects go into k boxes, some box holds at least ceil(N ÷ k).
Example
Among 367 people two share a birthday. In a class of 50, at least ceil(50 ÷ 12) = 5 students were born in the same month. Any 5 points in a unit square include two within distance √2 ÷ 2.
- Applications: collisions in hashing, lossless compression limits (no algorithm can shorten every file), scheduling and proofs of existence.
Key terms
- Permutation
- Ordered arrangement of objects
- Combination
- Unordered selection of objects
- Inclusion–exclusion
- Counting a union by adding and subtracting intersections
- Recurrence relation
- Equation defining a term from earlier terms
- Pigeonhole principle
- More objects than boxes forces a shared box
Quick revision
- Sum and product rules.
- P(n, r), C(n, r), repetition, multisets, circular; Pascal; binomial theorem.
- Inclusion–exclusion for two and three sets; derangements.
- Linear recurrences: characteristic equation; divide-and-conquer recurrences.
- Generating functions; pigeonhole and generalised pigeonhole principles.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.How many 4-digit PINs are possible?
- Q2.Find C(8, 3) and P(8, 3).
- Q3.How many integers from 1 to 60 are divisible by 2 or 3?
- Q4.Solve aₙ = 3aₙ₋₁, a0 = 2.
- Q5.What is the generating function of 1, 1, 1, …?
- Q6.Show that among 13 people two share a birth month.
Long-answer questions
- Q1.Explain permutations and combinations with examples.
- Q2.Explain and apply the inclusion–exclusion principle.
- Q3.Solve linear recurrence relations with the characteristic equation.
- Q4.Explain generating functions and the pigeonhole principle with applications.
Stuck on this unit?
Message SBS on WhatsApp for help with Discrete Structures & Optimization, or to ask about studying M.Sc IT at Synetic.