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

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..

• Does it have to give results this century, or is a proof of correctness good enough? – Peter Taylor Jun 8 '11 at 8:30
• @Peter In fact, I have no idea how long it'll take. Therefore proof of correctness of the program is good enough, but still the program should give a result in a reasonable time if n is small, like 4~5. – JiminP Jun 8 '11 at 8:57
• @JiminP, it seems that computing it for n=12 was worth a paper back in the day, and there isn't a known formula. For 4 or 5 I suspect it's doable in a few minutes by brute force. – Peter Taylor Jun 8 '11 at 9:13
• Is the improper subset of 2^X also a topology? – FUZxxl Jun 8 '11 at 21:03
• @FUZxxl : Yes. I think that's called the discrete topology. – JiminP Jun 9 '11 at 0:50

import List
p=filterM$const[True,False] f n=sum[1|t<-p$p[1..n],let e=(elemt).sort,e[],e[1..n],all e$[union,intersect]aptapt]  Almost a direct implementation of the specification, modulo some monad magic. Extremely slow for n > 4. ## 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. ## 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]]