What are common examiner traps in Combinatorics?

Overcounting/undercounting due to indistinguishable elements in derangement problems (e.g., duplicate letters in words like LILAC). Forgetting directionality in undirected graphs (forgetting to divide cycle permutations by 2 for undirected edges). Mixing up whether order matters (using simple combinations nk instead of combinations with repetition n+k-1k for non-decreasing digit strings). Missing non-homogeneous terms in recurrence relations (e.g., forgetting the 2n-2 term when the target substring condition is satisfied immediately at the suffix). Missing symmetry factors (such as the factor of 2 when either set A precedes B or set B precedes A). Attempting inclusion-exclusion on overlapping consecutive pairs directly instead of using the complement, leading to complex overlapping casework. Forgetting that the first character has k choices while subsequent non-matching positions have (k-1) choices. Off-by-one errors in length exponents (e.g., using 3 × 25 instead of 3 × 25-1). Failing to factor out the leading term in geometric power series before applying (1-x)-n (e.g., (x3 + x4 + )3 = x9(1-x)-3). Miscalculating the requested sequence value (e.g., giving a3 instead of a3 - a0, or omitting the scaling factor K). Double-subtracting or misapplying non-empty constraints in restricted mappings when some bins are already non-empty due to fixed assignments. Arithmetic errors in calculating pairwise and triple set intersections using LCMs in PIE divisibility problems. Multiplying the prime exponents directly without adding 1 to each (i.e., computing Π ai instead of Π (ai + 1)). Incorrect prime factorization of numbers with terminal zeros (e.g., miscounting factors of 2 or 5). Forgetting that p0 = 1 is a valid factor choice for each prime, which leads to the +1 term. Confusing the number of subsets containing a fixed element (2n-1) with the total number of all subsets (2n). Believing that only one representation (summation vs closed form) is mathematically valid rather than recognizing both as equivalent expressions of the same count. Index boundary confusion between k=0 and k=1 (even though 0 n0 = 0, leading terms require careful handling). Forgetting to multiply by x after differentiating, resulting in Σ (2k+1)x2k instead of Σ (2k+1)x2k+1 Sign errors in quotient rule when differentiating rational forms like (x)/(1-x2) Applying operations to the whole sequence instead of splitting into parity components (an = 1 + bn) Misidentifying base cases at n=0 (e.g., treating n=0 as odd)

GATE CSE Combinatorics PYQs

Medium yield8.1% of Engineering Mathematics

GATE evaluates Generating Functions by testing the candidate's ability to find closed-form representations of ordinary generating functions (OGFs) for piecewise… Read the guide

Take topic test

Questions: 19
Asked: since 2012
Total marks: 31
Marks / paper: 1.2

19 GATE CSE Combinatorics PYQs with solutions, from Engineering Mathematics. Browse all GATE CSE PYQs.

Questions

Every official paper that asked this topic, newest first.

What GATE tests in Combinatorics

Concepts, patterns, formulas and traps distilled from past papers.

GATE evaluates Generating Functions by testing the candidate's ability to find closed-form representations of ordinary generating functions (OGFs) for piecewise or parity-dependent sequences. Questions require decomposing sequences linearly and applying operations like substitution (e.g., $x^2$ ) and differentiation to handle polynomial coefficients. These items test analytical fluency with infinite series and discrete mathematics manipulations.

Core concepts

Inclusion-Exclusion Principle and Complementary Counting
Linear and Non-Homogeneous Recurrence Relations
Ordinary Generating Functions (OGF)
Combinations with Repetition / Multiset Coefficients
Restricted Permutations and Generalized Derangements
Graph Substructure Enumeration (Cycles in Kn)
Positional and Relative Order Permutations
Product rule of counting
Complementary counting / Subtraction principle
String/sequence counting over finite alphabets
Adjacency and consecutive symbol constraints
Ordinary Generating Functions (OGF) and negative binomial series
First-order recurrence relations solved by summation formulas
Principle of Inclusion-Exclusion (PIE) for multiple finite sets
Complementary counting in restricted assignments and surjections
Modular exponentiation via Fermat's Little Theorem and cyclicity
Fundamental Theorem of Arithmetic (Prime Factorization)
Product Rule of Combinatorics
Divisor Function d(n)
Double counting (Fubini's principle of counting)
Binomial coefficients and combinatorial identities
Incidence relations between elements and subsets
Summation over subset sizes
Parity and multisection of series (x → x2)
Differentiation and shift operations on power series
Linearity of generating functions
Closed-form rational function representations

Recurring question patterns

Recurrence relation formulation and evaluation
Commonmixed2 marks2015, 2014
Formulating linear or non-homogeneous recurrence relations from combinatorial constraints (e.g., bit strings avoiding/containing patterns or sequences summing to a target) and computing terms or finding the recurrence equation.
Restricted permutations and derangement variants
Commonmixed2 marks2023, 2020
Counting arrangements where certain elements cannot occupy specific positions (derangements with identical characters) or must appear in specific relative orders.
Stars and bars / Multisets / Combinations with repetition
OccasionalNAT1 marks2015
Counting non-decreasing sequences or distributions of identical items into distinct bins, equivalent to $\binom{n+k-1}{k}$ .
Generating functions and closed forms
OccasionalMCQ1 marks2018
Deriving the ordinary generating function $G(x) = \sum a_n x^n$ in closed form for arithmetic or polynomial coefficient sequences.
Inclusion-exclusion and onto function counting
CommonMCQ2 marks2012
Using inclusion-exclusion or complementary counting to determine surjective mappings or structured subgraphs (such as cycles in complete graphs).
Binary representation and weight partitioning
RareNAT2 marks2014
Applying properties of powers of 2 (uniqueness of binary representations) to solve combinatorial identification puzzles.
Complementary Counting on Strings with Adjacency Constraints
OccasionalNAT1 marks2025
Counting the number of strings of a given length over an alphabet of size k that contain at least one instance of consecutive identical symbols, solved by subtracting strings with no consecutive identical symbols from the total possible strings.
Generating Function Coefficient Extraction
CommonNAT2 marks2017, 2016
Given a formal power series or rational generating function (often expressed using $(1-x)^{-k}$ ), determine the coefficient of a specific term $x^r$ or compute an expression like $a_m - a_0$ .
Recurrence Solved via Finite Series Summation
OccasionalNAT2 marks2016
A first-order non-homogeneous recurrence of the form $a_n = a_{n-1} + P(n)$ (where $P(n)$ is a polynomial) is evaluated at a large $n$ using closed-form summation identities.
Principle of Inclusion-Exclusion (Divisibility)
OccasionalNAT2 marks2017
Counting the number of integers in a range $[1, N]$ divisible by at least one of multiple coprime or prime divisors using 3-set PIE.
Constrained Combinatorial Assignment
OccasionalNAT1 marks2021
Distributing distinct objects into distinct categories under specific pinned boundary conditions and non-empty bin requirements using complementary counting.
Modular Exponentiation / Number Theoretic Arithmetic
OccasionalNAT1 marks2019
Computing large powers modulo a prime $a^n \bmod p$ using Fermat's Little Theorem or cyclic period reduction.
Divisor Counting via Prime Factorization
CommonNAT1 marks2015
Given a positive integer $n$ , compute the total number of positive divisors by decomposing $n$ into its canonical prime factorization $n = \prod p_i^{a_i}$ and applying the multiplicative formula $\prod (a_i + 1)$ .
Double Counting of Element-Subset Pairs
RareMCQ1 marks2019
Counting the cardinality of ordered pairs $(x, X)$ where $x \in X$ and $X \subseteq U$ with $|U|=n$ , formulated both element-first ( $n \cdot 2^{n-1}$ ) and subset-cardinality-first ( $\sum_{k=1}^n k \binom{n}{k}$ ).
Closed-Form OGF for Parity-Dependent Sequences
RareMCQ2 marks2022
Given a sequence $a_n$ defined differently for odd and even $n$ (or incorporating polynomial factors on one parity), find the closed-form algebraic expression for $G(x) = \sum_{n=0}^{\infty} a_n x^n$ .

Formulas GATE uses

Surjective functions from n-set to 2-set

2^n - 2

Used when counting onto functions from a set of size $n$ to a set of size 2 by subtracting 2 constant functions.

Cycles of length k in a complete graph $K_n$

\binom{n}{k} \frac{(k-1)!}{2}

Used to count undirected simple cycles of length $k$ on $n$ labeled vertices.

Combinations with repetition (Multiset coefficient)

\binom{n+k-1}{k}

Used to count non-decreasing sequences of length $k$ using $n$ distinct symbols or distributing $k$ identical items into $n$ distinct bins.

Generating function for linear sequences

\sum_{n=0}^{\infty} x^n = \frac{1}{1-x}, \quad \sum_{n=0}^{\infty} n x^n = \frac{x}{(1-x)^2}

Used to convert sequences of the form $a_n = c_1 n + c_2$ into rational closed-form generating functions.

Ordered partition recurrence (Fibonacci type)

P(n) = P(n-1) + P(n-2)

Used when an $n$ -sum composition is formed using step sizes of 1 and 2.

Total Strings of Fixed Length

|U| = k^n

Used to find total number of length- $n$ strings over an alphabet of size $k$ .

Strings without Consecutive Identical Characters

|A^c| = k(k-1)^{n-1}

Used to count strings where no two adjacent positions have the same character.

Principle of Complementary Counting

|A| = |U| - |A^c|

Used when counting strings containing 'at least one' occurrence of an event is harder than counting zero occurrences.

Negative Binomial Series Expansion

(1 - x)^{-n} = \sum_{r=0}^{\infty} \binom{n + r - 1}{r} x^r = \sum_{r=0}^{\infty} \binom{n + r - 1}{n - 1} x^r

Used to find coefficients of terms in ordinary generating functions.

Principle of Inclusion-Exclusion (3 Sets)

|A \cup B \cup C| = |A| + |B| + |C| - (|A \cap B| + |B \cap C| + |C \cap A|) + |A \cap B \cap C|

Used when counting elements satisfying at least one of three divisibility or property criteria.

Sum of First n Squares

\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}

Used in telescoping recurrence relations involving quadratic polynomial increments.

Sum of First n Integers

\sum_{k=1}^{n} k = \frac{n(n+1)}{2}

Used in telescoping recurrence relations involving linear polynomial increments.

Fermat's Little Theorem

a^{p-1} \equiv 1 \pmod p \quad \text{for prime } p \text{ where } \gcd(a, p) = 1

Used to reduce large exponent modulo calculations.

Number of Positive Divisors Function ($d(n)$ or $\tau(n)$)

d(n) = \prod_{i=1}^{k} (a_i + 1) \quad \text{where } n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}

Used to find the total count of positive integer divisors of a given integer $n$ given its prime factorization.

Absorption Identity for Binomial Coefficients

k \binom{n}{k} = n \binom{n-1}{k-1}

Used to simplify summation terms containing an index multiplied by a binomial coefficient.

Binomial Identity for Derivative / First Moment Sum

\sum_{k=1}^n k \binom{n}{k} = n 2^{n-1}

Used when counting the total number of element-subset incidence pairs $(x, X)$ with $x \in X \subseteq U$ where $|U|=n$ .

Ordinary Generating Function (OGF)

G(x) = \sum_{n=0}^{\infty} a_n x^n

Fundamental definition used to convert a discrete sequence into a power series.

Geometric Series Sum

\sum_{n=0}^{\infty} x^n = \frac{1}{1-x} \quad \text{and} \quad \sum_{k=0}^{\infty} x^{2k+1} = \frac{x}{1-x^2}

Summing infinite constant sequences over all integers or restricted parities.

Index Multiplication via Differentiation

x \frac{d}{dx} f(x) = \sum_{n=0}^{\infty} n c_n x^n \quad \text{where } f(x) = \sum_{n=0}^{\infty} c_n x^n

Generating linear factors (like $(2k+1)$ or $n$ ) attached to series coefficients.

Examiner traps in Combinatorics

