# 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 $$\\emptyset\$$ are in $$\T\$$.

2. If $$\U, V\$$ are in $$\T\$$, then the union of those two sets is in $$\T\$$.

3. If $$\U, V\$$ are in $$\T\$$, then the intersection of those two sets is in $$\T\$$.

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

## Specifications

• 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\}\$$.

1. $$\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.

2. 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? Commented Jun 8, 2011 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. Commented Jun 8, 2011 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. Commented Jun 8, 2011 at 9:13
• Is the improper subset of 2^X also a topology? Commented Jun 8, 2011 at 21:03
• @FUZxxl : Yes. I think that's called the discrete topology. Commented Jun 9, 2011 at 0:50

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

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, 131 chars lambda n:sum(x&(x>>2**n-1)&all((~(x>>i&x>>j)|x>>(i|j)&x>>(i&j))&1 for i in range(2**n)for j in range(2**n))for x in range(2**2**n))  Expanded version: def f(n): count = 0 for x in range(2**2**n): # for every set x of subsets of [n] = {1,...,n} try: assert x & 1 # {} is in x assert (x >> 2 ** n - 1) & 1 # [n] is in x for i in range(2**n): # for every subset i of [n]... if x >> i & 1: # ...in x for j in range(2**n): # for every subset j of [n]... if x >> j & 1: # ...in x assert (x >> (i | j)) & 1 # their union is in x assert (x >> (i & j)) & 1 # their intersection is in x count += 1 except AssertionError: pass return count  For example, suppose n = 3. The possible subsets of [n] are 0b000 0b001 0b010 0b011 0b100 0b101 0b110 0b111  where the ith bit indicates whether i is in the subset. To encode sets of subsets, we notice that each of these subsets either belongs or does not belong to the set in question. Thus, for example, x = 0b10100001 0b000 # 1 0b001 # 0 0b010 # 1 0b011 # 0 0b100 # 0 0b101 # 0 0b110 # 0 0b111 # 1  indicates that x contains {}, {2}, and {1,2,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]]


# Jelly, 28 bytes

ŒP⁺f,œ|ɗþẎẎṢe¥€Ʋ;ẠCaiʋẠʋ€RS


Try it online!

So, incredibly, slow. Times out on TIO for all $$\n \ge 4\$$, and running it locally with $$\n = 4\$$ still didn't produce an output after 15 minutes. That is because this answer has a time complexity of $$\O(2^{2^n})\$$, as we calculate $$\\mathcal P(\mathcal P(\{1, 2, ..., n\}))\$$ and filter on topologies.

## How it works

ŒP⁺f,œ|ɗþẎẎṢe¥€Ʋ;ẠCaiʋẠʋ€RS - Main link. Takes n on the left
ŒP                           - Powerset of X = [1, 2, ..., n]
⁺                          - Powerset of that
f                         -       U ∩ V
œ|                      -       U ∪ V
,                        -       [U ∩ V, U ∪ V]
þ                   -     For all U ∈ T, V ∈ T, calculate h(U, V)
ẎẎ                 -     Flatten into a list of unions and intersections
Ṣ                -       Sort Z
e               -       Is Z ∈ T?
€             -     For each Z in the list of unions and intersections, find k(Z, T)
Ạ          -     Are all elements of T truthy?
C         -     Complement; are any falsey?
i       -     Index of X in T, or 0 if not present
a        -     And; are both true?
;           -   Concatenate the list of k(Z, T)s with l(T, X)
Ạ     -   Are all true?
R  - X = [1, 2, ..., n]
€   - Over each T ∈ P(P(X)), calculate f(T, X)
S - Count the truthy elements


# Scala, 450 343 bytes

Thanks to the comment, saved 107 bytes using some trivial tricks.

rewrite @user76284's solution into scala.

Using scala for calculation is so slow! On TIO, I only use one case f(4)=355

Golfed version. Try it online!

def f(n:Int)={var c=0;for(x<-0 until math.pow(2,math.pow(2,n)).toInt){try{assert((x&1)!=0);assert((x>>((math.pow(2,n)-1).toInt)&1)!=0);for(i<-0 until math.pow(2,n).toInt){if(((x>>i)&1)!=0){for(j<-0 until math.pow(2,n).toInt){if(((x>>j)&1)!=0){assert(((x>>(i|j))&1)!=0);assert(((x>>(i&j))&1)!= 0);}}}}; c+=1;}catch{case _:AssertionError=>;}};c}


Ungoled version. Try it online!

object Main {
def f(n: Int): Int = {
var count = 0
for (x <- 0 until math.pow(2, math.pow(2, n)).toInt) {
try {
assert((x & 1) != 0)
assert((x >> ((math.pow(2, n) - 1).toInt) & 1) != 0)
for (i <- 0 until math.pow(2, n).toInt) {
if ( ((x >> i) & 1) != 0) {
for (j <- 0 until math.pow(2, n).toInt) {
if ( ((x >> j) & 1) != 0) {
assert( ((x >> (i | j)) & 1) != 0)
assert( ((x >> (i & j)) & 1) != 0)
}
}
}
}
count += 1
} catch {
case _: AssertionError =>
}
}
count
}

def main(args: Array[String]): Unit = {
val n =4
val result = f(n)
println(s"f($n) =$result")
}
}


• Can you remove a lot of the spaces, and use single character variables names (e.g. c instead of count`) to save a bunch of bytes? Commented Apr 20, 2023 at 15:34