Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose I have a set $A$ such that $A$ = $\{1, 2, 3, 4, 5\}$ (or $A$ = $\{1, 2, 3, 4\}$ or $A$ = $\{1, 2, 3\}$ or any other finite small set). How can I find the total number of partial order relations on such a set?

I'm trying to wrap my head around the concept, but I'm still not quite getting it. (My instructor talked about a Hasse diagram, but am I always to use those/would it make it way easier?) If anyone could explain this concept a bit more clearly than my notes, that would be very good!

share|cite|improve this question
If I understand correctly, the number for your 5-element set is 4231, which suggests it's not so easy to calculate even for fairly small sets. – Gerry Myerson Nov 21 '12 at 5:08
My bad, I just selected finite small sets off the top of my head. I suppose we could just then consider the 3 and 4 element sets? (Since I know the 0, 1, and 2 element sets are trivial.) – user41419 Nov 21 '12 at 5:10
up vote 3 down vote accepted

Counting the possible partial orders on $\{1,\dots,n\}$ is a very hard task. For $n\le 4$ you can do it by hand, but it’s pretty tedious, and I don’t know of any really nice way to approach the task. For instance, for $n=3$ you get the following five Hasse diagrams:

   o              o   o               o                 o  
   |               \ /               / \                |  
   o                o               o   o               o   o         o  o  o  
  (a)              (b)               (c)                 (d)            (e)

The numbers $1,2$, and $3$ can be entered into (a) in $3!=6$ distinguishable ways. In (b) there are $3$ ways to choose the minimum element, and that’s it: the two diagrams below represent the same partial order.

         2   3              3   2  
          \ /                \ /  
           1                  1

Similarly, there are $3$ ways to choose the top element in (c), and the order of the other two elements in the picture doesn’t affect the partial order represented by the picture. In diagram (d) there are $3$ ways to choose the element that’s not comparable to the other two elements, and there are then $2$ ways to order those two elements, so there are $3\cdot2=6$ partial orders on $\{1,2,3\}$ represented by (d). Finally, (e) represents only one partial order, the relation of equality on $\{1,2,3\}$. That’s a total of $6+3+3+6+1=19$ partial orders on the set $\{1,2,3\}$.

There are $16$ unlabelled Hasse diagrams on four elements; it would probably be worth your while to try to find them. All of them except

     o   o   o   o

give rise to more than one partial order on $\{1,2,3,4\}$, some of them as many as $4!=24$; the total number of partial orders on $\{1,2,3,4\}$ turns out to be $219$.

share|cite|improve this answer
The 3 element set is much clearer to me now. Thank you very much for the detailed answer! I tried finding all Hasse diagrams for the 4 element set, but I can only think of 12 types. (I drew them by hand, so it is difficult to display them on here.) Is there some list of diagrams I can compare mine to, to see which ones I missed? – user41419 Nov 21 '12 at 6:21
@user41419: You can find the complete set in Fig. 3.1 on p. 279 of Vol. 1 of Stanley’s Enumerative Combinatorics, which you can download in PDF form here. (There’s probably a more convenient source out there, but I happen to know of this one.) – Brian M. Scott Nov 21 '12 at 6:29
Thanks for the source! It looks rather useful. I'll definitely remember it! – user41419 Nov 21 '12 at 6:43
@user41419: You’re welcome! – Brian M. Scott Nov 21 '12 at 6:46
@Mithleth: Thanks for catching that typo. So far as I know, there is no nice formula for the number of labelled posets on $n$ elements. – Brian M. Scott Jun 20 at 10:27

I don't know any way to count them, otheer than to systematically list them. For $\{{a,b,c\}}$, you can have

  1. no pair related: just one way to do that,

  2. $a\lt b$, with $c$ incomparable: 3 ways to choose the small element, 2 ways to choose the large, 6 orders all told,

  3. a linear order, like $a\lt b\lt c$: 6 orders like this, from the 6 permutations of 3 objects,

  4. one element larger than the other two, those two being incomparable: 3 orders like this, from the 3 ways to choose the big element, and

  5. one element smaller than the other two, those two being incomparable: 3 orders like this, from the 3 ways to choose the small element.

All told, that's $1+6+6+3+3=19$.

There may be more information in the link at the URL I gave in my comment.

share|cite|improve this answer

This is the integer sequence A001035: for n=18 the number you are looking for is 241939392597201176602897820148085023. The problem has been quite extensively studied: see a detailed discussion on the A001035 link above.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.