Binary Relation - The Number of Binary Relations

The Number of Binary Relations

The number of distinct binary relations on an n-element set is 2n2 (sequence A002416 in OEIS):

Number of n-element binary relations of different types
n all transitive reflexive preorder partial order total preorder total order equivalence relation
0 1 1 1 1 1 1 1 1
1 2 2 1 1 1 1 1 1
2 16 13 4 4 3 3 2 2
3 512 171 64 29 19 13 6 5
4 65536 3994 4096 355 219 75 24 15
OEIS A002416 A006905 A053763 A000798 A001035 A000670 A000142 A000110

Notes:

  • The number of irreflexive relations is the same as that of reflexive relations.
  • The number of strict partial orders (irreflexive transitive relations) is the same as that of partial orders.
  • The number of strict weak orders is the same as that of total preorders.
  • The total orders are the partial orders that are also total preorders. The number of preorders that are neither a partial order nor a total preorder is, therefore, the number of preorders, minus the number of partial orders, minus the number of total preorders, plus the number of total orders: 0, 0, 0, 3, and 85, respectively.
  • the number of equivalence relations is the number of partitions, which is the Bell number.

The binary relations can be grouped into pairs (relation, complement), except that for n = 0 the relation is its own complement. The non-symmetric ones can be grouped into quadruples (relation, complement, inverse, inverse complement).

Read more about this topic:  Binary Relation

Famous quotes containing the words number and/or relations:

    After mature deliberation of counsel, the good Queen to establish a rule and imitable example unto all posterity, for the moderation and required modesty in a lawful marriage, ordained the number of six times a day as a lawful, necessary and competent limit.
    Michel de Montaigne (1533–1592)

    The principle that human nature, in its psychological aspects, is nothing more than a product of history and given social relations removes all barriers to coercion and manipulation by the powerful.
    Noam Chomsky (b. 1928)