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] elderly and timid single gentleman in Paris ... never drove down the Champs Elysees without expecting an accident, and commonly witnessing one; or found himself in the neighborhood of an official without calculating the chances of a bomb. So long as the rates of progress held good, these bombs would double in force and number every ten years.”
—Henry Brooks Adams (1838–1918)
“... one of the blind spots of most Negroes is their failure to realize that small overtures from whites have a large significance ... I now realize that this feeling inevitably takes possession of one in the bitter struggle for equality. Indeed, I share it. Yet I wonder how we can expect total acceptance to step full grown from the womb of prejudice, with no embryo or infancy or childhood stages.”
—Sarah Patton Boyle, U.S. civil rights activist and author. The Desegregated Heart, part 1, ch. 10 (1962)