Number of preorder relations on a set related to the open problem about preorder relations

118 Views Asked by At

Consider a set $A=\left\{1,2,3\right\}$,I want to count the number of preorder relations on this set, so there is two cases two consider,either the relation is symmetric or it is not, if the relation is symmetric then it's also an equivalence relation and the number of equivalence relations on this set is $B_3$, where $B_k$ is the kth Bell number, but we also have to count the preorder relation which are not symmetric :

$$\left\{\left(1,1\right),\left(2,2\right),\left(3,3\right),\left(1,2\right)\right\}$$ $$\left\{\left(1,1\right),\left(2,2\right),\left(3,3\right),\left(1,3\right)\right\}$$

$$\left\{\left(1,1\right),\left(2,2\right),\left(3,3\right),\left(3,1\right)\right\}$$

these are some of examples of a preorder relations on the set $A$ that are not symmetric, here I think there should be a strategy for counting them, first we should note that since the preorder relation is reflexive, hence the ordered pairs $\left(1,1\right),\left(2,2\right),\left(3,3\right)$ appears in all of the relations, but if we want to make a preorder relation which is not symmetric hence we first should choose one of the elements in $A$,there are ${{3}\choose{1}}$ of them and then for each one of the chosen elements there exist $2$ ways for which of the remaining elements in the set $A$ the chosen element is going to be paired with, for example if we choose $1$ then there are $2$ ways to choose an element from the remaining ones in $A$ ( the remaining elements in $A$ are $2$ and $3$),that $1$ can be paired with, so now we can make two relations which are not symmetric : $$\left\{\left(1,1\right),\left(2,2\right),\left(3,3\right),\left(1,2\right)\right\}$$ and $$\left\{\left(1,1\right),\left(2,2\right),\left(3,3\right),\left(1,3\right)\right\}$$

The number of all these cases is :$$\color{blue}{ {{3}\choose{1}}\cdot2}\tag{I}$$

In all of these relations we just add one pair to the fixed set, for example in $\left\{\left(1,1\right),\left(2,2\right),\left(3,3\right),\left(1,3\right)\right\}$ we just add one pair $\left(1,3\right)$ to the set, but what about adding two pairs? Well I used the similar strategy and concluded that there exist $$\color{red}{ {{3}\choose{1}}{{2}\choose{1}}\cdot2\cdot1+{{3}\choose{1}}\cdot2}\tag{II}$$ of them.

For example assume we have the fixed set $\left\{\left(1,1\right),\left(2,2\right),\left(3,3\right)\right\}$ then we should decide which pair should be contained in this set, from above there exist $${{3}\choose{1}}\cdot2$$ relations of this from,but now we want to add another pair, we already have chosen $1$ element from the set, so there are two elements left in the set, the same strategy can be applied so there is ${{2}\choose{1}}\cdot1$ ways to make the second pair and since each time we removed $6$ we add $6$.

For example if we choose $1$ and let it to be paired with $2$ then we have $\left(1,2\right)$ as an ordered pair,but we also going to make another ordered pair with elements $2$ and $3$, if we choose $3$ then it can be just paired with $2$ (since if we pair $3$ with $1$ then we have a symmetric relation which already has been counted by $B_3$) , or if we choose $2$ then there is two elements that $2$ can be paired with, we actually removed the condition that $2$ is paired with $1$,and this is just one of the $${{3}\choose{1}}\cdot2$$ preorder relations , so we need to add this relation, so the number of preorder relations in this way is $$ {{3}\choose{1}}{{2}\choose{1}}\cdot2\cdot1+{{3}\choose{1}}\cdot2$$ which is the formula in $({\text{II}})$

Summing $({\text{I}})$ and $({\text{II}})$ and considering that a preorder relation can also be an equivalence relation implies the number of preorder relations on $A$ is: $$\color{blue}{{{3}\choose{1}}\cdot2}+ \color{red}{{{3}\choose{1}}{{2}\choose{1}}\cdot2\cdot1+{{3}\choose{1}}\cdot2} +B_3$$$$=\color{blue}{6}+\color{red}{18}+5=29$$

as Wikipedia says it should be $29$

As I know there does not exist any explicit formula for counting the number of preorder relations on a set with arbitrary $n$ elements and it's one of the open problems, I just want to know does my approach has any closed form or it does not.

Also it would be highly appreciated if someone explain what Wikipedia exactly has done. (please explain how can I find the number of preorder relations for $n$ arbitrary)