Counting Relations

Why this section exists. Boards ask you to prove properties; JEE Main asks you to count — how many relations, how many functions of each type, how many equivalence relations. Nearly every JEE question from this chapter is a counting question, and they all reduce to a handful of formulas derived below.

The master count: all relations

A relation on a set $A$ with $n$ elements is any subset of $A \times A$, which has $n^2$ ordered pairs. Each pair is independently in or out:

$$\text{Number of relations on an } n\text{-element set} = 2^{n^2}$$

For $n = 3$: $2^9 = 512$ relations.

Reflexive relations

Reflexivity forces the $n$ diagonal pairs $(a, a)$ in; the remaining $n^2 - n$ off-diagonal pairs stay free:

$$\text{Reflexive relations} = 2^{n^2 - n}$$

For $n = 3$: $2^6 = 64$.

Symmetric relations

Symmetry ties each pair $(a, b)$ to its mirror $(b, a)$ — they enter or leave together. The free choices are the $n$ diagonal pairs plus the $\frac{n^2 - n}{2}$ mirror-couples, a total of $\frac{n(n+1)}{2}$ independent decisions:

$$\text{Symmetric relations} = 2^{\frac{n(n+1)}{2}}$$

For $n = 3$: $2^6 = 64$ (equal to the reflexive count only by coincidence at $n = 3$).

Reflexive AND symmetric

Diagonal forced in, mirror-couples free: $\frac{n(n-1)}{2}$ decisions,

$$\text{Reflexive and symmetric relations} = 2^{\frac{n(n-1)}{2}}$$

For $n = 3$: $2^3 = 8$.

Equivalence relations = partitions (Bell numbers)

An equivalence relation is a partition of the set, so counting equivalence relations means counting partitions. These counts are the Bell numbers:

For $\{1, 2, 3\}$ the five are: $\{1\}\{2\}\{3\}$ (the identity relation), three of shape $\{1,2\}\{3\}$ (choose which pair merges), and $\{1,2,3\}$ (the universal relation). There is no closed formula — for JEE, memorise $1, 2, 5, 15$.

Warning — transitive relations have no formula either. Questions about "how many transitive relations" are always constrained ones (containing given pairs), solved by hand as in the Board section. Any option pattern suggesting a neat formula for transitive relations is a trap.

Counting Functions

All functions

A function from an $m$-element set $A$ to an $n$-element set $B$ makes a free choice of image for each of the $m$ inputs:

$$\text{Number of functions } A \to B = n^m$$

(Memory aid: $(\text{co-domain size})^{\text{domain size}}$ — the exponent counts the decisions.)

One-one functions

Distinct inputs need distinct images: the first input has $n$ choices, the next $n - 1$, and so on —

$$\text{One-one functions } A \to B = {}^{n}P_{m} = \frac{n!}{(n - m)!} \quad (m \leq n); \qquad 0 \text{ if } m > n$$

The zero case is a favourite trap: there is no one-one function from a bigger set into a smaller one (pigeonhole).

Onto functions (inclusion–exclusion)

$$\text{Onto functions } A \to B = \sum_{k=0}^{n} (-1)^k \binom{n}{k} (n - k)^m = n^m - \binom{n}{1}(n-1)^m + \binom{n}{2}(n-2)^m - \cdots$$

Subtract the functions missing at least one target, add back the double-subtracted, and so on. Special cases worth memorising:

$$\text{onto } A \to B \text{ with } \vert B \vert = 2: \quad 2^m - 2$$ $$\text{onto with } m = n: \quad n! \qquad \text{onto with } m < n: \quad 0$$

Worked count. Onto functions from a 4-element set to a 3-element set: $$3^4 - \binom{3}{1}2^4 + \binom{3}{2}1^4 = 81 - 48 + 3 = 36$$

Bijections

$$\text{Bijections of an } n\text{-element set} = n!$$

and these are simultaneously the one-one self-maps and the onto self-maps (the finite-set collapse).

The summary card

Common mistakes to avoid

Mistake 1 — swapping the exponent: functions $m \to n$ number $n^m$, not $m^n$. The domain size is the exponent.

Mistake 2 — using $^nP_m$ when $m > n$: the count is 0, not undefined or negative.

Mistake 3 — counting onto with a product: onto needs inclusion-exclusion; simple products overcount.

Mistake 4 — "symmetric" halving done wrong: the diagonal pairs are their own mirrors — they contribute $n$ free choices, not $\frac{n}{2}$.

