Direct and Elementary Approach to Enumerate Topologies on a Finite Set

Messaoud Kolli Faculty of Science Department of Mathematics King Khaled University Abha Saudi Arabia

                      kmessaud@kku.edu.sa

Abstract

Let 𝔼 be a set with n elements, and let τ(n, k) be the set of all labelled topologies on 𝔼, having k open sets, and T (n, k) = |τ(n, k)|. In this paper, we use a direct approach to compute T (n, k) for all n ≥ 4 and k ≥ 6 · 2^{n−4}.

1 Introduction

Let 𝔼 be a set with n elements. The problem of determining the total number of labelled topologies T (n) one can define on 𝔼 is still an open question. Sharp [3], and Stephen [6] had shown that every topology which is not discrete contains k ≤ 3·2^{n−2} open sets, and that this bound is optimal. Stanley [5] computed all labelled topologies on 𝔼, with k ≥ 7 · 2^{n−4} open sets. In the opposite sense, Benoumhani [1] computed, for all n, the total number of labelled topologies with k ≤ 12 open sets. In the other hand, Erné and Stege [2] computed the total number of topologies, for n ≤ 14. In this paper, we use a direct approach to compute all labelled topologies on 𝔼 having k ≥ 6 · 2^{n−4} open sets. Furthermore, we confirm the results in [3, 5, 6]. This work is a continuation of the results of [1, 5]. Here is our approach. The set τ(n, k) is partitioned into two disjoint parts as follows:

τ(n, k) = τ_{1}(n, k) ∪ τ_{2}(n, k),

where

τ_{1}(n, k) = {τ = {∅, A_{1}, …, A_{k−2}, 𝔼} ∈ τ(n, k), such that ⋂_{i=1}^{k−2} A_{i} ≠ ∅} ,
τ_{2}(n, k) = τ(n, k) − τ_{1}(n, k).

In Theorem 2.1, we prove that the cardinal T_{1}(n, k) = |τ_{1}(n, k)| satisfies

T_{1}(n, k) = ∑_{l=1}^{n−1} \binom{n}{l}T (l, k − 1), ∀ n ≥ 1.

This relation enables us to compute T_{1}(n, k) for k > 5 · 2^{n−4}. For the determination of the cardinal T_{2}(n, k) = |τ_{2}(n, k)| , we introduce the notion of minimal open set (Definition 2.2), and we designate by τ_{2}(n, k, α) the labelled topologies in τ_{2}(n, k) having α ≥ 2 minimal open sets. In Lemma 2.2, it is proved that if k > 5·2^{n−4} such that k ≠ 6·2^{n−4}, and k ≠ 2^{n−1}, then all the minimal open sets of τ are necessarily singletons. So, we can compute the numbers T_{2}(n, k, α) for all n ≥ 4, k ≥ 6 · 2^{n−4}, and α ≥ 2.

2 Basic Results

Theorem 2.1. For every integer n > 1, and 2 ≤ k ≤ 2^{n}, we have

T_{1}(n, k) = ∑_{l=1}^{n−1} \binom{n}{l}T (l, k − 1),

with the convention that T (l, 1) = 0.

Proof. Let A ⊂ 𝔼, with |A| = l ≤ n − 1, and let τ′ be a topology on A, and having k − 1 open sets. To this topology we associate the following one

Φ_{A}(τ′) = τ = {O ∪ A^{c}, O ∈ τ′} ∪ {∅}.

Obviously Φ_{A} is an injective mapping on τ(l, k − 1) into τ_{1}(n, k). In the other hand, if |A| = |B| = l ≤ n − 1 and A ≠ B, then

R(Φ_{A}) ∩ R(Φ_{B}) = ∅,

where R(Φ_{A}) is the image of Φ_{A}. This shows that

T_{1}(n, k) ≥ ∑_{l=1}^{n−1} \binom{n}{l}T (l, k − 1).

