Sound and Fury

Signifying nothing

Ennumerating structures on sets

leave a comment »

I have a question: for a set of N elements, how many different ways are there of partitioning it? In other words, how many distinct equivalence relations are there on a set? Similarly, how many distinct strict total orderings are there? How many weak partial orderings?

All of these things (equivalence relations, orderings…) are determined by sets of ordered pairs on the set. So is it easier to calculate numerical formulae for each type of structure on the set, or is it easier to demonstrate that, for example there are more weak partial orderings than there are partitions… It’s trivial, for example, to show that there are at least as many weak partial orderings as there are strict total ones, since each strict total order is equivalent to a weak partial order.

There could be quite a lot of partitions. A partition is a subset of the power set. Or an element of the power set of the power set. So the absolute upper bound on partitions for a 4 element set is 2^(2^4) = 65,536. Obviously this is a ridiculously high figure, but I can’t see an easier way to get closer to the actual number. I am no good at combinatorics. But for the 4 element set you could probably just list all the possible partitions. First list all the ways the sets could break down:

  • 1,1,1,1
  • 2,1,1
  • 2,2
  • 3,1
  • 4

Then list the number of ways of splitting up the 4 elements, A,B,C,D into those sets.

  • Only one {1,1,1,1} partition
  • Six {2,1,1}
  • Six {2,2}
  • Four {3,1}
  • One {4}

For a total of 18 partitions. So there are more partitions than there are subsets. But for the 2 element set, the power set has 4 elements, whereas there are only two possible partitions. My guess is for bigger sets there will be more partitions than there are subsets.

As for strict total orderings, I think there will be N! of them. Because there are N choices for the maximal element, N-1 choices for the next “biggest” and so on. So the 4 element set has 24 strict total orderings on it. N! > 2^N for N>3. As for weak partial ordering, there’s probably even more of them…

What other kinds of structure can one impose on a set? If one thinks of graph theory in terms of set theoretic structure, what then? In undirected graphs, the edges of a graph are pairs of elements of the set of vertices. I just did a little googling and learned that there is something called “graph ennumeration” which is where one studies the number of graphs with a certain number of vertices that have certain properties. Much like the classification of finite groups, I suppose. So for example there are no asymmetric graphs with less than 5 vertices. (Or possibly 6?)

Anyway, that’s just what I was thinking about this morning, when I should probably have been trying to understand the game theory lecture…


Written by Seamus

February 10, 2009 at 2:51 pm

Posted in maths

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: