The Number of Topologies on a Finite Set

Moussa Benoumhani Faculty of Science Department of Mathematics Sana’a University P.O. Box 14026 Sana’a Yemen

                     benoumhani@yahoo.com

Abstract

Let X be a finite set having n elements. How many different labeled topologies one can define on X? Let T (n, k) be the number of topologies having k open sets. We compute T (n, k) for 2 ≤ k ≤ 12, as well as other results concerning T_{0} topologies on X having n + 4 ≤ k ≤ n + 6 open sets.

1 Introduction

Recall that a topology τ on the set X ≠ ϕ is a subset of P (X) that contains ϕ and X, and is closed under union and finite intersection. A topology on X is a sublattice of (P (X), ⊆) with the maximum element X, denoted by 1, and the minimum element, which is ϕ, denoted by 0. Let X be an n−element set. The number T (n) of topologies on X is exactly the number of sublattices of P (X), with 0 and 1.

There is another connection between the number of topologies on X, and the number of some kind of binary relations on it. A relation on X is called a preorder if it is reflexive and transitive. Let Q_{n} denotes the number of such relations. It is known that T (n) = Q_{n}. A preorder on X which is transitive is a partial order. The subset A ⊂ X of the preordered set X is called an ideal if x ∈ A and y ≤ x implies y ∈ A. Let P_{n} denotes the total number of partial orders on X. Then P_{n} is also the number of T_{0} topologies one can define on X. Note that the open sets in the topology correspond to the ideals in the preorder: a topology on X having k open sets, corresponds to a preorder with k ideals and vice versa.

Efficient computation of the total number of labeled topologies T (n) one can define on X is still an open question. There is no known simple formula giving T (n). For small values of n, this may be done by hand; for example, T (1) = 1, T (2) = 4, and T (3) = 29. For n ≥ 4, the calculations are complicated. The online encyclopedia of N. J. A. Sloane [2] gives the value of T (n) for 1 ≤ n ≤ 14.

An approach towards the determination of T (n) is as follows. Let t(n, k) be the set of all labeled topologies on X and having k open sets (or, which is the same, the number of preorders on X having k ideals), 2 ≤ k ≤ 2^{n}, and T (n, k) = |t(n, k)|. So, T (n) = ∑_{k≥2} T (n, k).

Obviously, we have

T (n, 2) = T (n, 2^{n}) = 1
T (n, 3) = 2^{n} − 2

For k ≥ 4, the determination of T (n, k) is not as straightforward as for T (n, 2) and T (n, 3). The numbers T (n, k) have been determined for some values of k. For instance, R. Stanley [3] computed T (n, k) for large values of k, viz.; 3 · 2^{n−3} < k < 2^{n}. Also, he determined labeled T_{0} topologies on X having either n + 1, n + 2, or n + 3 open sets.

In this paper, we compute T (n, k) for 2 ≤ k ≤ 12, as well as the total number of labeled T_{0} topologies on X having n+4, n+5, n+6 open sets. We also give different proofs (shorter or simpler) of some known results in [1, 3, 2].

We need some preliminary definitions and results. Let us recall the definition of Stirling numbers of the second kind:

Definition 1.1. The number of partitions of a finite set with n elements into k blocks, is the Stirling number of the second kind. It is denoted S(n, k).

The explicit, and somewhat complicated formula for Stirling numbers of the second kind is

S(n, k) = S_{n, k} = \frac{1}{k!} ∑_{j=0}^{k}(−1)^{j} ( \begin{matrix}k \\ j \end{matrix} ) (k − j)^{n}.  (1)

Lemma 1.2. Let τ be a topology on a finite set X. Then τ^{c} = {A^{c}, A ∈ τ} is also a topology on X.

Remark 1.3. The previous lemma is not necessarily true if X is infinite. Note, also, if τ is a topology, it may happen that τ = τ^{c}. Take X = {a, b, c}, and τ = {ϕ, X, {a}, {b, c}}.

Definition 1.4. A chain topology on X, is a topology whose open sets are totally ordered by inclusion.

2 Topologies with small number of open sets

In this section we compute T (n, k) for 2 ≤ k ≤ 12. We need the following lemma

Lemma 2.1. (D. Stephen) Let C(n, k) be the number of chain topologies on X having k open sets. Then