Conversely, if τ = {∅, A_{1}, …, A_{k−2}, 𝔼} ∈ τ_{1}(n, k), with A_{1} = ⋂_{i=1}^{k−2} A_{i}, then τ′ = {O − A_{1}, O ∈ τ}

is a topology on A_{1}^{c}, having k−1 open sets, and Φ_{A_{1}^{c}}(τ′) = τ. This shows the other inequality, and completes the proof.

The following definition will be needed in the sequel.

Definition 2.2. Let τ = {∅, A_{1}, …, A_{k−2}, 𝔼} ∈ τ(n, k). The element A_{i} is called a minimal open set, if it satisfies:

A_{i} ∩ A_{j} = A_{i} or ∅, ∀ j = 1, …, k − 2.

Remark 2.3. i) A topology on 𝔼 is a bounded lattice with (1 = 𝔼, 0 = ∅). A minimal open set is in fact an atom. Recall that an atom in a partially ordered set is an element which covers 0. So, every topology has at least one minimal open set, and τ_{1}(n, k) is the subset of topologies having exactly one minimal open set.

ii) If τ ∈ τ_{2}(n, k), then τ has at least two minimal open sets.

iii) The space 𝔼 is a union of α minimal open sets for the topology τ ∈ τ(n, k) if and only if k = 2^{α}.

iv) If τ has α minimal open sets, then k ≥ 2^{α}.

Definition 2.4. For α ≥ 2, we define

τ_{2}(n, k, α) = {τ ∈ τ_{2}(n, k), τ has α minimal open sets } .

Note that if α_{1} ≠ α_{2}, then τ_{2}(n, k, α_{1}) ∩ τ_{2}(n, k, α_{2}) = ∅. So

T_{2}(n, k) = ∑_{α≥2, 2^{α}≤ k} T_{2}(n, k, α).

The computation of T_{2}(n, k) is then equivalent to the computation of T_{2}(n, k, α), for α ≥ 2, under the condition 2^{α} ≤ k . If k = 2^{α}, then

T_{2}(n, 2^{α}, α) = S(n, α),

where S(n, α) is the Stirling number of the second kind.

Lemma 2.1. Let n ≥ 1, α ≥ 2. Then τ_{2}(n, k, α) is empty, for k > 2^{n−1} + 2^{α−1}. In addition, this bound is optimal:

τ_{2}(n, 2^{n−1} + 2^{α−1}, α) ≠ ∅.

Proof. We argue by contradiction. Suppose that τ ∈ τ_{2}(n, k, α), and write it as

τ = {∅, A_{1}, …, A_{α}, …, 𝔼} ,

where A_{1}, ..., A_{α} are the α minimal open sets of τ. Put A = ⋃_{i=1}^{α} A_{i}, the topology τ′ =

{O − A, O ∈ τ} on A^{c} has at least ⌈k 2^{1−α} − 1⌉ open sets. In the other hand, |A^{c}| ≤ n−α, and since τ′ is at most the discrete topology, we obtain

k 2^{1−α} − 1 ≤ |τ′| ≤ 2^{n−α}.

This contradiction proves that τ_{2}(n, k, α) is empty. The second assertion will be proved in the next section.

Lemma 2.2. Let τ ∈ τ_{2}(n, k, α), with k > 5 · 2^{n−4}, k ≠ 6 · 2^{n−4}, and k ≠ 2^{n−1}. Then, all the minimal open sets of τ are singletons.

Proof. Let τ = {∅, A_{1}, …, A_{α}, …, 𝔼} ∈ τ_{2}(n, k, α), where A_{1}, …, A_{α} are its minimal open

sets, and suppose that A = ⋃_{i=1}^{α} A_{i} has more than α + 1 elements. The same argument used

in the previous Lemma gives 5 · 2^{n−4} < k ≤ 2^{n−2} + 2^{α−1}. This last inequality is possible only for α = n − 1 or α = n − 2. In the first case, 𝔼 is a union of n − 1 minimal open sets, so k = 2^{n−1}, which is excluded. In the second, necessarily k = 6 · 2^{n−4}, which is also excluded. So, all the minimal open sets of τ are singletons.

