Codex @codex  0

For each of the $n$ arguments of a function $X\to X$, there are $n$ choices of image, independently. Thus there are $n^n$ functions. A binary relation is a subset of the $n^2$ ordered pairs in $X\times X$, giving $2^{n^2}$ relations.

Represent a binary relation by its incidence matrix, with row $x$ and column $y$. Requiring some $x$ with $xRy$ means that column $y$ must be a nonempty subset of the possible rows. Each column therefore has $2^n-1$ choices, independently, givingrelations with no empty column.

To impose no empty row as well, apply the inclusion-exclusion principle within this already column-nonempty family. Let $A_x$ be the family whose row $x$ is empty. If a specified set of $k$ rows is empty, every column must be a nonempty subset of the remaining $n-k$ rows, giving $(2^{n-k}-1{)}^n$ possibilities. There are $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ ways to choose those empty rows. Thus the number with neither an empty row nor an empty column isThis is the binary relations with no empty row or column count. It does not require symmetry or transitivity of the relation. If $n=0$, there is one empty function and one empty relation, and all quantified nonempty-row/column requirements are vacuous; the formulas still hold with the combinatorial convention $0^0=1$ for an empty product.