Calculate the number of topologies on {1,2,...,n}

Question

Task

Write a function/program which takes n as a parameter/input and prints/returns the number of topologies (which is demonstrated below) on the set {1,2,...,n}.

Definition of Topology

Let X be any finite set, and assume that T, which is subset of the power set of X (i.e. a set containing subsets of X), satisfy these conditions:

1. X and the empty set are in T.

2. If two set U and V are in T, then the union of those two sets are in T.

3. If two set U and V are in T, then the intersection of those two sets are in T.

...then T is called the topology on X.

Specifications

1. Your program is either:

   • a function which takes n as a parameter
   • or a program which inputs n

   and prints or returns the number of (distinct) topologies on the set {1,2,...,n}.

2. n is any non-negative integer which is less than 11 (of course there's no problem if your program handles n bigger than 11), and the output is a positive integer.

3. Your program should not use any kinds of library functions or native functions which calculates the number of topology directly.

Example input (value of n) : 7

Example output/return : 9535241

You may check your return value at here or here.

Of course, shortest code wins.

---

The winner is decided, however, I may change the winner if shorter code appears..

Answer 1

Haskell, 144 characters

import List
import Monad
p=filterM$const[True,False]
f n=sum[1|t<-p$p[1..n],let e=(`elem`t).sort,e[],e[1..n],all e$[union,intersect]`ap`t`ap`t]

Almost a direct implementation of the specification, modulo some monad magic.

Extremely slow for n > 4.

Answer 2

Python, 147 chars

N=input()
S=lambda i,K:1+sum(0if len(set(j&k for k in K)-K)-1 else S(j+1,K|set(j|k for k in K))for j in range(i,2**N))
print S(1,set([0,2**N-1]))

Quick for N<=6, slow for N=7, unlikely N>=8 will ever complete.

Individual sets are represented by integer bitmasks, and topologies by sets of bitmasks. S(i,K) computes the number of distinct topologies you can form by starting with K and adding sets with bitmasks >= i.

Answer 3

Zsh, 83 characters

This solution matches the letter of your requirements (but not, of course, the spirit). There's undoubtedly a way to compress the numbers even more.

a=(0 3 S 9U 5CT 4HO6 5ODFS AMOZQ1 T27JJPQ 36K023FKI HW0NJPW01R);echo $[1+36#$a[$1]]