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

No comments:

Post a Comment