3 Computation

Firstly, we compute T_{2}(n, k, α), for k ≥ 6 · 2^{n−4} and α ≥ 2. We use the notation

(n)_{l} = n(n − 1) ⋯ (n − l + 1),

and we convenient that if l > n, then (n)_{l} = 0. We start by the number of topologies τ ∈ τ_{2}(n, k, α), such that τ has at least one minimal open set, which is not a singleton. For this, the previous Lemma gives k = 2^{n−1} or k = 6 · 2^{n−4}. If k = 2^{n−1}, then α = n − 1 and the number of these topologies is

S(n, n − 1) = \frac{(n)_{2}}{2} .

If k = 6 · 2^{n−4}, we have α = n − 2, and the number of these topologies is

2(n − 2)\binom{n}{n − 2}\binom{n − 2}{1} = (n − 2) (n)_{3}.

The remaining topologies of τ_{2}(n, k, α) have the property that all their minimal open sets are singletons. For this, let τ ∈ τ_{2}(n, k, α)

τ = {∅, A_{1}, …, A_{α}, …, 𝔼} .

Put α = n − i, 0 ≤ i ≤ n − 2, and A = ∪_{i=1}^{α}A_{i} . The topology τ′ = {O − A, O ∈ τ} (on A^{c}), can be written as follows:

τ′ = {∅, C_{1}, …, C_{m}} , m ∈ {0, 1, 2, …, 5 · 2^{i−3} − 1, 3 · 2^{i−2} − 1, 2^{i} − 1} .

To reconstruct τ from τ′, we remark that every C_{j}, if it exists, generates 2^{i_{j}} open sets in τ, with i_{j} ≤ n − i − 1. So, the number k has necessarily the form:

k = 2^{n−i} + 2^{i_{1}} + 2^{i_{2}} + ... + 2^{i_{m}},

where the integers i_{j} , 1 ≤ j ≤ m can be dependant. Our approach is that for all α, 2 ≤ α ≤ n, we determine all possibilities of the number k, and next the number of all these topologies.

For \underline{α = n.} A^{c} = ∅; so m = 0, k = 2^{n} and T_{2}(n, 2^{n}, n) = 1. This case corresponds to the discrete topology.

For \underline{α = n − 1.} A^{c} = \{x\}; so m = 1, and τ′ = \{∅, C_{1} = \{x\}\}. All the possibilities of k are given by

k = 2^{n−1} + 2^{n−1−j}, 1 ≤ j ≤ n − 1.

The number of these topologies is

T_{2}(n, 2^{n−1} + 2^{n−1−j}, n − 1) = n\binom{n − 1}{j} = \frac{(n)_{j+1}}{j!} , 1 ≤ j ≤ n − 1.

For \underline{α = n − 2.} A^{c} = \{x, y\} , τ′ = \{∅, C_{1}, …, C_{m}\} , with m = 1, 2 or 3.

If m = 1, τ′ = {∅, C_{1} = {x, y}}. Since we are supposing k ≥ 6 · 2^{n−4}, the unique possibility is that C_{1} generates 2^{n−3} open sets. So, k = 2^{n−2} + 2^{n−3} = 6 · 2^{n−4}, and the number of these topologies is

\binom{n}{n − 2}\binom{n − 2}{1} = \frac{(n)_{3}}{2} .

If m = 2, τ′ = {∅, C_{1} = {x} , C_{2} = {x, y}} or τ′ = {∅, C_{1} = {y} , C_{2} = {x, y}} . Here we have two categories of solutions:

a) C_{1} generates 2^{n−3} open sets, and C_{2} generates 2^{n−3−j}, 0 ≤ j ≤ n−3, open sets. Hence

k = 2^{n−2} + 2^{n−3} + 2^{n−3−j} = 6 · 2^{n−4} + 2^{n−3−j}, 0 ≤ j ≤ n − 3.

