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 x1-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)

Combinatorics

19 Qs · since 2012 · 31 marks · 1.2 marks/paperMedium yield

Take topic test

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… Guide

Type

GATE CSE 2025 Set 1Q30NAT1 markEasyLet $S$ be the set of all ternary strings defined over the alphabet $\{a, b, c\}$ . Consider all strings in $S$ that contain at least one occurrence of two consecutive symbols, that is, “aa”, “bb” or “cc”. The number of such strings of length 5 that are possible is ________. (Answer in integer)
GATE CSE 2023Q48MCQ2 marksMediumLet $U = \{1, 2, \dots, n\}$ , where $n$ is a large positive integer greater than 1000. Let $k$ be a positive integer less than $n$ . Let $A, B$ be subsets of $U$ with $|A| = |B| = k$ and $A \cap B = \emptyset$ . We say that a permutation of $U$ separates $A$ from $B$ if one of the following is…
GATE CSE 2022Q36MCQ2 marksMediumWhich one of the following is the closed form for the generating function of the sequence $\{ a_n \}_{n \ge 0}$ defined below? $a_n = \begin{cases} n+1, & n \text{ is odd} \\ 1, & \text{otherwise} \end{cases}$
GATE CSE 2021 Set 1Q19NAT1 markMediumThere are 6 jobs with distinct difficulty levels, and 3 computers with distinct processing speeds. Each job is assigned to a computer such that: - The fastest computer gets the toughest job and the slowest computer gets the easiest job. - Every computer gets at least one job. The number of ways in which this can be…
GATE CSE 2020Q42NAT2 marksMediumThe number of permutations of the characters in LILAC so that no character appears in its original position, if the two L’s are indistinguishable, is _________.
GATE CSE 2019Q5MCQ1 markMediumLet $U = \{1,2, \dots, n\}$ . Let $A = \{(x, X)|x \in X, X \subseteq U\}$ . Consider the following two statements on $|A|$ . I. $|A| = n2^{n-1}$ II. $|A| = \sum_{k=1}^n k \binom{n}{k}$ Which of the above statements is/are TRUE?
GATE CSE 2019Q21NAT1 markEasyThe value of $3^{51} \bmod 5$ is _______.
GATE CSE 2018Q1MCQ1 markEasyWhich one of the following is a closed form expression for the generating function of the sequence $\{a_n\}$ , where $a_n = 2n + 3$ for all $n = 0, 1, 2, \dots$ ?
GATE CSE 2017 Set 1Q47NAT2 marksMediumThe number of integers between 1 and 500 (both inclusive) that are divisible by 3 or 5 or 7 is ________.
GATE CSE 2017 Set 2Q47NAT2 marksMediumIf the ordinary generating function of a sequence $\{a_n\}_{n=0}^{\infty}$ is $\frac{1+z}{(1-z)^3}$ , then $a_3 - a_0$ is equal to ________.
GATE CSE 2016 Set 1Q26NAT2 marksEasyThe coefficient of $x^{12}$ in $(x^3 + x^4 + x^5 + x^6 + \cdots)^3$ is ________ .
GATE CSE 2016 Set 1Q27NAT2 marksMediumConsider the recurrence relation $a_1 = 8$ , $a_n = 6n^2 + 2n + a_{n-1}$ . Let $a_{99} = K \times 10^4$ . The value of $K$ is ________ .
GATE CSE 2015 Set 1Q49MCQ2 marksMediumLet $a_n$ represent the number of bit strings of length $n$ containing two consecutive 1s. What is the recurrence relation for $a_n$ ?
GATE CSE 2015 Set 2Q9NAT1 markEasyThe number of divisors of 2100 is ______.
GATE CSE 2015 Set 3Q5NAT1 markMediumThe number of 4 digit numbers having their digits in non-decreasing order (from left to right) constructed by using the digits belonging to the set $\{1, 2, 3\}$ is ________.
GATE CSE 2014 Set 1Q37NAT2 marksEasyThere are 5 bags labeled 1 to 5. All the coins in a given bag have the same weight. Some bags have coins of weight 10 gm, others have coins of weight 11 gm. I pick 1, 2, 4, 8, 16 coins respectively from bags 1 to 5. Their total weight comes out to 323 gm. Then the product of the labels of the bags having 11 gm coins…
GATE CSE 2014 Set 1Q49NAT2 marksMediumA pennant is a sequence of numbers, each number being 1 or 2. An $n$ -pennant is a sequence of numbers with sum equal to $n$ . For example, $(1,1,2)$ is a 4-pennant. The set of all possible 1-pennants is $\{(1)\}$ , the set of all possible 2-pennants is $\{(2), (1,1)\}$ and the set of all 3-pennants is $\{(2,1), (1,1,1), (1,2)\}$ …
GATE CSE 2012Q37MCQ2 marksEasyHow many onto (or surjective) functions are there from an $n$ -element ( $n \ge 2$ ) set to a 2-element set?
GATE CSE 2012Q38MCQ2 marksMediumLet G be a complete undirected graph on 6 vertices. If vertices of G are labeled, then the number of distinct cycles of length 4 in G is equal to

Topic guide

What does GATE test in Combinatorics?

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
common · mixed · 2 marks · 2015, 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
common · mixed · 2 marks · 2023, 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
occasional · NAT · 1 marks · 2015
Counting non-decreasing sequences or distributions of identical items into distinct bins, equivalent to $\binom{n+k-1}{k}$ .
Generating functions and closed forms
occasional · MCQ · 1 marks · 2018
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
common · MCQ · 2 marks · 2012
Using inclusion-exclusion or complementary counting to determine surjective mappings or structured subgraphs (such as cycles in complete graphs).
Binary representation and weight partitioning
rare · NAT · 2 marks · 2014
Applying properties of powers of 2 (uniqueness of binary representations) to solve combinatorial identification puzzles.
Complementary Counting on Strings with Adjacency Constraints
occasional · NAT · 1 marks · 2025
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
common · NAT · 2 marks · 2017, 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
occasional · NAT · 2 marks · 2016
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)
occasional · NAT · 2 marks · 2017
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
occasional · NAT · 1 marks · 2021
Distributing distinct objects into distinct categories under specific pinned boundary conditions and non-empty bin requirements using complementary counting.
Modular Exponentiation / Number Theoretic Arithmetic
occasional · NAT · 1 marks · 2019
Computing large powers modulo a prime $a^n \bmod p$ using Fermat's Little Theorem or cyclic period reduction.
Divisor Counting via Prime Factorization
common · NAT · 1 marks · 2015
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
rare · MCQ · 1 marks · 2019
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
rare · MCQ · 2 marks · 2022
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 x1-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 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).