GATE CS & DA Preparation Guide Module 4 – Engineering mathematics (CS section 1; DA sections 1-3)
Graphs, counting, recurrences, generating functions
GATE CS combinatorics by problem family: counting rules, derangements, Catalan numbers, recurrences, generating functions and graph theory.
What you will learn
- Apply counting rules, inclusion-exclusion, the pigeonhole principle and stars and bars to GATE-style NATs
- Solve linear recurrences and use generating functions to count
- Answer graph questions on connectivity, matchings, colouring, planarity and degree sequences
Before you start
What you’ll learn · Before you start
What you will learn
- Apply counting rules, inclusion-exclusion, the pigeonhole principle and stars and bars to GATE-style NATs
- Solve linear recurrences and use generating functions to count
- Answer graph questions on connectivity, matchings, colouring, planarity and degree sequences
Before you start
On this page
Section 1 of the GATE CS syllabus lists graphs (connectivity, matching, colouring) and combinatorics (counting, recurrence relations, generating functions), and the DA paper’s probability section begins with counting, so both papers need the counting half. Counting questions ask for one exact number, the shape of a NAT: Numerical answer type question: no options. The answer is a number typed on the screen's keypad, right when it falls inside the key's range; a wrong one costs nothing. More in “MCQ, MSQ and NAT: GATE marking and when to guess”, which makes them dependable marks once the method is fixed: decide whether the objects and the boxes are distinct and what each box may hold, pick the formula, and check it on a small case by listing. Recurrences reduce to the roots of a characteristic equation: The equation a linear recurrence gives when a(n) = rⁿ is tried: for a(n) = 5a(n − 1) − 6a(n − 2) it is r² − 5r + 6 = 0, and its roots 2 and 3 give a(n) = A · 2ⁿ + B · 3ⁿ.. Generating functions turn a counting question into reading one coefficient of a power series. Questions on graphs rest on a handful of counting facts, the handshake lemma: The degrees of a graph's vertices add up to twice its number of edges, because each edge is counted once at each end. So the number of vertices of odd degree is even. first. This lesson gives the decision diagram, checks six counting families by brute force and solves five problems.
Not affiliated
MySmartCoPilot has no tie to the institutes that conduct GATE. The clauses on graphs and combinatorics come from the official CS and DA syllabus PDFs, which decide what may be asked.
Objects into boxes: one decision picks the formula
Follow a question down the diagram: the kind of objects picks the branch, and what a box may hold picks the formula.
Which formula counts k objects in n distinct boxes
Text description of the diagram
The diagram starts from one box at the top, "k objects into n distinct boxes", with an arrow down to the question "Objects distinct?". Two arrows leave the question.
The arrow labelled "yes" leads down to the right, to a group titled "Yes: each object picks a box", with three formulas:
- any number of objects per box: n^k, because each of the k objects chooses one of n boxes;
- at most one object per box: n!/(n-k)!, the number of ordered choices of k different boxes;
- no box empty: inclusion-exclusion, the sum over i of (-1)^i C(n, i) (n - i)^k.
The arrow labelled "no" leads down to the left, to a group titled "No: only the box sizes matter", with two formulas:
- any number of objects per box: C(k + n - 1, n - 1), the stars-and-bars count;
- no box empty: C(k - 1, n - 1), stars and bars after putting one object in each box first.
Most counting questions put k objects into n boxes, even when they talk about seats, envelopes or digits. When the objects are distinct, each object chooses its box. When they are identical, only how many land in each box matters, and stars and bars: A count of the ways to put k identical objects into n distinct boxes: k stars and n − 1 bars in a row, so C(k + n − 1, n − 1) ways, or C(k − 1, n − 1) with no box empty. counts the ways: k stars and n − 1 bars in a row. The pigeonhole principle is the same picture read backwards: with n + 1 objects in n boxes, some box holds at least two, as 3 objects in 2 boxes show.
1. Stars and bars (NAT). x₁ + x₂ + x₃ = 10 has C(12, 2) = 66 solutions in non-negative integers and C(9, 2) = 36 in positive integers.
Checkpoint
Check: Objects into boxes
Four more families, each confirmed by listing small cases
- Arrangements with a restriction: count them all and subtract the bad ones. Four people in a row with two kept apart: 24 − 12 = 12.
- Derangements: Dₙ = n! (1 − 1/1! + 1/2! − ⋯ ± 1/n!), the orderings that leave nothing in place. D₄ = 9.
- Catalan numbers: C(2n, n)/(n + 1). For n = 3 there are 5.
- Inclusion–exclusion: add the single sets, subtract the pairs, add the triples: |A ∪ B| = |A| + |B| − |A ∩ B|.
Catalan numbers count balanced bracket strings, binary search tree shapes and stack-sortable orders, which is why they appear in data-structure questions too.
2. Derangements (NAT). Five letters can go into five addressed envelopes with every letter in a wrong envelope in D₅ = 44 ways.
3. Catalan (NAT). Four distinct keys can form C₄ = C(8, 4)/5 = 14 binary search trees of different shapes.
The program lists every case of six families, these four and stars and bars with and without empty boxes, and compares each count with its formula:
from itertools import permutations, product
from math import comb, factorial
def not_adjacent(n):
"""People 0..n-1 in a row, with persons 0 and 1 never side by side."""
return sum(abs(p.index(0) - p.index(1)) > 1 for p in permutations(range(n)))
def identical_into_boxes(k, n, at_least=0):
"""k identical objects into n distinct boxes: count the tuples of box sizes that add up to k."""
return sum(sum(c) == k for c in product(range(at_least, k + 1), repeat=n))
def derangements(n):
"""Orderings of 0..n-1 in which no item stays in its own place."""
return sum(all(p[i] != i for i in range(n)) for p in permutations(range(n)))
def onto(k, n):
"""Functions from k distinct objects onto n distinct boxes (no box empty)."""
return sum(len(set(f)) == n for f in product(range(n), repeat=k))
def balanced(n):
"""Strings of n '(' and n ')' that never close more brackets than they have opened."""
count = 0
for s in product("()", repeat=2 * n):
depth = 0
for ch in s:
depth += 1 if ch == "(" else -1
if depth < 0:
break
count += depth == 0
return count
def derangements_formula(n):
return sum((-1) ** i * factorial(n) // factorial(i) for i in range(n + 1))
families = [
("row of n, two people apart", [4, 5, 6, 7], not_adjacent, lambda n: factorial(n) - 2 * factorial(n - 1), "n! - 2(n-1)!"),
("10 identical into n boxes", [2, 3, 4], lambda n: identical_into_boxes(10, n), lambda n: comb(10 + n - 1, n - 1), "C(10+n-1, n-1)"),
("10 identical, none empty", [2, 3, 4], lambda n: identical_into_boxes(10, n, 1), lambda n: comb(9, n - 1), "C(9, n-1)"),
("derangements of n", [4, 5, 6, 7], derangements, derangements_formula, "n! (1 - 1/1! + ... )"),
("6 distinct onto n boxes", [2, 3, 4], lambda n: onto(6, n), lambda n: sum((-1) ** i * comb(n, i) * (n - i) ** 6 for i in range(n + 1)), "inclusion-exclusion"),
("balanced brackets, n pairs", [3, 4, 5, 6, 7], balanced, lambda n: comb(2 * n, n) // (n + 1), "C(2n, n)/(n+1)"),
]
for name, ns, brute, formula, how in families:
found = [brute(n) for n in ns]
expected = [formula(n) for n in ns]
verdict = "agree" if found == expected else "DIFFER"
print(f"{name:<28} n = {ns}: {found} {how}: {verdict}")Output
row of n, two people apart n = [4, 5, 6, 7]: [12, 72, 480, 3600] n! - 2(n-1)!: agree 10 identical into n boxes n = [2, 3, 4]: [11, 66, 286] C(10+n-1, n-1): agree 10 identical, none empty n = [2, 3, 4]: [9, 36, 84] C(9, n-1): agree derangements of n n = [4, 5, 6, 7]: [9, 44, 265, 1854] n! (1 - 1/1! + ... ): agree 6 distinct onto n boxes n = [2, 3, 4]: [62, 540, 1560] inclusion-exclusion: agree balanced brackets, n pairs n = [3, 4, 5, 6, 7]: [5, 14, 42, 132, 429] C(2n, n)/(n+1): agree
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 count_check.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
Every family agrees with its formula for every n tried. Listing is slow, but it is exact, and a program that lists the cases for n = 4 is the best check on a formula you are about to use for n = 10.
Permutation & Combination Calculator Check a C(n, k) or P(n, k) value before you build a larger count on it.Checkpoint
Check: Derangements, Catalan numbers and complements
Recurrences: the roots of one equation give the closed form
A linear recurrence such as a(n) = 5a(n − 1) − 6a(n − 2) is solved by trying a(n) = rⁿ. The characteristic equation r² − 5r + 6 = 0 has roots 2 and 3, so a(n) = A · 2ⁿ + B · 3ⁿ, and the initial values fix A and B.
4. Recurrence (MCQ). With a(0) = 2 and a(1) = 5, A + B = 2 and 2A + 3B = 5 give A = B = 1, so a(n) = 2ⁿ + 3ⁿ and a(5) = 32 + 243 = 275. Step through the same solution:
The drawing shows the whole scene; its 6 steps are listed below.
Every step as text
- Guess rⁿ. A linear recurrence with constant coefficients is solved by trying a(n) = rⁿ. Substituting gives rⁿ = 5rⁿ⁻¹ − 6rⁿ⁻², and dividing by rⁿ⁻² leaves an equation in r alone.
- The equation in r. That equation, r² − 5r + 6 = 0, is the characteristic equation of the recurrence. Its coefficients 1, −5 and 6 come straight from the recurrence.
- Its roots. It factors as (r − 2)(r − 3) = 0, so its roots are 2 and 3. Both 2ⁿ and 3ⁿ satisfy the recurrence.
- The general solution. Any combination of the two solutions satisfies the recurrence as well, so for two distinct roots the general solution is a(n) = A · 2ⁿ + B · 3ⁿ.
- Fit the initial values. The initial values fix the constants: a(0) = A + B = 2 and a(1) = 2A + 3B = 5. Subtracting twice the first equation from the second gives B = 1, so A = 1.
- The value asked for. So a(n) = 2ⁿ + 3ⁿ, and the a(5) the question asks for is 2⁵ + 3⁵ = 32 + 243 = 275.
A generating function stores a sequence as the coefficients of a power series. The ways to choose amounts with a given total are then one coefficient of a product, with one factor per choice.
Checkpoint
Check: Solving linear recurrences
Graphs: most questions start from the degrees
For graphs, the facts that settle most questions are short. The degrees add up to twice the number of edges, so the number of odd-degree vertices is even. A connected graph has an Euler circuit exactly when every degree is even. A connected planar graph satisfies v − e + f = 2. There are nⁿ⁻² labelled trees on n vertices.
5. Handshake (NAT). A simple graph with degrees 4, 3, 3, 2 and 2 has 14/2 = 7 edges. Step through one such graph, built an edge at a time:
The drawing shows the whole scene; its 9 steps are listed below.
Every step as text
- No edges. Five vertices and no edges yet. Every degree is 0, and so is their sum.
- Edge 1, A–B. The edge A–B adds 1 to the degree of A and 1 to the degree of B. The sum of the degrees is now 2.
- Edge 2, A–C. A–C raises A to 2 and C to 1. Two more for the sum, which is now 4.
- Edge 3, A–D. A–D raises A to 3 and D to 1, and the sum to 6.
- Edge 4, A–E. A–E gives A its fourth edge and E its first. The sum is 8, twice the 4 edges so far.
- Edge 5, B–C. B–C raises B and C to 2 each. The sum is 10.
- Edge 6, B–D. B–D raises B to 3 and D to 2. The sum is 12.
- Edge 7, C–E. C–E raises C to 3 and E to 2. The degrees are now 4, 3, 3, 2 and 2, and their sum is 14.
- Twice the edges. The degrees add up to 14, twice the 7 edges, because every edge was counted once at each end. The two odd degrees, B's 3 and C's 3, come as a pair, as they must.
Each edge added 2 to the sum, once at each end, so the sum of the degrees is always even, and the odd degrees always come in pairs.
Checkpoint
Check: Degrees, Euler circuits and planar graphs
Practise: counting and graphs in GATE’s formats
Practise all four ideas, starting with the one you know least.
Practice that adapts to you
Practise this lesson
12 questions about 6 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.
Counting and recurrences: each formula derived and checked by program Pro: opens with a Pro, Premium or Ultimate pass
Every formula in this module comes from a few arguments, and knowing them is what saves a question whose wording hides the family. This part derives them, solves three recurrences three ways and reads counts off generating functions.
In this part:
- Inclusion–exclusion worked: onto maps and derangements from one formula
- Catalan numbers: three objects, one count, worked to n = 5
- Recurrences solved three ways, checked against SymPy
- Generating functions: reading a coefficient, checked three ways
- Count k objects in n boxes for all four cases
- Results of the sample tests
2 runnable examples (Python) · 1 exercise with sample tests · about 5 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Graph questions: bounds, degree sequences, colouring and planarity checked Pro: opens with a Pro, Premium or Ultimate pass
Many graph questions are counting questions in disguise, and every bound they use can be checked on small graphs. This part counts all graphs on five labelled vertices, tests degree sequences and colourings by program, and ends with a ten-minute set with answers.
In this part:
- All 1,024 graphs on five labelled vertices, counted
- Degree sequences, colourings and planarity, tested
- Matchings: Hall’s condition, with a failing case worked
- A ten-minute set, with answers
1 diagram · 2 runnable examples (Python) · about 6 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Interview questions
-
Fresher · Warm-up
When do you count placements with n to the power k, and when with stars and bars?
Both count k objects in n distinct boxes; the difference is whether the objects can be told apart. If they are distinct, such as people choosing hostels, each object chooses its box on its own, which gives n to the power k. If they are identical, such as sweets or marks to distribute, two placements with the same number in every box are the same placement, and stars and bars counts them: k stars and n − 1 bars in a row, C(k + n − 1, n − 1). For 4 objects and 3 boxes that is 81 against 15. When every box must get something, the identical case becomes C(k − 1, n − 1), and the distinct case needs inclusion–exclusion.
-
Fresher to mid
A simple graph has 20 vertices and exactly 3 connected components. What is the largest number of edges it can have, and how do you show that no graph does better?
-
Fresher to mid
A NAT gives a(n) = 6a(n − 1) − 9a(n − 2) with a(0) = 2 and a(1) = 3 and asks for a(5). A candidate writes a(n) = A · 3ⁿ + B · 3ⁿ. What goes wrong, what is the right form, and how do you check the value?
-
Fresher to mid
How many bit strings of length 10 contain no two consecutive 1s? Derive the count in a way that would also handle "no three consecutive 1s".
Key takeaways
- Decide first whether the objects and the boxes are distinct and what a box may hold; the formula follows, and a listing for n = 4 confirms it.
- Counting by complement, stars and bars, derangements and Catalan numbers are the families to recognise first.
- Linear recurrences reduce to the roots of their characteristic equation; generating functions reduce counting to reading a coefficient.
- For graphs, start from the handshake lemma and the parity of the degrees.
Terms in this lesson
- characteristic equation
- The equation a linear recurrence gives when a(n) = rⁿ is tried: for a(n) = 5a(n − 1) − 6a(n − 2) it is r² − 5r + 6 = 0, and its roots 2 and 3 give a(n) = A · 2ⁿ + B · 3ⁿ.
- handshake lemma
- The degrees of a graph's vertices add up to twice its number of edges, because each edge is counted once at each end. So the number of vertices of odd degree is even.
- stars and bars
- A count of the ways to put k identical objects into n distinct boxes: k stars and n − 1 bars in a row, so C(k + n − 1, n − 1) ways, or C(k − 1, n − 1) with no box empty.
References
- GATE 2027 syllabus, Computer Science and Information Technology (section 1) (Indian Institute of Technology Madras (GATE 2027))
- GATE 2027 syllabus, Data Science and Artificial Intelligence (section 1) (Indian Institute of Technology Madras (GATE 2027))
- Mathematics for Computer Science (chapters on counting, generating functions, recurrences and graphs) (Massachusetts Institute of Technology (Lehman, Leighton and Meyer))
- NIST Digital Library of Mathematical Functions, chapter 26: combinatorial analysis (National Institute of Standards and Technology)
- A001187: number of connected labelled graphs with n nodes (The OEIS Foundation)
- A000108: Catalan numbers (The OEIS Foundation)
- SymPy: solving recurrences with rsolve (SymPy Development Team)
- itertools: permutations, product and combinations (Python Software Foundation)
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress