GATE CSE Engineering Mathematics Formula Sheet: Counting to Calculus

Q: How many onto functions are there from an m-set to an n-set?

Use inclusion and exclusion: the count is Σₖ₌₀ⁿ (-1)ᵏ C(n, k) (n-k)ᵐ. Start with all nᵐ functions, remove those that miss at least one element of the codomain, and add back the double removals. From a 4-set to a 2-set this gives 16 - 2 = 14. From a 6-set to a 3-set it gives 540, not 3⁶.

Q: How many reflexive and symmetric relations are there on a set of n elements?

There are 2^(n(n-1)/2). Reflexivity fixes all n diagonal pairs, so only the off-diagonal pairs are free. Symmetry ties each pair (a, b) to (b, a), which leaves n(n-1)/2 independent choices. Writing 2^(n(n+1)/2) is the classic mistake, because that is the count of symmetric relations without the reflexive condition.

Q: What are the mean and variance of the exponential and Poisson distributions?

An exponential distribution with rate lambda has mean 1/λ and variance 1/λ², and it is memoryless. A Poisson count over an interval of length t has mean and variance both equal to lambda times t. Always rescale the rate to the interval the question asks about, for example a per-hour rate for a 20-minute window.

By MD ANISH AHAMADUpdated 4 Oct 20267 min read

GATE CSE Engineering Mathematics Formula Sheet: Counting to Calculus

Engineering Mathematics in GATE CSE rewards a small set of exact formulas: counting rules, relation counts, graph bounds, eigenvalue properties, named distributions and a few calculus results. The official pattern gives the section about 13 of the 100 marks; check the current notification. This sheet goes deeper than the general GATE CSE formula sheet, with a one-line worked example and the trap for every formula.

In this guide

Key takeaways
The terms this sheet uses
Counting functions and arrangements
Counting relations on an n-element set
Linear recurrences
Graph theory bounds and counts
Linear algebra: eigenvalues, determinants and rank
Probability: conditioning, expectation and distributions
Calculus: limits, extrema and integrals
Quick revision

Key takeaways

Onto functions, derangements and inclusion and exclusion all come from one idea: count everything, then subtract the bad cases.
Reflexive and symmetric relations on $n$ elements number $2^{n(n-1)/2}$ , not $2^{n(n+1)/2}$ .
A connected planar graph satisfies $v - e + f = 2$ ; bipartite planar graphs have the tighter bound $e \le 2v - 4$ .
Eigenvalues sum to the trace and multiply to the determinant, and they follow powers, inverses and shifts of a single matrix.
For independent variables, $\text{Var}(X - Y)$ adds the variances; it never subtracts them.
On a closed interval, the absolute maximum can sit at an endpoint, so always check both ends.

The terms this sheet uses

A function from an $m$ -set to an $n$ -set sends each of the $m$ elements to one of the $n$ . It is injective if no two elements share an image and onto if every element of the codomain is hit.
A relation on a set is any set of ordered pairs. It is reflexive if every $(a, a)$ is in it and symmetric if $(a, b)$ in it forces $(b, a)$ .
A graph is planar if it can be drawn with no crossing edges. Its chromatic number $\chi$ is the fewest colours that give adjacent vertices different colours.
An eigenvalue $\lambda$ of a matrix $A$ satisfies $A\mathbf{x} = \lambda \mathbf{x}$ for some non-zero $\mathbf{x}$ . The trace is the sum of the diagonal entries.
Conditional probability $P(A \mid B)$ is the probability of $A$ once $B$ is known to have happened.

Counting functions and arrangements

Most counting questions are one of these rules with a twist in the condition.

Formula	One-line example	Watch out for
All functions: $n^{m}$	3-set to 2-set: $2^{3} = 8$	Base is the codomain size
Injective: $\displaystyle \dfrac{n!}{(n - m)!}$	3-set to 5-set: $5 \times 4 \times 3 = 60$	Zero when $m > n$
Onto: $\sum_{k=0}^{n} (-1)^{k} \binom{n}{k} (n - k)^{m}$	4-set to 2-set: $16 - 2 = 14$	6-set to 3-set is 540, not $3^{6}$
Derangements: $\displaystyle D_n = n! \sum_{k=0}^{n} \dfrac{(-1)^{k}}{k!}$	$D_4 = 9$ ; sequence 1, 0, 1, 2, 9, 44, 265	Starts at $n = 0$
Stars and bars: $\binom{n + k - 1}{k - 1}$	$x_1 + x_2 + x_3 = 5$ : $\binom{7}{2} = 21$	Non-negative solutions only
Pigeonhole: some box holds $\ge \lceil n/k \rceil$	25 objects, 6 boxes: some box has 5	To force $k + 1$ in one box you need $k \times \text{boxes} + 1$
Non-adjacent $k$ -subsets of $\{1, \dots, n\}$ : $\binom{n - k + 1}{k}$	$n = 6$ , $k = 2$ : $\binom{5}{2} = 10$	Check against $15 - 5$ adjacent pairs
Binary strings with no two adjacent 1s: $F_{n+2}$	Length 4: $F_6 = 8$	Fix the Fibonacci indexing first

Trap: In inclusion and exclusion, subtract every pairwise intersection once and add every triple back once. Double-subtracting an intersection is the usual slip.

Counting relations on an n-element set

There are $n^{2}$ ordered pairs, and each condition fixes or ties some of them. With $n = 3$ the counts are easy to check by hand.

Relations of this kind	Formula	Value for $n = 3$
All	$2^{n^{2}}$	512
Reflexive	$2^{n^{2} - n}$	64
Symmetric	$2^{n(n+1)/2}$	64
Reflexive and symmetric	$2^{n(n-1)/2}$	8
Antisymmetric	$2^{n} \times 3^{n(n-1)/2}$	216
Asymmetric	$3^{n(n-1)/2}$	27
Equivalence	Bell number: 1, 1, 2, 5, 15, 52, 203	5

For groups, Lagrange's theorem says the order of a subgroup divides the order of the group. The cyclic group $\mathbb{Z}_n$ has $\varphi(n)$ generators and $\tau(n)$ subgroups, so $\mathbb{Z}_{12}$ has 4 generators and 6 subgroups.

Linear recurrences

For $a_n = p\,a_{n-1} + q\,a_{n-2}$ , solve the characteristic equation $r^{2} - pr - q = 0$ . Distinct roots give $a_n = A r_1^{n} + B r_2^{n}$ , and a repeated root gives $a_n = (A + Bn)\,r^{n}$ .

Worked example. For $a_n = 5a_{n-1} - 6a_{n-2}$ , the equation is $r^{2} - 5r + 6 = 0$ , so $r = 2, 3$ and $a_n = A \cdot 2^{n} + B \cdot 3^{n}$ .

Graph theory bounds and counts

Formula	One-line example	Watch out for
$\sum \deg(v) = 2e$	10 vertices of degree 3: $e = 15$	An odd degree sum is impossible
Connected planar: $v - e + f = 2$	$v = 8$ , $e = 12$ : $f = 6$	$f$ counts the outer face
Planar, $v \ge 3$ : $e \le 3v - 6$	$v = 10$ : $e \le 24$	Necessary, not sufficient
Bipartite planar: $e \le 2v - 4$	$K_{3,3}$ : $9 > 8$ , so non-planar	Use this, not $3v - 6$ , for triangle-free graphs
Spanning trees: $K_n$ has $n^{n-2}$ ; $K_{m,n}$ has $m^{n-1} n^{m-1}$	$K_4$ : 16; $K_{2,3}$ : 12	$C_n$ has $n$
Disconnected simple graph: at most $\binom{n-1}{2}$ edges	$n = 6$ : 10 edges	One more edge forces connectivity
$\chi(C_n) = 2$ or 3; $\chi(K_n) = n$ ; planar $\chi \le 4$	$C_5$ : 3	Bipartite iff no odd cycle

Remember: "A graph with $n - 1$ edges" is not enough to make a tree. It must also be connected or acyclic. The graph theory question guide shows how these bounds are asked.

The book's last-minute revision sheet gives the full mathematics table, including lattices, colouring bounds, perfect matchings and generating functions, each with when it applies and its trap. It is part of the GATE CSE 2027 book.

Linear algebra: eigenvalues, determinants and rank

Eigenvalue questions rarely need the characteristic polynomial. Two facts usually suffice: the eigenvalues sum to the trace and multiply to the determinant.

Worked example. A $2 \times 2$ matrix with trace 7 and determinant 10 has eigenvalues 2 and 5, since $\lambda^{2} - 7\lambda + 10 = 0$ . Then $A^{2}$ has 4 and 25, $A^{-1}$ has $\displaystyle \tfrac{1}{2}$ and $\displaystyle \tfrac{1}{5}$ , and $A + 3I$ has 5 and 8.

Formula	One-line example	Watch out for
$\det(kA) = k^{n} \det A$	$3 \times 3$ , $\det A = 4$ : $\det(2A) = 32$	Not $2 \times 4$
$\det(\operatorname{adj} A) = (\det A)^{n-1}$	$3 \times 3$ , $\det A = 4$ : 16	Power is $n - 1$
Nullity $= n - \operatorname{rank}(A)$	$4 \times 4$ of rank 3: nullity 1	Homogeneous systems have $n - \text{rank}$ independent solutions
Unique solution iff $\operatorname{rank}(A) = \operatorname{rank}([A : b]) = n$	Ranks 3, 3 and $n = 3$ : unique	Compare the augmented rank, not just $\det A = 0$

The linear algebra question guide works through these cases.

Probability: conditioning, expectation and distributions

Bayes' rule turns a forward probability into a backward one. The denominator is the total probability of the evidence:

P(A_i \mid B) = \frac{P(B \mid A_i)\,P(A_i)}{\sum_j P(B \mid A_j)\,P(A_j)}

Worked example. Machine A makes 60% of items with 2% defective, and machine B makes 40% with 5% defective. For a defective item, $\displaystyle P(A \mid D) = \dfrac{0.012}{0.012 + 0.020} = 0.375$ .

Variance is $\text{Var}(X) = E[X^{2}] - (E[X])^{2}$ . If $E[X] = 2$ and $E[X^{2}] = 7$ , then $\text{Var}(X) = 3$ and $\text{Var}(2X + 5) = 4 \times 3 = 12$ .

Distribution	Mean and variance	One-line example
$\text{Uniform}(a, b)$	$\displaystyle \dfrac{a + b}{2}$ , $\displaystyle \dfrac{(b - a)^{2}}{12}$	$(0, 6)$ : mean 3, variance 3
$\text{Exponential}(\lambda)$	$\displaystyle \dfrac{1}{\lambda}$ , $\displaystyle \dfrac{1}{\lambda^{2}}$	$\lambda = 0.5$ : mean 2, variance 4
$\text{Poisson}(\lambda t)$ : $\displaystyle P(k) = \dfrac{e^{-\lambda t} (\lambda t)^{k}}{k!}$	$\lambda t$ , $\lambda t$	3 per hour, 20 minutes: $P(0) = e^{-1} \approx 0.368$
$\text{Binomial}(n, p)$	$np$ , $np(1 - p)$	$n = 10$ , $p = 0.3$ : 3 and 2.1
$\text{Geometric}(p)$	$\displaystyle \dfrac{1}{p}$ , $\displaystyle \dfrac{1 - p}{p^{2}}$	$p = 0.25$ : 4 and 12
Normal	About 68, 95 and 99.7% within 1, 2 and 3 $\sigma$	$P(X > \mu) = 0.5$

Trap: "At least one six in two throws" is $\displaystyle \tfrac{11}{36}$ , while "exactly one six" is $\displaystyle \tfrac{10}{36}$ . More questions on this are in the probability question guide.

Calculus: limits, extrema and integrals

