The Enumeration of Binary Relations

Binary relations between finite sets N and X, families of subsets, and lattice homomorphisms from P(N) to P(X) are three faces of the same object.

This self-contained monograph, merging and substantially expanding the author's ICTP preprint IC/97/180 (1997) and a 2026 companion note, enumerates every combinatorial type (arbitrary, injective, surjective, on either side), both raw and up to the actions of the symmetric groups S_N, S_X, and S_N x S_X, via the Cauchy-Frobenius-Burnside lemma.

The generating functions of all counts are then determined, revealing e^{z+w+zw}, Bell numbers, Euler's partition product, and the quasi-polynomiality of the hardest, two-sided column of the table.

All prerequisite tools -- elementary counting, group actions, Stirling and Bell numbers, formal power series, and Mobius inversion on the Boolean lattice -- are developed from first principles, making the book accessible after a first course in algebra and combinatorics.

A documented correction to Theorem B of the 1997 preprint is included; all formulas have been verified by symbolic computation and brute-force enumeration.