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:
“In this world, which is so plainly the antechamber of another, there are no happy men. The true division of humanity is between those who live in light and those who live in darkness. Our aim must be to diminish the number of the latter and increase the number of the former. That is why we demand education and knowledge.”
—Victor Hugo (1802–1885)
“Throughout human history, the apostles of purity, those who have claimed to possess a total explanation, have wrought havoc among mere mixed-up human beings.”
—Salman Rushdie (b. 1948)