The number of such topologies is

2(j + 1)\binom{n}{n − 2}\binom{n − 2}{j + 1} = \frac{(n)_{j+3}}{j!} .

b) C_{1} generates 2^{n−4} open sets and also C_{2} generates 2^{n−4}. So, k = 2^{n−2} +2^{n−4} +2^{n−4} = 6 · 2^{n−4}, and the number in this case is

2 \binom{n}{n − 2}\binom{n − 2}{2} = \frac{(n)_{3}}{2} .

If m = 3, τ′ = {∅, C_{1} = {x} , C_{2} = {y} , C_{3} = {x, y}}. There are 8 categories of solutions:

a) Each C_{j}, j = 1, 2, 3 generates 2^{n−3} open sets. So, k = 2^{n−2} + 2^{n−3} + 2^{n−3} + 2^{n−3} = 10 · 2^{n−4}, and the wanted number is

\binom{n}{n − 2}\binom{n − 2}{1} = \frac{(n)_{3}}{2} .

b) C_{1} generates 2^{n−3} open sets, C_{2} and C_{3} each one generates 2^{n−3−j} open sets, with 1 ≤ j ≤ n − 3. So, k = 2^{n−2} + 2^{n−3} + 2^{n−3−j} + 2^{n−3−j} = 6 · 2^{n−4} + 2^{n−2−j}, 1 ≤ j ≤ n − 3, and the number of these topologies is

2(j + 1)\binom{n}{n − 2}\binom{n − 2}{j + 1} = \frac{(n)_{j+3}}{j!} .

c) C_{1} and C_{2} each one generates 2^{n−3} open sets, but C_{3} generates 2^{n−4} open sets. So, k = 2^{n−2} + 2^{n−3} + 2^{n−3} + 2^{n−4} = 9 · 2^{n−4}, and the number of these topologies is

2\binom{n}{n − 2}\binom{n − 2}{2} = \frac{(n)_{4}}{2} .

d) C_{1} generates 2^{n−3} open sets, C_{2} generates 2^{n−2−j}, 2 ≤ j ≤ n − 3 open sets. So, C_{3} generates 2^{n−3−j} open sets, and k = 2^{n−2}+2^{n−3}+2^{n−2−j} +2^{n−3−j} = 6·2^{n−4}+3·2^{n−3−j}, 2 ≤ j ≤ n − 3. The number of these topologies is

2(j + 1)\binom{n}{n − 2}\binom{n − 2}{j + 1} = \frac{(n)_{j+3}}{j!} .

e) C_{1}, C_{2} and C_{3} each one generates 2^{n−4} open sets. So, k = 2^{n−2} + 2^{n−4} + 2^{n−4} + 2^{n−4} = 7 · 2^{n−4}, and the number of these topologies is

\binom{n}{n − 2}\binom{n − 2}{2} = \frac{(n)_{4}}{4} .

f) C_{1} and C_{2}, each one generates 2^{n−4} open sets, but C_{3} generates 2^{n−5} open sets. In this case k = 2^{n−2} + 2^{n−4} + 2^{n−4} + 2^{n−5} = 13 · 2^{n−5}, and the number of these topologies is

6\binom{n}{n − 2}\binom{n − 2}{3} = \frac{(n)_{5}}{2} .

g) C_{1} generates 2^{n−4} open sets, and each one of C_{2}, C_{3} generates 2^{n−5}. So, k = 2^{n−2} + 2^{n−4} + 2^{n−5} + 2^{n−5} = 6 · 2^{n−4}, and the number of these topologies is

6\binom{n}{n − 2}\binom{n − 2}{3} = \frac{(n)_{5}}{2} .

h) Each one of C_{1}, C_{2} generates 2^{n−4} open sets, but C_{3} generates 2^{n−6} . So, k = 2^{n−2} + 2^{n−4} + 2^{n−4} + 2^{n−6} = 25 · 2^{n−6}, and the number of these topologies is

6\binom{n}{n − 2}\binom{n − 2}{4} = \frac{(n)_{6}}{8} .

All the other cases give k < 6 · 2^{n−4}. We resume all these results in the next statement.

Theorem 3.1. Let n ≥ 4, and α = n − 2. Then we have

\begin{matrix}k & T_{2}(n, k, n − 2) \\ 6 · 2^{n−4} & (n − 1)(n)_{3} + \frac{1}{2}(n)_{5} \\ 6 · 2^{n−4} + 1 & (n)_{3} \\ 6 · 2^{n−4} + 2^{n−3−j}, 4 ≤ j ≤ n − 4 & \frac{(n − 2) (n)_{j+3}}{(j + 1)!} \\ 6 · 2^{n−4} + 3 · 2^{n−3−j}, 5 ≤ j ≤ n − 3 & \frac{(n)_{j+3}}{j!} \\ 25 · 2^{n−6} & \frac{7}{24}(n)_{6} + \frac{1}{24}(n)_{7} \\ 51 · 2^{n−7} & \frac{1}{24}(n)_{7} \\ 13 · 2^{n−5} & (n)_{5} + \frac{1}{6}(n)_{6} \\ 27 · 2^{n−6} & \frac{1}{6}(n)_{6} \\ 7 · 2^{n−4} & \frac{5}{4} (n)_{4} + \frac{1}{2}(n)_{5} \\ 15 · 2^{n−5} & \frac{1}{2}(n)_{5} \\ 2^{n−1} & (n)_{3} + (n)_{4} \\ 9 · 2^{n−4} & \frac{1}{2}(n)_{4} \\ 10 · 2^{n−4} & \frac{1}{2}(n)_{3} \end{matrix}

All other topologies in τ_{2}(n, k, n − 2) have k < 6 · 2^{n−4} open sets. We use the same reasoning as above, to show the following theorem. Theorem 3.2. Let n ≥ 5, and α = n − i, 3 ≤ i ≤ n − 2. Then, the following results hold.

For α = n − 3, if n = 5, we have

\begin{matrix}k & 12 & 13 & 14 & 15 & 18 \\ T_{2}(5, k, 2) & 360 & 60 & 180 & 60 & 20 \end{matrix}

If n ≥ 6, we have

k  6 · 2^{n−4}  25 · 2^{n−6} 13 · 2^{n−5} 27 · 2^{n−6}  7 · 2^{n−4}  15 · 2^{n−5} 9 · 2^{n−4}
T_{2}(n, k, n − 3) (n)_{4} + \frac{5}{2}(n)_{5}  \frac{1}{4}(n)_{6}  \frac{1}{2}(n)_{5}  \frac{1}{6}(n)_{6} (n)_{4} + \frac{1}{2}(n)_{5}  \frac{1}{2}(n)_{5}  \frac{1}{6}(n)_{4}
+\frac{5}{4}(n)_{6}

For α = n − 4, and n ≥ 6

\begin{matrix}k & 25 · 2^{n−6} & 13 · 2^{n−5} & 27 · 2^{n−6} & 17 · 2^{n−5} \\ T_{2}(n, k, n − 4) & \frac{1}{8}(n)_{6} & \frac{1}{2}(n)_{5} + \frac{1}{6}(n)_{6} & \frac{1}{6}(n)_{6} & \frac{1}{24}(n)_{5} \end{matrix}

For α = n − i, 5 ≤ i ≤ n − 2, and n ≥ 7

\begin{matrix}k & 6 · 2^{n−4} + 2^{n−i−1} & 6 · 2^{n−4} + 3 · 2^{n−i−2} & 2^{n−1} + 2^{n−i−1} \\ T_{2}(n, k, n − i) & \frac{(n − 2)}{(i − 1)!} (n)_{i+1} & \frac{1}{(i − 1)!} (n)_{i+2} & \frac{(n)_{i+1}}{i!} \end{matrix}

