関係の数

$S$ に定まる(2項)関係は $S\times S$ の部分集合であるので、
行に $n$ 個の元を並べ、さらに列に $n$ 個の元を並べて、
各行列の成分が関係が成り立っているか成り立っていないかの2種類あるので、
合計で $2^{(n^2)}$ 個の関係が考えられる。