## Friday, March 15, 2013

### Enumerating labeled binary relations

Labeled binary relations on a set of size $n$ can be enumerated using the following counting sequences:
• All relations: $2^{n^2}$
• Commutative relations: $2^{n^{\underline 2}}$
• Endofunctions: $n^n$
• Permutations: $n!$
• Equivalence relations: $B_n$
• Weak orders: A000670