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:
“Cultivated labor drives out brute labor. An infinite number of shrewd men, in infinite years, have arrived at certain best and shortest ways of doing, and this accumulated skill in arts, cultures, harvestings, curings, manufactures, navigations, exchanges, constitutes the worth of our world to-day.”
—Ralph Waldo Emerson (1803–1882)
“The word infant derives from Latin words meaning “not yet speaking.” It emphasizes what the child cannot do and reflects the baby’s total dependence on adults. The word toddler, however, demonstrates our change in perspective, for it focuses on the child’s increased mobility and burgeoning independence.”
—Lawrence Kutner (20th century)