Counting non-isomorphic relations On a set $X$ of $n$ elements, how many non-isomorphic relations are there? The number of relations on a set of $n$ elements is $|\mathcal{P}(X \times X)|=2^{n^2}$, but is there any way to give a general formula for how many of these are non-isomorphic? I am interested in this question for an application to modal logic. Thanks!
In particular, I consider two relations $R$ and $S$ to be isomorphic if there exists a bijection $\varphi: X \rightarrow X$ such that $\varphi(x) R \varphi(y) \Leftrightarrow x S y$

A relation on $X$ can be modeled as a graph on the vertex set $X$. Since it is a hard problem to determine the number of isomorphism types of graphs, I guess that your answer does not have a simple answer, and that there is no simple formula for the number of non-isomorphic relations.
ADDITION
This is sequence 595 in the online encyclopedia of integer sequences.
I'm a bit surprised that there is indeed a formula given:
$$a(n) = \sum_{1s_1+2s_2+\ldots =n} \frac{\operatorname{fixA}[s_1, s_2, ...]}{1^{s_1}s_1!\cdot 2^{s_2}s_2!\cdot\ldots}$$
where
$$\operatorname{fixA}[s_1, s_2, \ldots] = 2^{\sum_{i, j\geq 1} \gcd(i, j)s_i s_j}$$
I guess the formula arises as an application of the Cauchy-Frobenius lemma.
