Number of Relations

Number of Relations

## Formula

If:

$$n(A)=m,\qquad n(B)=n$$

then:

$$n(A\times B)=mn$$

Therefore, the number of relations from $A$ to $B$ is:

$$2^{mn}$$

The number of non-empty relations is:

$$2^{mn}-1$$

## Conditions / Special Cases

For relations on $A$, where:

$$n(A)=n$$

the number of relations is:

$$2^{n^2}$$

The number of non-empty relations on $A$ is:

$$2^{n^2}-1$$

## Usage

- Used in counting problems involving relations between finite sets.