Sets & relations formulas

For a finite set A; each element is either in or out of a subset.

Finite sets. A relation from A to B is any subset of A × B, so there are $2^{|A||B|}$ of them.

Finite sets; this is the basis of Venn-diagram counting.

Finite sets; add singles, subtract pairs, add the triple.

Finite sets.

Each of the $n^2$ ordered pairs is in or out.

The n diagonal pairs are forced; the other $n(n-1)$ are free. Irreflexive relations have the same count.

For $n\ge 1$, where no relation is both reflexive and irreflexive: subtract the reflexive and the irreflexive relations from all relations.

Choose freely for each of the $n$ diagonal pairs and each of the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ unordered pairs $\{a,b\}$ with $a\ne b$.

Diagonal pairs are free ($2^n$); each unordered pair $\{a,b\}$ with $a\ne b$ has 3 choices: none, $(a,b)$ only, $(b,a)$ only.

Diagonal pairs are excluded; each unordered pair has the same 3 choices. Reflexive and antisymmetric relations have the same count (diagonal forced in instead of out).

Diagonal forced to 1; each unordered pair with $a\ne b$ is in or out. Irreflexive and symmetric relations have the same count.

Such a relation is a subset of the identity relation, so only the diagonal pairs are free.

$B_n$ (Bell number) counts partitions of an n-element set; $S(n,k)$ (Stirling number of the second kind) counts partitions into exactly $k$ non-empty blocks.

With $S(n,1)=S(n,n)=1$ for $n\ge 1$, and $S(n,n-1)=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$.

For $n\ge 2$: the number of equivalence relations on n elements with exactly two classes.

Each element of $A$ independently picks an image.

$m=|A|$, $n=|B|$, $m\le n$; when $m>n$ there are none (the product form gives 0).

$|A|=|B|=n$; this is also the number of permutations of an n-set.

$m=|A|$, $n=|B|$; zero when $m<n$.

$m=|A|$, $n=|B|$; each element of $A$ maps to one of the $n$ elements or is left undefined.

Poset $(\mathcal{P}(A),\subseteq )$ with $|A|=n$: $S$ is covered by $S\cup \{x\}$ for each $x\notin S$.

Poset of positive divisors under 'divides' ($p_i$ distinct primes); join is lcm and meet is gcd.

$N=p_1^{a_1}\cdots p_k^{a_k}$; $d$ is covered by $d{p}_i$ whenever $d{p}_i$ divides $N$. For $N=12=2^2\cdot 3$: $2\cdot 2+1\cdot 3=7$.