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:
“As Jerome expanded, its chances for the title, “the toughest little town in the West,” increased and when it was incorporated in 1899 the citizens were able to support the claim by pointing to the number of thick stone shutters on the fronts of all saloons, gambling halls, and other places of business for protection against gunfire.”
—Administration in the State of Ariz, U.S. public relief program (1935-1943)
“The human spirit is itself the most wonderful fairy tale that can possibly be. What a magnificent world lies enclosed within our bosoms! No solar orbit hems it in, the inexhaustible wealth of the total visible creation is outweighed by its riches!”
—E.T.A.W. (Ernst Theodor Amadeus Wilhelm)