Enumerating structure on sets, again.

The number of partitions on an N-membered set is called its “Bell number“. The number of strict total orders, I’m not sure about that… There is some relevant information here.

Well it’s good to see those problems solved, and I’m glad they weren’t trivial… Here is a more general issue. How many relations are there on a set? How many transitive? And so on.

So, a relation is simply a set of ordered pairs. So there are 2^X possible relations if there are X ordered pairs. For a set with N elements, there are N^2 ordered pairs. Thus 2^(N^2) relations on N elements. To give you an idea of scale, there are 65,536 relations on the 4 element set. But there are only 15 partitions on the 4 element set (not 18 as I said before; I counted each 2+2 partition twice.) So the properties of being transitive, reflexive and symmetrical must seriously cut down the number of relations! The only thing I’ve concluded in answer to this question is that there is an upper bound on the number of possible total relations on N elements: 2^(N^2) – 2^([n^2]/2). This is because the property of being total means that the size of the set of ordered pairs has to be big enough to contain at least one of (a,b) or (b,a) for every a,b. So small sets of pairs are ruled out.