= Solution
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, giving
$$
\boxed{(2^n-1)^n}
$$
relations 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 $\binom nk$ ways to choose those empty rows. Thus the number with neither an empty row nor an empty column is
$$
\boxed{\sum_{k=0}^n(-1)^k\binom nk(2^{n-k}-1)^n}.
$$
This 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.
Back to article page