Overcounting/undercounting due to indistinguishable elements in derangement problems (e.g., duplicate letters in words like LILAC).
Forgetting directionality in undirected graphs (forgetting to divide cycle permutations by 2 for undirected edges).
Mixing up whether order matters (using simple combinations nk instead of combinations with repetition n+k-1k for non-decreasing digit strings).
Missing non-homogeneous terms in recurrence relations (e.g., forgetting the 2n-2 term when the target substring condition is satisfied immediately at the suffix).
Missing symmetry factors (such as the factor of 2 when either set A precedes B or set B precedes A).
Attempting inclusion-exclusion on overlapping consecutive pairs directly instead of using the complement, leading to complex overlapping casework.
Forgetting that the first character has k choices while subsequent non-matching positions have (k-1) choices.
Off-by-one errors in length exponents (e.g., using 3 × 25 instead of 3 × 25-1).
Failing to factor out the leading term in geometric power series before applying (1-x)-n (e.g., (x3 + x4 + )3 = x9(1-x)-3).
Miscalculating the requested sequence value (e.g., giving a3 instead of a3 - a0, or omitting the scaling factor K).
Double-subtracting or misapplying non-empty constraints in restricted mappings when some bins are already non-empty due to fixed assignments.
Arithmetic errors in calculating pairwise and triple set intersections using LCMs in PIE divisibility problems.
Multiplying the prime exponents directly without adding 1 to each (i.e., computing Π ai instead of Π (ai + 1)).
Incorrect prime factorization of numbers with terminal zeros (e.g., miscounting factors of 2 or 5).
Forgetting that p0 = 1 is a valid factor choice for each prime, which leads to the +1 term.
Confusing the number of subsets containing a fixed element (2n-1) with the total number of all subsets (2n).
Believing that only one representation (summation vs closed form) is mathematically valid rather than recognizing both as equivalent expressions of the same count.
Index boundary confusion between k=0 and k=1 (even though 0 n0 = 0, leading terms require careful handling).
Forgetting to multiply by x after differentiating, resulting in Σ (2k+1)x2k instead of Σ (2k+1)x2k+1
Sign errors in quotient rule when differentiating rational forms like (x)/(1-x2)
Applying operations to the whole sequence instead of splitting into parity components (an = 1 + bn)
Misidentifying base cases at n=0 (e.g., treating n=0 as odd)

How questions are asked

Recurrence relation setup from string constraints
Numeric answer for word permutations with fixed/banned positions
Closed-form ordinary generating function identification
Abstract counting formula derivation with subsets and permutations
Integer composition / step-counting sequences
Numerical calculation of constrained strings of fixed length
Extract coefficient in algebraic power series expansion
Compute value/coefficient ratio K from a polynomial recurrence
Range divisibility count using inclusion-exclusion
Constrained job-to-machine assignment counting
Modular arithmetic reduction ab mod m
Direct integer calculation in a fill-in-the-blank NAT prompt
Multi-statement correctness evaluation (Statement I / Statement II)
Closed-form identification for piecewise sequence

Paper trends

Shift from basic formula identification (onto functions, cycles) towards constructive NAT problems involving case casework and derangements.
2020, 2014, 2012
Introduction of abstract algebraic combinatorial questions involving parameterized sets and order relations.
2023
Direct numerical-answer counting problems evaluating elementary combinatorial principles like complementary counting are featured as concise 1-mark NAT questions.
2025
Exclusively tested as NAT questions across the sampled years, demanding exact integer computation without multiple-choice elimination.
2021, 2019, 2017, 2016
Higher-weight 2-mark questions focus on generating function expansions and 3-set PIE, while 1-mark questions assess direct modular arithmetic or assignment principles.
2021, 2019, 2017, 2016
Direct calculation items on elementary combinatorics/number theory are placed as 1-mark NAT questions without multiple-choice options, testing arithmetic precision and basic divisor function application.
2015
Emphasis on multi-statement verification where both closed-form and summation representations of the same combinatorial quantity must be identified as valid.
2019
Appears as a 2-mark calculus/algebra-heavy discrete mathematics question requiring series differentiation and algebraic simplification rather than simple recurrence solving.
2022

Difficulty notes

Easy: Direct closed-form formula substitution or standard generating function expansions (1 mark). Medium: Multi-step case breakdowns (such as derangements with duplicate items, recurrence derivations for substring constraints, or parameterized permutation problems) (2 marks).