Let $X$ be a finite set with $n$ elements. How many functions are there from $X$ to $X$ ? How many relations are there on $X$ ?

Show that the number of relations $R$ on $X$ such that, for each $y \in X$, there exists at least one $x \in X$ with $x R y$, is $\left(2^{n}-1\right)^{n}$.

Using the inclusion-exclusion principle or otherwise, deduce that the number of such relations $R$ for which, in addition, for each $x \in X$, there exists at least one $y \in X$ with $x R y$, is

$$\sum_{k=0}^{n}(-1)^{k}\left(\begin{array}{l} n \\ k \end{array}\right)\left(2^{n-k}-1\right)^{n}$$