C(n, k) = ∑_{l=1}^{n−1} \binom{n}{l} C(l, k − 1) = (k − 1)!S(n, k − 1)  (2)

Proof. This proof is shorter than that in Stephen [4]. First, there is a bijective correspondence between the k−ordered partitions (partitions having k blocks) of the set X and the chains of subsets of X having k (non empty and different from X) members: the chain ϕ ≠ A_{1} ⫋ A_{2} ⫋ A_{3} … ⫋ A_{k} ⫋ X, is associated with the partition (B_{1}, B_{2,} B_{3,} … B_{k}), where B_{1} = A_{1}, B_{i} = A_{i} − A_{i−1}, A_{k+1} = X − A_{k}. In the other hand, if (B_{1}, B_{2,} B_{3,} … B_{k}) is an ordered partition, the chain ϕ ≠ A_{1} ⫋ A_{2} ⫋ A_{3} … ⫋ A_{k−} ⫋ X, where A_{1} = B_{1}, A_{i} = A_{i−1} ∪ B_{i}, 2 ≤ i ≤ k − 1, is associated with the partition (B_{1}, B_{2,} B_{3,} … B_{k}). Now the cardinal of the ordered k-partitions is k!S(n, k), which is the desired result.

For the recursion, note that a chain topology on a subset A ⊆ X, 1 ≤ |A| = l ≤ n − 1, having k − 1 open sets, is a chain topology on X with k open sets. The total number of such

topologies on A is \binom{n}{l} C(l, k − 1). So, C(n, k = ∑_{l=1}^{n−l} \binom{n}{l} C(l, k − 1). ■

Now we are ready to prove our main result.

Theorem 2.2. For every n ≥ 1, we have

T (n, 4) = S_{n, 2} + 3!S_{n, 3} = 3^{n} − 5 · 2^{n−1} + 2
T (n, 5) = 3!S_{n, 3} + 4!S_{n, 4} = 4^{n} − 3^{n+1} + 3 · 2^{n} − 1
T (n, 6) = 3!S_{n, 3} + \frac{3}{2}4!S_{n, 4} + 5!S_{n, 5}
T (n, 7) = \frac{9}{4}.4!S_{n, 4} + 2.5!S_{n, 5} + 6!S_{n, 6}
T (n, 8) = S_{n, 3} + 2.4!S_{n, 4} + \frac{15}{4}.5!S_{n, 5} + \frac{5}{2}.6!S_{n, 6} + 7!S_{n, 7}
T (n, 9) = \frac{5}{6}4!S_{n, 4} + 5.5!S_{n, 5} + \frac{11}{2}6!S_{n, 6} + 3.7!S_{n, 7} + 8!S_{n, 8}
T (n, 10) = 4!S_{n, 4} + \frac{11}{2}5!S_{n, 5} + \frac{73}{8}6!S_{n, 6} + \frac{15}{2}7!S_{n, 7} + \frac{7}{2}8!S_{n, 8} + 9!S_{n, 9}
T (n, 11) = \frac{25}{6}5!S_{n, 5} + \frac{79}{6}6!S_{n, 6} + \frac{29}{2}7!S_{n, 7} + \frac{39}{4}8!S_{n, 8} + 4.9!S_{n, 9} + 10!S_{n, 10}.
T (n, 12) = \frac{1}{2}4!S_{n, 4} + \frac{9}{2}5!S_{n, 5} + 16.6!S_{n, 6} + \frac{295}{12}7!S_{n, 7} + \frac{85}{4}8!S_{n, 8} + \frac{49}{4}.9!S_{n, 9}

+ \frac{9}{2}.10!S_{n, 10} + 11!S_{n, 11}.

Proof. For every T (n, k), we list all the forms of the topologies in t(n, k), and then compute the topologies of each form. Let τ = {ϕ, X, A, B} ∈ t(n, 4), then either τ is a chain or has the form (A ∩ B = ϕ and A ∪ B = X).

[figure: •; ∅; •; A; •; B; •; X; •; ∅; •; A; •; X; •; B]

The two cases are disjoint.

Case (1): this is the number of chain topologies having 4 open sets; so the number is 3!S(n, 3).

Case (2): This is the total number of partitions of X into two blocks, and is done in S(n, 2) = 2^{n−1} − 1 different ways. Finally, the desired number is

T (n, 4) = 3!S(n, 3) + S(n, 2).

For T (n, 5), there are 3 forms:

[figure: •; •; ∅; •; B; A; •; C; •; X; •; •; A; •; X; •; B; C; ∅; •; •; •; A; •; C; •; B; ∅; X; •]

1) Chain topologies with 5 open sets.