JEE-Pattern Worked Examples

Example 1 — All relations

How many relations can be defined on the set $A = \{a, b, c\}$?

Step 1 — count the pairs: $\vert A \times A \vert = 3^2 = 9$.

Step 2 — each subset of $A \times A$ is a relation: $2^9 = 512$.

Answer: $512$.

Example 2 — Reflexive, symmetric, and both

For $A = \{1, 2, 3\}$, count the relations that are (i) reflexive, (ii) symmetric, (iii) both.

Step 1 — (i): the 3 diagonal pairs are forced; the $9 - 3 = 6$ others are free: $2^6 = 64$.

Step 2 — (ii): free choices are the 3 diagonal pairs and the 3 mirror-couples $\{(1,2),(2,1)\}, \{(1,3),(3,1)\}, \{(2,3),(3,2)\}$: $\ 2^{3+3} = 64$.

Step 3 — (iii): diagonal forced, 3 mirror-couples free: $2^3 = 8$.

Answer: (i) $64$, (ii) $64$, (iii) $8$.

Example 3 — All equivalence relations on a 3-set

Count and list the equivalence relations on $\{1, 2, 3\}$.

Step 1 — count partitions instead: each equivalence relation is a partition.

Step 2 — enumerate by shape: all separate: $\{1\}\{2\}\{3\}$ — 1 way. One pair together: choose the pair in $\binom{3}{2} = 3$ ways. All together: $\{1,2,3\}$ — 1 way.

Answer: $1 + 3 + 1 = 5$ equivalence relations (the Bell number $B_3$). The smallest is the identity relation, the largest the universal relation.

Example 4 — Functions of each kind, $3 \to 5$

Let $\vert A \vert = 3$ and $\vert B \vert = 5$. Count (i) all functions $A \to B$, (ii) one-one functions $A \to B$, (iii) onto functions $A \to B$.

Step 1 — (i): $5^3 = 125$.

Step 2 — (ii): $^5P_3 = 5 \times 4 \times 3 = 60$.

Step 3 — (iii): a 3-element domain cannot cover a 5-element co-domain: $0$.

Answer: $125$, $\ 60$, $\ 0$ — the three standard counts side by side.

Example 5 — Onto by inclusion-exclusion

Find the number of onto functions from $A = \{1, 2, 3, 4\}$ to $B = \{a, b, c\}$.

Step 1 — start from all functions and subtract those missing a target: $$3^4 - \binom{3}{1} \cdot 2^4 + \binom{3}{2} \cdot 1^4$$

Step 2 — compute: $81 - 3(16) + 3(1) = 81 - 48 + 3 = 36$.

Answer: $36$. (Cross-check by direct construction: one target receives two inputs, the others one each — $\binom{4}{2} \times 3! = 6 \times 6 = 36$ ✓.)

Example 6 — Onto a two-element set

Show that the number of onto functions from an $m$-element set onto $\{0, 1\}$ is $2^m - 2$.

Step 1 — all functions: $2^m$.

Step 2 — remove the non-onto ones: exactly two functions miss a target — the constant function 0 and the constant function 1.

Answer: $2^m - 2$. For $m = 5$: $\ 32 - 2 = 30$.

Example 7 — Permutations with a forbidden value

How many one-one functions $f : \{1, 2, 3\} \to \{1, 2, 3\}$ satisfy $f(1) \neq 1$?

Step 1 — all one-one self-maps: $3! = 6$.

Step 2 — subtract those with $f(1) = 1$: the other two elements permute freely: $2! = 2$.

Answer: $6 - 2 = 4$. (Complementary counting — subtract the violators — is the standard JEE move for restricted permutations.)

Example 8 — Building a transitive closure count

On $A = \{1, 2, 3\}$, what is the smallest relation containing $(1, 2)$ and $(2, 3)$ that is both reflexive and transitive, and how many ordered pairs does it have?

Step 1 — reflexivity contributes $(1,1), (2,2), (3,3)$.

Step 2 — transitivity applied to $(1,2)$ and $(2,3)$ forces $(1,3)$, and no further chains produce anything new.

Step 3 — assemble: $R = \{(1,1), (2,2), (3,3), (1,2), (2,3), (1,3)\}$.

Answer: 6 ordered pairs. (This "smallest relation with given properties" construction is the engine behind all the counting-with-constraints questions of the Board section.)