Combinatorics — Counting, Recurrences and Generating Functions
Every counting question is one of four shapes, and naming the shape is most of the work. Does order matter, and may things repeat? Order and no repetition is a permutation, nPr; no order and no repetition is a combination, nCr; order with repetition is nʳ; and no order with repetition is the one candidates forget — C(n + r − 1, r), the stars-and-bars count, which is also the number of non-negative integer solutions of x₁ + ⋯ + xₙ = r. Deciding those two questions before reaching for a formula prevents almost every wrong answer in the topic. Two more tools handle what plain counting cannot. Inclusion–exclusion fixes double counting: |A ∪ B| = |A| + |B| − |A ∩ B|, and with three sets you add the singles, subtract the pairs and add the triple back — the alternating signs are not decoration, they are the corrections of corrections. And the pigeonhole principle answers existence questions that look like they need a construction: thirteen people must include two born in the same month, because there are twelve months, and no amount of cleverness in choosing the people avoids it. The second half of the chapter is recurrences, and a linear homogeneous recurrence with constant coefficients is solved exactly like a differential equation of the same shape: write the characteristic equation, find its roots, and combine the powers. For aₙ = 5aₙ₋₁ − 6aₙ₋₂ the characteristic equation is x² − 5x + 6 = 0 with roots 2 and 3, so aₙ = A·2ⁿ + B·3ⁿ, and the initial conditions fix A and B. Always check the closed form by iterating the recurrence two or three steps — it costs seconds and it is the only way to catch a sign error in A or B. Generating functions are the same idea in a different currency: encode a sequence as the coefficients of a power series, do algebra on the series, and read the answer off as a coefficient. The one expansion worth knowing cold is 1/(1 − x)ᵏ, whose coefficient of xⁿ is C(n + k − 1, k − 1) — which is the stars-and-bars formula again, arriving from the other direction.
Recurrences — the Characteristic Equation
A linear homogeneous recurrence with constant coefficients is solved by the same three steps as a differential equation of the same shape, and if you have read the Engineering Mathematics chapter on differential equations the method will already be familiar — the analogy is exact, with powers in place of exponentials.
- Write the characteristic equation by replacing aₙ₋ₖ with x(−k) and clearing: aₙ = 5aₙ₋₁ − 6aₙ₋₂ gives x² − 5x + 6 = 0.
- Solve it. Roots 2 and 3, distinct, so the general solution is aₙ = A·2ⁿ + B·3ⁿ. A repeated root r would give (A + Bn)·rⁿ, exactly as a repeated root in a differential equation brings in a factor of t.
- Fit the initial conditions. With a₀ = 1 and a₁ = 5: A + B = 1 and 2A + 3B = 5 give B = 3, A = −2, so aₙ = 3·3ⁿ − 2·2ⁿ. Then check by iterating: 1, 5, 19, 65, 211 from the recurrence, and the closed form gives the same five terms.
⚠️ Check the closed form by iterating — it is the only cheap check there is
The characteristic roots are hard to get wrong; the constants A and B are easy to get wrong, because they come from a small linear system solved under time pressure and a sign error there produces a formula that looks entirely reasonable. Iterating the recurrence for three terms and comparing costs about fifteen seconds and catches every such error. It also catches the other common slip, which is fitting the constants to the wrong indices — whether the given data is a₀ and a₁ or a₁ and a₂ changes the system, and the question will state which.Generating Functions, and One Expansion to Know
- 1/(1 − x) = 1 + x + x² + ⋯, so every coefficient is 1. This is the sequence of all ones, and every other expansion in the topic is built from it.
- 1/(1 − x)ᵏ has xⁿ-coefficient C(n + k − 1, k − 1). For k = 3 and n = 10 that is C(12, 2) = 66 — the same 66 as the stars-and-bars answer above, which is not a coincidence: multiplying k copies of 1 + x + x² + ⋯ is exactly distributing n identical items into k labelled boxes.
- (1 + x)ⁿ has xʳ-coefficient C(n, r) — the binomial theorem read as a generating function. The coefficient of x⁵ in (1 + x)⁸ is C(8, 5) = 56, the same 56 as the 8-bit-strings count, again for the same reason.
- Catalan numbers count binary search trees on n distinct keys, balanced-bracket strings and triangulations of a polygon, and are Cₙ = C(2n, n)/(n + 1): C₃ = 5 and C₄ = 14. GATE asks this most often as "how many distinct BSTs on n keys", and the answer is Catalan rather than n! precisely because a BST is determined by its shape and the keys then have only one place to go.
Key takeaways
- Decide two questions before any formula: does order matter, and may things repeat? The four answers are nPr, nCr, nʳ and C(n + r − 1, r).
- Stars and bars counts non-negative solutions. For strictly positive ones, hand each variable its compulsory 1 first: 66 becomes 36.
- Inclusion–exclusion alternates signs because each correction over-corrects: singles minus pairs plus the triple.
- Pigeonhole answers existence without construction, and its generalised form ⌈m/n⌉ answers how many must share rather than whether two do.
- Solve a linear recurrence by its characteristic equation, exactly as for a differential equation — distinct roots give A·r₁ⁿ + B·r₂ⁿ, a repeated root gives (A + Bn)rⁿ.
- Always check a closed form by iterating the recurrence two or three steps. The roots are hard to get wrong and the constants are easy.
- Know 1/(1 − x)ᵏ, whose xⁿ-coefficient is C(n + k − 1, k − 1) — the stars-and-bars formula arriving from the other direction.
Practice questions (8)
Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.
The number of non-negative integer solutions of x₁ + x₂ + x₃ = 10 is:
Show answer
Answer: B — 66
Stars and bars: ten identical stars and two bars separating three groups, so choose which 2 of the 12 positions hold bars — C(12, 2) = 66. Option A is the count of strictly positive solutions, C(9, 2) = 36, which is what you get by handing each variable its compulsory 1 first and distributing the remaining 7. Both numbers are in the options because reading whether zero is allowed is the entire question. Option D is 10³, the answer if the variables were ordered choices from ten values rather than parts of a fixed sum.The recurrence aₙ = 5aₙ₋₁ − 6aₙ₋₂ with a₀ = 1 and a₁ = 5 has the closed form:
Show answer
Answer: A — 3·3ⁿ − 2·2ⁿ
The characteristic equation x² − 5x + 6 = 0 has roots 2 and 3, so aₙ = A·2ⁿ + B·3ⁿ. Fitting a₀ = 1 gives A + B = 1 and a₁ = 5 gives 2A + 3B = 5, so B = 3 and A = −2 — the closed form is 3·3ⁿ − 2·2ⁿ. Check by iterating: the recurrence gives 1, 5, 19, 65, 211, and so does the formula. Option B has the constants with their signs swapped, which is exactly the error the iteration check exists to catch — it gives a₀ = −1. Option C fits neither condition, and option D would be the shape for a repeated root, which this equation does not have.The number of 8-bit binary strings containing exactly three 1s is:
Show answer
Answer: B — 56
A string is fixed by which three of the eight positions hold the 1s, and the positions are chosen without order and without repetition: C(8, 3) = 56. Option D is P(8, 3) = 336, the answer if the three 1s were distinguishable and their order mattered — they are not, and 336 = 56 × 3! is exactly the over-count. Option C is 2⁸, the number of 8-bit strings with no condition at all. The general move is worth naming: "exactly k of something in n slots" is always a combination, and recognising that turns a string question into a binomial coefficient without any case analysis.In a class, 30 students study Maths, 25 Physics and 20 Chemistry; 12 study Maths and Physics, 10 Maths and Chemistry, 8 Physics and Chemistry, and 5 study all three. The number studying at least one subject is:
Show answer
Answer: B — 50
Inclusion–exclusion: 30 + 25 + 20 − 12 − 10 − 8 + 5 = 50. The final plus is the step candidates drop, and it is worth understanding rather than memorising: the five students in all three subjects were counted three times in the singles, then removed three times by the pairs, leaving them out altogether — so they have to be added back once. Dropping that term gives 45, which is option A. Option D is the plain sum 75, the answer if nobody overlapped at all, and the difference of 25 between 75 and 50 is exactly the double counting the corrections remove.The coefficient of x¹⁰ in the expansion of 1/(1 − x)³ is:
Show answer
Answer: C — 66
The coefficient of xⁿ in 1/(1 − x)ᵏ is C(n + k − 1, k − 1), so here it is C(12, 2) = 66. That is the same 66 as the number of non-negative solutions of x₁ + x₂ + x₃ = 10, and the coincidence is the point: multiplying three copies of 1 + x + x² + ⋯ and collecting the x¹⁰ term is distributing ten units among three variables, so the generating function and the stars-and-bars argument are one calculation in two notations. Option A is the coefficient for 1/(1 − x)², which is C(11, 1) = 11, and offering it checks that you read the exponent on the denominator.Which of the following are correct? (More than one option may be correct.)
Show answer
Answer: A — Among any 13 people, two share a birth month; B — C(n, r) = C(n, n − r) for all 0 ≤ r ≤ n; D — The number of subsets of an n-set is 2ⁿ
Three hold. A is the pigeonhole principle with 13 objects and 12 boxes. B is the symmetry of the binomial coefficient — choosing r to include is the same as choosing n − r to leave out — and it is the identity that halves the work in a table of binomials. D is the standard subset count, one binary choice per element. Only C fails: the number of BSTs on n distinct keys is the Catalan number Cₙ = C(2n, n)/(n + 1), so on four keys it is 14, not 24. The distinction is worth holding: 4! = 24 counts the insertion orders, and different orders can build the same tree, which is exactly why the tree count is smaller than the permutation count.The number of ways to choose 3 objects from 10 distinct objects, when order does not matter, is _____.
Numerical answer — type the value.
Show answer
Answer: 120
C(10, 3) = (10 × 9 × 8)/(3 × 2 × 1) = 720/6 = 120. The corresponding ordered count is P(10, 3) = 720, and the factor between them is 3! = 6 — the number of orderings of any one chosen triple. Keeping that relationship in mind is faster than either formula: compute the falling product 10 × 9 × 8 and divide by r! only if order is irrelevant. Note also the symmetry C(10, 3) = C(10, 7), which means a question asking for 7 of 10 has the same answer and should not be recomputed from scratch.The number of distinct binary search trees that can be built from 4 distinct keys is _____.
Numerical answer — type the value.
Show answer
Answer: 14
This is the Catalan number C₄ = C(8, 4)/5 = 70/5 = 14. The recursive argument is the one to reproduce under time pressure: pick which key is the root, and the keys below it and above it are then forced into the left and right subtrees, so Cₙ = Σ Ck·Cn−1−k over the n choices of root. For four keys that is 5 + 2 + 2 + 5 = 14, using C₀ = 1, C₁ = 1, C₂ = 2 and C₃ = 5. The answer is deliberately not 4! = 24: that counts insertion orders, and different orders often build the same tree — which is why the same Catalan number also counts balanced-bracket strings and polygon triangulations.