Number of topolgies and equivalence relations on a finite set

By Pooya Farshim on Tuesday, November 26, 2002 - 03:16 pm:

Given a finite set X={1,2,...,n}:
(a) How many equivalence relations are there on X?
(b) How many topologies? How many are non-homeomorphic?

By Ben Tormey on Tuesday, November 26, 2002 - 05:45 pm:

How many topologies?

There is a very complicated formula for this; see Sloane's integer sequence A000798 .

By Demetres Christofides on Friday, December 06, 2002 - 09:42 am:

Equivalence relations partition the set. Every partition corresponds to a unique equivalence relation.

Demetres

By Pooya Farshim on Saturday, December 07, 2002 - 01:24 am:

The solution to (a) is:

f(n,m)=

(-1)^m

m
å
r=1

(-1)^r

æ
ç
è

ö
÷
ø

rⁿ

E(n)=

n
å
m=1

f(n,m)

Here E(n) is the number of equivalence relations on a set of n distinct objects. Any suggestions to simplify E(n)?

By Ben Tormey on Saturday, December 07, 2002 - 05:25 pm:

Well, f(n, m) is obviously a Stirling number of the second kind; f(n, m) = the coefficient of xⁿ /n! in (e^x -1)^k /k! is the only fairly explicit formula I know...

By Pooya Farshim on Saturday, December 07, 2002 - 06:01 pm:

Well, I was kind of thinking the solution might hit the good old stirling numbers at some stage.