2)(ϕ ⊂ C ⊂ B, ϕ ⊂ C ⊂ A, A ∪ B = X) or

3)(ϕ ⊂ A ⊂ C, ϕ ⊂ B ⊂ C, A ∪ B = C ⊊ X) .

The number of topologies in the first case is 4!S(n, 4). Cases (2) and (3) are symmetric (and different, i.e., these cases correspond to t and t^{c}). So, we compute only one, case (3). Let C ⊊ X be such that |C| = k, 2 ≤ k ≤ n − 1. This is chosen in \binom{n}{k}different ways, and then it is partitioned into two disjoint blocks: this is done in S(k, 2) = 2^{k−1} − 1 different ways. Furthermore, the number in case (3) is :

∑_{k=2}^{n−1} \binom{n}{k} (2^{k−1} − 1) = \frac{3^{n} − 3 · 2^{n} + 3}{2} = \frac{3!S(n, 3)}{2}·

So, the total number for (2) and (3) is 3!S(n, 3). Consequently, we get

T (n, 5) = 3!S(n, 3) + 4!S(n, 4) = 4^{n} − 3^{n+1} + 3 · 2^{n} − 1.

For T (n, 6), we have 5 forms, as indicated in the figure below:

[figure: •; •; •; ∅; •; B; A; •; C; •; D; X; •; •; C; •; X; •; B; A; D; ∅; •; •; •; •; A; •; C; •; B; ∅; X; •; D; •]

[figure: •; •; A; •; C; •; B; D; X; •; ∅; •; •; •; A; •; C; •; B; X; D; •; ∅; •]

1) Chain topologies with 6 open sets.

2)(A ∩ B = ϕ, A ∪ B = C, A ⊂ C, C ∩ D = B, C ∪ D = X)

3)(ϕ ⊊ A_{1} ⊊ A_{3} ⊊ A_{4} ⊊ X, and ϕ ⊊ A_{2} ⊊ A_{3} ⊊ A_{4} ⊊ X, A_{1} ∩ A_{2} = ϕ) , and its symmetric case.

4)ϕ ⊊ A_{1} ⊊ A_{2} ⊊ A_{4} ⊊ X,and ϕ ⊊ A_{1} ⊊ A_{3} ⊊ A_{4} ⊊ X, A_{2} ∪ A_{3} = A_{4}.

The number of topologies in the first case is 5!S(n, 5). The number in the second case is computed as follows: let C ⊊ X, such that 2 ≤ |C| = k ≤ n − 1. We then partition C in to two blocks A, B. To each partition (A, B) corresponds two topologies:

(ϕ, A, B, A ∪ B = C, A ∪ (X − B), X)

and

(ϕ, A, B, A ∪ B = C, B ∪ (X − A), X) .

So, the total number of topologies in this case is

2 ∑_{k=2}^{n−1} \binom{n}{k} (2^{k−1} − 1) = 3^{n} − 3.2^{n} + 3 = 3!S(n, 3).

For the third case, we choose A_{3}, 2 ≤ |A_{3}| = k ≤ n − 2, in \binom{n}{k} different ways and then partition it into 2 blocks, (A_{1}, A_{2}) with S(k, 2) = 2^{k−1} − 1 different ways. There remain (n − k) elements, from which we choose the elements of A_{4}: note that |A_{4}| = k + i ≤ n − 1. The number of these choices is \binom{n}{k} \binom{n−k}{i} S(k, 2). Finally the total number for the third case and its reciprocal is

2 ∑_{k=2}^{n−2} ∑_{i=1}^{n−k−1} \binom{n}{k} \binom{n − k}{i} (2^{k−1} − 1) = 4^{n} − 4 · 3^{n} + 3 · 2^{n+1} − 4 = 4!S(n, 4).

The last case is computed similarly and is equal to

\frac{4!S(n, 4)}{2}.

So, we obtain

T (n, 6) = 3!S(n, 3) + \frac{3}{2}4!S(n, 4) + 5!S(n, 5).

The computation of the remaining cases is similar to T (n, 5) and T (n, 6), but much longer. We note that for T (n, 7), we have 8 forms, for T (n, 8), there are 15 forms, for T (n, 9) there are 26 cases, and so on. ■

3 Topologies with large number of open sets

The following result is due to H. Sharp [1] and D. Stephen [4].

Theorem 3.1. For n ≥ 3, T (n, k) = 0 for 3 · 2^{n−2} < k < 2^{n}.

Sharp [1] proved this result using graph theory. Stephen’s proof [4]used topological facts. Here is another one, which is direct and allows us to compute T (n, 3 · 2^{n−2}).

Proof. Since we are looking for a non-discrete topology τ having the maximum of open sets, it must not contain all the singletons, so, there is an a ∈ X, such that {a} ∉ τ .We have to remove all subsets from P (X) such that their intersections give {a}, those are all \{a, x\}, except one, say, \{a, y\}. The number of these removed sets is \binom{n}{k}. Sets of the form \{a, x_{1}, x_{2}\} are also removed. Their number is \binom{n−2}{2}. In general all subsets of the form \{a, x_{1}, x_{2}, …, x_{k}\}, 3 ≤ k ≤ n − 2 must be removed. Their number is \binom{n−2}{k}. Finally, the total number of the removed sets is

∑_{k=0}^{n−2} \binom{n − 2}{k} = 2^{n−2}.

The remaining elements form a topology having 2^{n} − 2^{n−2} = 3 · 2^{n−2} open sets. ■

The following theorem gives the number of topologies for large k. The notation (n)_{k} = n(n − 1) ⋯ (n − k + 1) is used.

Theorem 3.2. (R. Stanley) For n ≥ 5, we have the following values

T (n, 3 · 2^{n−2}) = (n)_{2}
T (n, 5 · 2^{n−3}) = (n)_{3}
T (n, 9 · 2^{n−4}) = \frac{5(n)_{5}}{6}
T (n, 17 · 2^{n−5}) = \frac{(n)_{5}}{12}
T (n, 15 · 2^{n−5}) = (n)_{5}
T (n, 7 · 2^{n−4}) = \frac{9}{4}(n)_{5} + (n)_{5}
T (n, 2^{n−1}) = (n)_{4} + (n)_{3} + \frac{(n)_{2}}{2} .

Proof. We give only the proof of the first assertion, which is related to the previous Theorem. The element a is chosen in \binom{n}{1} = n ways. The other one , i.e; \{a, y\}, in \binom{n−1}{1} = (n − 1) ways. So the total number is n(n − 1). ■

Now let T_{0}(n, k) be the number of labeled T_{0} topologies on X having k open sets. This is also the number of labeled posets on X having k ideals. Since a topology is T_{0} if and only if it has a minimal base of n + 1, it follows then that T_{0}(n, k) = 0 for 2 ≤ k ≤ n. R. Stanley [3] determined T_{0}(n, k) for n + 1 ≤ k ≤ n + 3. We now determine T_{0}(n, n + 4), T_{0}(n, n + 5), T_{0}(n, n + 6):

Theorem 3.3. We have

T_{0}(n, n + 4) = \frac{(n − 3)(n^{2} + 15n + 20)}{48}n!, n ≥ 3.
T_{0}(n, n + 5) = \frac{n^{4} + 26n^{3} + 35n^{2} − 478n − 248}{384}n!, n ≥ 4, T_{0}(3, 8) = 1.

T_{0}(n, n + 6) = \frac{n^{5} − 15n^{4} + 1885n^{3} − 15265n^{2} + 53954n − 97680}{3840}n!, n ≥ 5

Proof. A topology with n + 4

open sets, on a set of n-element,

is T_{0} if and only if it contains 3

copies of the graph in the Figure

on the right.

[figure: •; •; •; •] Figure 1

Those are 8 elements, inserted in any place in the chain formed by the remaining elements, as indicated in the following figure:

[figure: •; •; •; •; •; •; •; •; •; •; ⋮; •; •; •; •; •; •; ⋮; •; •; •; •; •; •; •; •; •; •; •; •; ⋮; •; •; •; •; •; •; ⋮; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; ⋮; •; •; ⋮; •; •; •; •]