Formula	One-line example	Watch out for
$\displaystyle \left(1 + \dfrac{a}{n}\right)^{bn} \to e^{ab}$	$\displaystyle \left(1 + \dfrac{2}{n}\right)^{3n} \to e^{6}$	Multiply $a$ and $b$
$\displaystyle \dfrac{\sin x}{x} \to 1$ as $x \to 0$	$\displaystyle \dfrac{\sin 3x}{x} \to 3$	L'Hôpital only for $\displaystyle \tfrac{0}{0}$ or $\displaystyle \tfrac{\infty}{\infty}$
Absolute extrema on $[a, b]$ : compare critical points and both endpoints	$x^{3} - 12x$ on $[-3, 5]$ : max 65 at $x = 5$ , min $-16$ at $x = 2$	The interior maximum 16 at $x = -2$ is only local
$\int_0^{\infty} x^{n} e^{-x}\,dx = n!$	$n = 3$ : 6	Integer $n \ge 0$
Odd $f$ : $\int_{-a}^{a} f(x)\,dx = 0$	$\int_{-2}^{2} x^{3} \cos x\,dx = 0$	Check the symmetry of the limits

The engineering mathematics important topics guide ranks which of these areas past papers have tested most.

More formula sheets: all of GATE CSE · Computer Networks · COA · Operating Systems

Quick revision

Onto from $m$ to $n$ : $\sum_{k} (-1)^{k} \binom{n}{k} (n - k)^{m}$ ; derangements 1, 0, 1, 2, 9, 44, 265.
Stars and bars: $\binom{n + k - 1}{k - 1}$ .
Reflexive and symmetric relations: $2^{n(n-1)/2}$ ; antisymmetric: $2^{n} 3^{n(n-1)/2}$ .
$v - e + f = 2$ ; $e \le 3v - 6$ ; bipartite $e \le 2v - 4$ ; $K_n$ has $n^{n-2}$ spanning trees.
Eigenvalues: sum $=$ trace, product $= \det$ ; $\det(kA) = k^{n} \det A$ .
Bayes needs the total-probability denominator; $\text{Var}(X - Y) = \text{Var}\,X + \text{Var}\,Y$ for independent variables.
Exponential mean $1/\lambda$ ; Poisson mean and variance $\lambda t$ , rescaled to the interval.
Absolute extrema on $[a, b]$ : check both endpoints.

Frequently asked questions

How many onto functions are there from an m-set to an n-set?

Use inclusion and exclusion: the count is $\sum_{k=0}^{n} (-1)^k \binom{n}{k} (n-k)^m$ . Start with all $n^m$ functions, remove those that miss at least one element of the codomain, and add back the double removals. From a 4-set to a 2-set this gives $16 - 2 = 14$ . From a 6-set to a 3-set it gives 540, not $3^6$ .

How many reflexive and symmetric relations are there on a set of n elements?

There are $2^{n(n-1)/2}$ . Reflexivity fixes all n diagonal pairs, so only the off-diagonal pairs are free. Symmetry ties each pair (a, b) to (b, a), which leaves $n(n-1)/2$ independent choices. Writing $2^{n(n+1)/2}$ is the classic mistake, because that is the count of symmetric relations without the reflexive condition.

What are the main eigenvalue properties asked in GATE CSE?

The sum of the eigenvalues equals the trace and their product equals the determinant. If A has eigenvalue lambda, then $A^k$ has $\lambda^k$ , the inverse has $1/\lambda$ and A plus cI has lambda plus c. A triangular matrix has its diagonal entries as eigenvalues. A matrix is invertible exactly when no eigenvalue is zero. Eigenvalues of A plus B are not sums.

What are the mean and variance of the exponential and Poisson distributions?

An exponential distribution with rate lambda has mean $1/\lambda$ and variance $1/\lambda^2$ , and it is memoryless. A Poisson count over an interval of length t has mean and variance both equal to lambda times t. Always rescale the rate to the interval the question asks about, for example a per-hour rate for a 20-minute window.

How many marks does Engineering Mathematics carry in GATE CSE?

The official pattern gives Engineering Mathematics about 13 of the 100 marks, alongside 15 marks of General Aptitude and about 72 marks of core subjects. Discrete mathematics, probability, linear algebra and calculus are all in the section. Confirm the current pattern and syllabus at gate2027.iitm.ac.in before you plan your revision.

Sources

Dates, fees and the syllabus are set by the GATE 2027 organising institute and can change. Always confirm at gate2027.iitm.ac.in.