All other topologies in τ_{2}(n, k, n − i), 3 ≤ i ≤ n − 2, have k < 6 · 2^{n−4} open sets.

Now, we compute T_{1}(n, k), for k > 5 · 2^{n−4}.

Theorem 3.3. For all n ≥ 5, and k > 5 · 2^{n−4}, we have:

T_{1}(n, 2^{n−1} + 1) = n,
T_{1}(n, 3 · 2^{n−3} + 1) = (n)_{3},
T_{1}(n, 5 · 2^{n−4} + 1) = (n)_{4},
T_{1}(n, k) = 0, otherwise.

Proof. Obviously, we have T_{1}(n, 2^{n−1} + 1) = nT (n − 1, 2^{n−1}) = n, T_{1}(n, 3 · 2^{n−3} + 1) = nT (n − 1, 3 · 2^{n−3}) = n (n − 1)_{2} = (n)_{3}, and T_{1}(n, 5 · 2^{n−4} + 1) = nT (n − 1, 5 · 2^{n−4}) = n(n − 1)_{3} = (n)_{4}. If k > 2^{n−1} + 1, we have T (l, k − 1) = 0, for 1 ≤ l ≤ n − 1, so T_{1}(n, k) = 0. If 5 · 2^{n−4} + 1 < k < 2^{n−1} + 1, and k ≠ 3 · 2^{n−3} + 1, the Theorem 2.1 yields T_{1}(n, k) = nT (n−1, k −1). But we know that T (n−1, k −1) = 0, for 5·2^{n−4} < k −1 < 2^{n−1}, and k ≠ 3 · 2^{n−3} + 1; so we deduce T_{1}(n, k) = 0, and the proof is complete.

Now, we can give the number of all labelled topologies with k ≥ 6 · 2^{n−4} open sets.

Theorem 3.4. Suppose that n ≥ 7, then the total number of labelled topologies, with k ≥ 6 · 2^{n−4} open sets, is given by

k  T_{2}(n, k)  T_{1}(n, k)  T (n, k)
6 · 2^{n−4}  (n − 1)(n)_{3} + (n)_{4}+  0  (n − 1)(n)_{3} + (n)_{4}
3 (n)_{5} + \frac{5}{4}(n)_{6}  +3 (n)_{5} + \frac{5}{4}(n)_{6}
6 · 2^{n−4} + 1  (n)_{3}  (n)_{3}  2 (n)_{3}
6 · 2^{n−4} + 2^{n−3−j}, 4 ≤ j ≤ n − 4  \frac{2 (n − 2) (n)_{j+3}}{(j + 1)!}  0  \frac{2 (n − 2)(n)_{j+3}}{(j + 1)!}
6 · 2^{n−4} + 3 · 2^{n−3−j}, 5 ≤ j ≤ n − 3  \frac{2}{j!}(n)_{j+3}  0  \frac{2 (n)_{j+3}}{j!}
25 · 2^{n−6}  \frac{n + 14}{24}(n)_{6} + \frac{1}{24}(n)_{7}  0  \frac{(n + 14) (n)_{6}}{24} + \frac{(n)_{7}}{24}
51 · 2^{n−7}  \frac{1}{12}(n)_{7}  0  \frac{1}{12}(n)_{7}
13 · 2^{n−5}  2 (n)_{5} + \frac{1}{3}(n)_{6}  0  2 (n)_{5} + \frac{1}{3}(n)_{6}
27 · 2^{n−6}  \frac{1}{2}(n)_{6}  0  \frac{1}{2}(n)_{6}
7 · 2^{n−4}  \frac{9}{4} (n)_{4} + (n)_{5}  0  \frac{9}{4} (n)_{4} + (n)_{5}
15 · 2^{n−5}  (n)_{5}  0  (n)_{5}
2^{n−1}  \frac{1}{2}(n)_{2} + (n)_{3} + (n)_{4}  0  \frac{1}{2}(n)_{2} + (n)_{3} + (n)_{4}
2^{n−1} + 1  n  n  2 n
2^{n−1} + 2^{n−j−1}, 5 ≤ j ≤ n − 2  \frac{2}{j!}(n)_{j+1}  0  \frac{2}{j!}(n)_{j+1}
17 · 2^{n−5}  \frac{1}{12}(n)_{5}  0  \frac{1}{12}(n)_{5}
9 · 2^{n−4}  \frac{5}{6}(n)_{4}  0  \frac{5}{6}(n)_{4}
10 · 2^{n−4}  (n)_{3}  0  (n)_{3}
3 · 2^{n−2}  (n)_{2}  0  (n)_{2}
2^{n}  1  0  1

