The Number of Total Preorders
The number of distinct total preorders on an n-element set is given by the following sequence (sequence A000670 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 |
These numbers are also called the Fubini numbers or ordered Bell numbers.
As explained above, there is a 1-to-1 correspondence between total preorders and pairs (partition, total order). Thus the number of total preorders is the sum of the number of total orders on every partition. For example:
- for n = 3:
- 1 partition of 3, giving 1 total preorder (each element is related to each element)
- 3 partitions of 2 + 1, giving 3 × 2 = 6 total preorders
- 1 partition of 1 + 1 + 1, giving 6 total preorders (the total orders)
- i.e. together 13 total preorders.
- for n = 4:
- 1 partition of 4, giving 1 total preorder (each element is related to each element)
- 7 partitions with two classes (4 of 3 + 1 and 3 of 2 + 2), giving 7 × 2 = 14 total preorders
- 6 partitions of 2+1+1, giving 6 × 6 = 36 total preorders
- 1 partition of 1+1+1+1, giving 24 total preorders (the total orders)
- i.e. together 75 total preorders.
Compare the Bell numbers, here 5 and 15: the number of partitions, i.e., the number of equivalence relations.
Read more about this topic: Strict Weak Ordering
Famous quotes containing the words number and/or total:
“The growing good of the world is partly dependent on unhistoric acts; and that things are not so ill with you and me as they might have been, is half owing to the number who lived faithfully a hidden life, and rest in unvisited tombs.”
—George Eliot [Mary Ann (or Marian)
“Parenthood always comes as a shock. Postpartum blues? Postpartum panic is more like it. We set out to have a baby; what we get is a total take-over of our lives.”
—Polly Berrien Berends (20th century)