The total number in the first case is 2(n − 3)n!, in the second case is (n − 3)(n − 4)n!/2, and the total number in the last case is (n − 3)(n − 4)(n − 5)n!/48. Summing, we obtain the desired result. Also, for T_{0}(n, n + 5), these topologies are constituted by 4 copies of the graph in Figure 1, or a copy of a boolean algebra having 8 elements as indicated in Figure 2 (note that T_{0}(3, 8) = 1).

According to the disposition of these copies we have 5 cases: in the first, the number is

\frac{(n + 3)(n − 4)}{2}n!, in the second we have \frac{(2n − 9)(n − 4) + 1}{2}n! in the third case the num-

ber is \frac{(n − 4)(n − 5)(n − 6)}{8}n!. In the fourth case, \frac{(n − 4)(n − 5)(n − 6)(n − 7)}{384}n!. In the

last one, for the topologies having a copy of a boolean algebra of 8 elements, the number

is \frac{(n − 2)}{6}n!. The total number is obtained by summing these numbers in all the previous cases. For T_{0}(n, n + 6), we proceed in the same manner: A topology with (n + 6) open sets on an n-element set is T_{0} if and only if it contains 5 copies of the graph in Figure 1, or a copy of a boolean algebra with 8 elements and a copy of Figure 2. Note that T_{0}(4, 10) = 48. Let n > 4. Here too, according to the disposition of the graph in the

chain, we have 6 cases: 2(n^{2} − 6n + 6)n! in the first case . \frac{(n − 5)(n − 6)(n + 1)}{4}n! in

the second case. The number in the third case is \frac{(n − 5)(n^{2} − 12n + 38)}{4}n!. The num-

ber in the fourth case is \frac{(n − 5)(n − 6)(n − 7)(n − 8)}{192}n!.The number in the fifth case is

\frac{(n − 5)(n − 6)(n − 7)(n − 8)(n − 9)}{3840}n!. In the last case , we have a copy of a boolean alge-

bra and a copy of the graph in Figure 1. The total number in this case is \frac{(n^{2} + 5n − 12)}{12}n!. The total number is obtained by computing all topologies in all cases. ■

• • • • •[figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] • • •Figure 2

Let T_{0}^{h}(n, k) be the number of homeomorphic T_{0} topologies with k open sets. From the last theorem, we easily deduce

Theorem 3.4. We have

T_{0}^{h}(n, n + 4) = \frac{(n − 3)(n^{2} − 3n + 8)}{6}, n ≥ 3.
T_{0}^{h}(n, n + 5) = \frac{(n − 1)(n − 3)(n^{2} − 6n + 32)}{24}, n ≥ 4, T_{0}^{h}(3, 8) = 1.
T_{0}^{h}(n, n + 6) = \frac{n^{5} − 25n^{4} + 345n^{3} − 2015n^{2} + 5054n − 4320}{120}, n ≥ 5, T_{0}^{h}(4, 10) = 2.

For small n, we can use the previous results to compute T (n).

T (3, 2) = 1, T (3, 3) = 6, T (3, 4) = 9, T (3, 5) = 6, T (3, 6) = 6, T (3, 7) = 0, T (3, 8) = 1 .

For n = 4, we have

T (4, 2) = 1, T (4, 3) = 14, T (4, 4) = 43, T (4, 5) = 60, T (4, 6) = 72, T (4, 7) = 54
T (4, 8) = 54 , T (4, 9) = 20, T (4, 10) = 24, T (4, 11) = 0, T (4, 12) = 12, T (4, 16) = 1
T (4, k) = 0 for 12 < k < 16.

So, T (4) = 355.

4 Remarks and questions

There are some interesting questions related to the sequence T (n, k): where its maximum is reached? Perhaps it is near n + k_{0}, where k_{0} is the integer which maximizes the Stirling numbers of the second kind. Is it true that T (n, k) ≠ 0, for 2 ≤ k ≤ 2^{n−2}. It is easy to prove that T (n, k) ≠ 0, for 2 ≤ k ≤ 2n.

5 Acknowledgments

My sincere thanks to Prof. Y. Attic, for his kind help in drawing the graphs in this paper. I also thank the anonymous referee for his/her helpful comments.

References

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

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

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

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

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

2000 Mathematics Subject Classification: Primary 11B73; Secondary 11B65. Keywords: Labeled topology, Stirling number .

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

Received August 29 2005; revised version received May 20 2006. Published in Journal of Integer Sequences, May 24 2006.

Return to Journal of Integer Sequences home page.