Number of Quasi reflexive and coreflexive relations on a set with $n$ elements Given a binary relation $R$ over a set $A$ with $n$ elements,then :
$R$ is coreflexive if:
$$\forall a,b \in A:aRb \implies a=b$$
$R$ is Quasi-reflexive if:
$$\forall a,b \in A:aRb \implies aRa \;\;\;\text{and}\;\;\; bRb$$

*

*How many coreflexive and Quasi-reflexive relations exist on $A$?


Define $$A:=\left\{a_i \mid i \in I\right\}\tag{$\left|I\right|=n,n \in \mathbb N$}$$
Based on the definition  $(a_i,a_j)\in R$ if $a_i=a_j$ .
On the other hand for each such $i$,either $(a_i,a_i)\in R$ or $(a_i,a_i) ∉ R$,so
Easily follows the number of coreflexive relation on $A$ is $2^n$.
For the other question let $i<j$.
If $(a_i,a_j)\in R$,then so are $(a_i,a_i)$ and $(a_j,a_j)$,also for each such $i$ either $(a_j,a_i)\in R$ or $(a_j,a_i)∉ R$,if $(a_i,a_j)∉ R$,then the only uncounted case appears when  $(a_i,a_j)\in R$,from here it's seen that for all such $i$ there are 3 distinct Quasi-reflexive relations on $A$
Now we are left with the number of such $i$ which is $\sum_{k=1}^{n-1}k=\frac{n\left(n-1\right)}{2}$
So the number of Quasi-reflexive relations with $i \ne j$ is $$3^{\large\frac{n\left(n-1\right)}{2}}\tag{I}$$
Also for equal indexes either $(a_i,a_i) \in R$ or $(a_i,a_i) ∉ R$,the number of such $i$ is $n$,follows the number of such Quasi-relations is $$2^n\tag{II}$$
Summing $(\text{I})$ and $(\text{II})$ gives thew total number of Quasi-reflexive relations on $A$ for $n\ge2$.
But I'm not sure if the results are true,can someone check them?
 A: Let $|A|=n$.
A coreflexive relation defines a subset $S$ of the vertices:
$S = \{a \in A \mid aRa\}$.
Vice versa, every subset $S \subseteq A$ defines a coreflexive relation: $R=\{ (a,b) \mid a\in S, b \in S\}$.
Therefore, the number of coreflexive relations is the number of subsets of $A$, i.e., $2^{|A|} = 2^n$.
Let $R$ be a quasi-reflexive relation. Define the set
$S_R= \{ a\in A \mid \exists b\in A \setminus \{a\} : aRb \text{ or } bRa \}$.
The relation $R$ restricted to the set $S_R$ is a labelled directed graph without isolated vertices such that every vertex is self-looped. Labelled means that the vertices are labelled. Without the self-loops, it corresponds to a labelled directed simple graph without isolated vertices.
The relation $R$ resticted to the set $A \setminus S_R$ is a graph with only self-loops.
Any two such graphs define a quasi-reflexive relation.
This means that the number $QR(A)$ of quasi-reflexive relations on the set $A$ is equal to
$$QR(A) = \sum_{S \subseteq A} N(S) * M(S),$$
where $N(S)$ is the number of labelled simple directed graphs on $S$ without isolated vertices; $M(S)$ is the number of graphs with only self-loops on $A \setminus S$.
The number $M(S)$ is just choosing a subset of $A \setminus S$, so that is equal to $2^{|A \setminus S|}$.
The number $N(S)$ is equal to $N(T)$ for equally sized sets $S$ and $T$. Therefore, let $D_i$ the number $N(S)$ for some subset $S$ of size $i$.
Since there are $\binom{|A|}{i}$ subsets of $A$ of size $i$, we have that
$$QR(A) = \sum_{i=0}^{|A|} \binom{|A|}{i} D_i * 2^{|A|-i}.$$
It is easy to see that $D_0=1$ and $D_1=1$.
In general, it has been answered in this stack exchange answer that
$$D_i = \sum_{p=0}^i \binom{i}{p} (-1)^p 4^{\binom{i-p}{2}},$$
where $\binom{a}{2}=0$ if $a < 2$.
Therefore,
$$QR(A) = \sum_{i=0}^{|A|} \binom{|A|}{i} 2^{|A|-i} \left(\sum_{p=0}^i \binom{i}{p} (-1)^p 4^{\binom{i-p}{2}}\right).$$
So if $|A|=n$, we have that
$$QR_n = \sum_{i=0}^{n} \binom{n}{i} 2^{n-i}\left(\sum_{p=0}^i \binom{i}{p} (-1)^p 4^{\binom{i-p}{2}}\right).$$
I am sure this can be simplified further. For small numbers (starting from $n=0$) gives the sequence $1, 2, 7, 80, 4381, 1069742, \ldots$.
A: Given any set $X$, there is a one-to-one correspondence between subsets of $X$ and coreflexive relations on $X$:
If $Y \subseteq X$, then $\{(y,y) \mid y \in Y\}$ is a coreflexive relation on $X$.
Conversely, if $R$ is a coreflexive relation on $X$, then $\{x \in X \mid (x,x) \in R\}$ is a subset of $X$.
In particular, if $X$ is a set with exactly $n$ elements, then the number of coreflexive relations on $X$ is $2^n$.
A quasi-reflexive relation on $X$ is equivalently a reflexive relation on some subset of $X$. If $Y$ is a subset of $X$ with exactly $k$ elements, then the number of reflexive relations on $Y$ is $2^{k^2-k}$.
The total number of quasi-reflexive relations on $X$ is thus given by the following formula:
$$\sum_{k=0}^{n} {n \choose k} 2^{k^2-k}$$.
