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:
“This nightmare occupied some ten pages of manuscript and wound off with a sermon so destructive of all hope to non-Presbyterians that it took the first prize. This composition was considered to be the very finest effort of the evening.... It may be remarked, in passing, that the number of compositions in which the word “beauteous” was over-fondled, and human experience referred to as “life’s page,” was up to the usual average.”
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)
“The land is the appointed remedy for whatever is false and fantastic in our culture. The continent we inhabit is to be physic and food for our mind, as well as our body. The land, with its tranquilizing, sanative influences, is to repair the errors of a scholastic and traditional education, and bring us to just relations with men and things.”
—Ralph Waldo Emerson (1803–1882)