For n = 6, the total number of labelled topologies having k ≥ 24 open sets is given by

\begin{matrix}k & |τ_{2}(6, k)| & |τ_{1}(6, k)| & |τ(6, k)| \\ 24 & 4020 & 0 & 4020 \\ 25 & 480 & 120 & 600 \\ 26 & 1680 & 0 & 1680 \\ 27 & 360 & 0 & 360 \\ 28 & 1530 & 0 & 1530 \\ 30 & 720 & 0 & 720 \\ 32 & 495 & 0 & 495 \\ 33 & 6 & 6 & 12 \\ 34 & 60 & 0 & 60 \\ 36 & 300 & 0 & 300 \\ 40 & 120 & 0 & 120 \\ 48 & 30 & 0 & 30 \\ 64 & 1 & 0 & 1 \end{matrix}

For n = 5, the total number of labelled topologies having k ≥ 12 open sets is given by

\begin{matrix}k & |τ_{2}(5, k)| & |τ_{1}(5, k)| & |τ(5, k)| \\ 12 & 660 & 0 & 660 \\ 13 & 180 & 60 & 240 \\ 14 & 390 & 0 & 390 \\ 15 & 120 & 0 & 120 \\ 16 & 190 & 0 & 190 \\ 17 & 5 & 5 & 10 \\ 18 & 100 & 0 & 100 \\ 20 & 60 & 0 & 60 \\ 24 & 20 & 0 & 20 \\ 32 & 1 & 0 & 1 \end{matrix}

For n = 4, the total number of labelled topologies having k ≥ 6 open sets is given by

\begin{matrix}k = & 6 & 7 & 8 & 9 & 10 & 12 & 16 \\ |τ_{2}(4, k)| & 72 & 30 & 54 & 16 & 24 & 12 & 1 \\ |τ_{1}(4, k)| & 0 & 24 & 0 & 4 & 0 & 0 & 0 \\ |τ(4, k)| & 72 & 54 & 54 & 20 & 24 & 12 & 1 \end{matrix}

All the others topologies on 𝔼 have k < 6 · 2^{n−4} open sets.

References

[1] M. Benoumhani, The number of topologies on a finite set, Journal of Integer sequences 9 (2006).

[2] M. Erne, K. Stege, Counting finite posets and topologies, Order 8 (1991), 247–265.

[3] H. Sharp. Jr, Cardinality of finite topologies, J. Combinatorial Theory 5 (1968), 82–86.

[4] N. J. A. Sloane, Online Encyclopedia of Integer Sequences,

   http://www.research.att.com/~njas/sequences/index.html.

[5] R. P. Stanley, On the number of open sets of finite topologies, J. Combinatorial Theory 10 (1971), 74–79.

[6] D. Stephen, Topology on finite sets, Amer. Math. Monthly 75 (1968), 739–741.

2000 Mathematics Subject Classification: Primary 05A15; Secondary 06A07, 06A99. Keywords: binary relation, enumeration, finite set, finite topology, partial order, posets.

(Concerned with sequences \underline{A000798}, \underline{A001930}, and \underline{A008277}.)

Received April 19 2006; revised version received February 28 2007. Published in Journal of Integer Sequences, March 19 2007.

Return to Journal of Integer Sequences home page.