Finite Topologies and Partitions

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

                     benoumhani@yahoo.com
                      kmessaud@kku.edu.sa

Abstract

Let E be a set with n elements, and let T (n, k) be the number of all labeled topologies having k open sets that can be defined on E. In this paper, we compute these numbers for k ≤ 17, and arbitrary n, as well as t_{N0}(n, k), the number of all unlabeled non-T_{0} topologies on E with k open sets, for 3 ≤ k ≤ 8.

1 Introduction

Let E be an n-element set, and let T (n) be the total number of labeled topologies one can define on E. Using the one-to-one correspondence between finite topologies and idempotent 0–1-matrices with 1 in the diagonal (see Krishnamurty [17]), it is possible to establish explicit formulae for T (n) (see Erné [7]), but they are too complex for a numerical evaluation in reasonable time, even on a modern computer. Comtet [5], Evans et al. [11], Renteln [19] and others reduced the computation of the numbers T (n) to that of the numbers γ_{n} of labeled acyclic transitive graphs, in other words, of partially ordered sets with n points. These numbers are connected via the formula T (n) = ∑_{l=1}^{n} S_{n,l}γ_{l}, where the S_{n,l} are the Stirling numbers of the second kind. That formula is evident in view of the one-to-one correspondence between quasiorders and topologies, respectively, between partial orders and T_{0}-topologies, observed by Alexandrov [1] already in the 1930’s, and pursued later by many authors (see, e.g., [2, 3, 7, 8, 9, 10, 14]). Consequently, γ_{n} is simultaneously the number T_{0}(n) of all T_{0}-topologies on n points. Combining the above formula with computer methods, Evans et al. obtained the numbers T (n) for n ≤ 7 in 1966; using suitable combinatorial identities, Erné computed T_{0}(n) and T (n) for n ≤ 8 in 1970 and for n ≤ 9 in 1972 (see [7]). Later the calculations were pushed forward, via sophisticated computer techniques, by Das [6], Stege [24], Heitzig and Reinhold [14], and finally by Brinkmann and McKay [3, 4] until n = 18.

We shall use a refinement of the above formula involving the Stirling numbers, due to Erné (see [7, 8], saying that for any property p of topologies that is invariant under lattice isomorphisms, the number T^{p}(n) of all topologies on n points with property p is obtained from the corresponding numbers T_{0}^{p}(n) of T_{0}-topologies by the identity T^{p}(n) = ∑_{l=1}^{n} S_{n,l}T_{0}^{p}(l). For example, this applies to the numbers T (n, k) of all topologies on n points having exactly k open sets, or even more specifically, to the numbers T_{a}(n, k) of all such topologies with exactly a atoms, i.e., minimal (nonempty) open sets. Alternatively, T (n, k) is the number of all quasiordered sets with k downsets or antichains, respectively. Sharp [21] and Stephen [25] showed that the maximal size of non-discrete topologies on E is 3 · 2^{n−2}. Stanley [23] enumerated all labeled topologies on E with k ≥ 7 · 2^{n−4} open sets, and Kolli [16] extended the range to k ≥ 6 · 2^{n−4}. Erné and Stege [9, 10] determined T_{0}(n, k) and T (n, k) for n ≤ 12 and, using these numbers, T_{0}(n) and T (n) for n ≤ 14. In their paper [10], using another approach via an elegant combinatorial identity, they obtained formulae for T_{0}(n, n + k + 1) and k ≤ min{n, 12}. Combining the results of the two papers [9] and [10], one could compute T_{0}(n, k) and T (n, k) for n ≤ 12 and k ≤ 25, but not for all larger values. Independently, Benoumhani [2] computed by a direct method, for all n, the number of labeled topologies with k ≤ 12 open sets, and gave alternate proofs of some known facts in the field. The enumeration of unlabeled (T_{0}) topologies seems to be an even more difficult task. For an early approach, see Knopfmacher [15], and for later more extensive calculations, [3, 4, 9, 10, 14].

The results in this paper are presented as follows: in Section 2, we continue the calculation of T (n, k). The method used is one that was developed in [16]. The tedious calculations in Section 2 illustrate how hard it is to determine, for instance, T_{0}(10, n). In Section 3, we compute the number of unlabeled non-T_{0} topologies with k ≤ 8 open sets, thereby extending the work of Stanley [23]. In the two main results, the presence of the sequences related to partitions of sets or numbers, respectively, is evident: labeled topologies create set partitions (induced by the equivalence relation identifying points with the same closure), and as the elements of the blocks are distinguishable in that case, the Stirling numbers of the second kind are involved. When counted up to homeomorphism, finite topologies are related, in a similar way, to partitions of integers, because in that case, only the number of elements in the single blocks is relevant. This explains the appearance of the numbers of partitions of the integer n in the corresponding formulae.

2 Computation of T (n, k), k ≤ 17

The following (known) properties of Stirling numbers of the second kind will be needed in Example 4. We put them in Lemma 1. For all n, and 1 ≤ k ≤ n − 1, the following relations hold

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

∑_{l=1}^{n−1} \binom{n}{l}S_{l,k}S_{n−l,m} = \binom{m + k}{k}S_{n,k+m}.

For a proof of this result, and other properties concerning Stirling numbers, see [13].

For the sake of brevity, we recall the definition of an ideal in a topology T (this is the definition of an ideal in a poset).

Definition 2. Let T be a topology on E. The set A ⊂ T is called an ideal if it satisfies

∀A, B ∈ A, ∀O ∈ T , A ∪ B ∈ A, and A ∩ O ∈ A.

From [16] recall the definition of a minimal open set.

Definition 3. The element A ∈ T is called a minimal open set if for all O in T , we have

A ∩ O ∈ {∅, A}.

Using the lattice theoretic terminology, a minimal open set is in fact an element covering the least element that is, an atom.

We designate by T_{a}(n, k) the set of all labeled topologies, having k open sets, and a minimal open sets, T (n, k) the set of all topologies on E having k open sets. Let T_{a}(n, k) = |T_{a}(n, k)|, and T (n, k) = |T (n, k)|. It is easy to see that

T (n, k) = ∑_{a,2^{a}≤k} T_{a}(n, k).

For a = 1, Kolli [16] proved

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

To compute the other remaining numbers T_{a}(n, k), we use the method developed in [16]: if T ∈ T_{a}(n, k), write it as

T = {∅, A_{1}, …, A_{a}, …, E},

where A_{1}, …, A_{a} are the minimal open sets of the topology T . Let A = ⋃_{i=1}^{a} A_{i}, and define the mapping

Φ(T ) = T′ = {O − A, O ∈ T }.

It is clear that T′ is a topology on E − A, having r open sets, where

k − 2^{a} + 1 ≥ r ≥ ⌈\frac{k}{2^{a−1}} ⌉ − 1.  (2)

Conversely, if T′ is in T (l, r), with l < n and r satisfies (2), we may restitute all the topologies T from T′ by determining all the possibilities of r. This means, we determine all the topologies T having k open sets and a minimal open sets, and such that Φ(T ) = T′.

Example 4. To illustrate our method, we compute T (n, 10) in all details. Using formula (1), we have

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

Now, let T = {∅, A_{1}, A_{2}, A_{3} = A_{1} ∪ A_{2}, A_{4}, …, A_{8}, E} ∈ T_{2}(n, 10), and let T′ = {O − A_{3}, O ∈ T }. This topology has r open sets, and according to (2), the only possibilities for r are 7, 6, 5, 4. Let us examine these cases one by one. For r = 7, let T′ = {∅, B_{1}, …, B_{5}, E − A_{3}}, and since a topology is stable by union, then

T = {∅, A_{1}, A_{2}, A_{3} = A_{1} ∪ A_{2}, A_{4} = B_{1} ∪ A_{3}, …, A_{8} = B_{5} ∪ A_{3}, E}.

The topology T is then completely determined by T′, and the total number of such topologies is

∑_{l=1}^{n−1} \binom{n}{l}S_{l,2}T (n − l, 7).

For r = 6, let T′ = {∅, B_{1}, B_{2}, B_{3}, B_{4}, , E − A_{3}}. The topology T will be obtained as follows:

T = {∅, A_{1}, A_{2}, A_{3} = A_{1} ∪ A_{2}, A_{4} = B_{1} ∪ A_{3}, …, A_{7} = B_{4} ∪ A_{3}, X, E}.

We have to determine the form of X. Note that if {∅, B_{1}} is an ideal of T′, then we have two solutions: X = B_{1} ∪ A_{l}, l = 1, 2. So, the wanted number is

∑_{l=1}^{n−1} \binom{n}{l}S_{l,2}(2T_{1}(n − l, 6) + 4T_{2}(n − l, 6)).

For r = 5, let T′ = {∅, B_{1}, B_{2}, B_{3}, E − A_{3}}. The topology T has the form

T = {∅, A_{1}, A_{2}, A_{3} = A_{1} ∪ A_{2}, A_{4} = B_{1} ∪ A_{3}, …, A_{6} = B_{3} ∪ A_{3}, X, Y, E}.

As above, if {∅, B_{1}, B_{2}} is an ideal of T′, then we have two solutions:

(X = B_{1} ∪ A_{l}, Y = B_{2} ∪ A_{l}) l = 1, 2,

and if {∅, B_{1}}, {∅, B_{2}} are two distinct ideals of T′, then also we have two solutions:

(X = B_{1} ∪ A_{1}, Y = B_{2} ∪ A_{2}) ,

and

(X = B_{1} ∪ A_{2}, Y = B_{2} ∪ A_{1}) .

So, the wanted number of such topologies is

∑_{l=1}^{n−1} \binom{n}{l}S_{l,2}(2T_{1}(n − l, 5) + 4T_{2}(n − l, 5)).

For r = 4, T′ = {∅, B_{1}, B_{2}, E − A_{3}}, the topology T′ is either a chain or its proper open sets form a partition of the whole set (see Figure 1). We restitute T as follows:

T = {∅, A_{1}, A_{2}, A_{3} = A_{1} ∪ A_{2}, A_{4} = B_{1} ∪ A_{3}, A_{5} = B_{2} ∪ A_{3}, X, Y, Z, E}.

If T′ is a chain topology, then we have two solutions:

(X = B_{1} ∪ A_{1}, Y = B_{2} ∪ A_{1}, Z = E − A_{2}),

and

(X = B_{1} ∪ A_{2}, Y = B_{2} ∪ A_{2}, Z = E − A_{1}).

In the other case, there is no solution, and then the total number of such topologies is

2 ∑_{l=1}^{n−1} \binom{n}{l}S_{l,2}T_{1}(n − l, 4).

All these numbers added, we obtain T_{2}(n, 10). Now, we compute T_{3}(n, 10). Let

T = {∅, A_{1}, A_{2}, A_{3}, …, A_{7} = A_{1} ∪ A_{2} ∪ A_{3}, A_{8}, E} ∈ T_{3}(n, 10),

where A_{1}, A_{2}, A_{3} are its three minimal open sets. Let T′ = {O −A_{7}, O ∈ T }. This topology has r open sets with r = 3 or r = 2. For r = 3, T′ = {∅, B_{1}, E − A_{7}}, then

T = {∅, A_{1}, A_{2}, A_{3}, …, A_{7} = A_{1} ∪ A_{2} ∪ A_{3}, A_{8} = B_{1} ∪ A_{7}, E}.

The topology T is then totally determined by T′. The total number of possibilities to reconstruct T from T′ is

∑_{l=1}^{n−1} \binom{n}{l}S_{l,3}T (n − l, 3).

For r = 2, T′ = {∅, E − A_{7}}. The topology T has the form

T = {∅, A_{1}, A_{2}, A_{3}, …, A_{7} = A_{1} ∪ A_{2} ∪ A_{3}, X, E},

and the three possibilities for the open set X are:

X = E − A_{3}, or X = E − A_{2}, or X = E − A_{1}.

The number of such topologies is 3 ∑_{l=1}^{n−1} \binom{n}{l}S_{l,3}. Adding these numbers for r = 2, 3, yields T_{3}(n, 10), and then T (n, 10).

According to Erné’s result [7]:

T_{a}(n, k) = ∑_{l=1}^{n−1} T_{a,0}(l, k)S_{n,l} = ∑_{l=1}^{n−1} C_{a}(l, k)l!S_{n,l}.

This means that the numbers T_{a}(n, k) are linear combinations of the (l!S_{n,l})_{l=1}^{k−1}. So, we only have to determine the coefficients C_{a}(l, k). This is done in the following tables for 10 ≤ k ≤ 17. Note that we omitted the easy computations for k ≤ 9.

C_{a}(l, 10).

l = 4 l = 5 l = 6 l = 7 l = 8 l = 9
a = 1 0  \frac{5}{6}  5  \frac{11}{2}  3  1
a = 2 \frac{1}{2}  \frac{9}{2}  \frac{33}{8}  2  \frac{1}{2}  0
a = 3 \frac{1}{2}  \frac{1}{6}  0  0  0  0

C_{a}(l, 11).

l = 5 l = 6 l = 7 l = 8 l = 9 l = 10
a = 1 1  \frac{11}{2}  \frac{73}{8}  \frac{15}{2}  \frac{7}{2}  1
a = 2 \frac{31}{12}  \frac{15}{2}  \frac{43}{8}  \frac{9}{4}  \frac{1}{2}  0
a = 3 \frac{7}{12}  \frac{1}{6}  0  0  0  0

C_{a}(l, 12).

l = 4 l = 5 l = 6 l = 7 l = 8 l = 9 l = 10 l = 11
a = 1 0  0  \frac{25}{6}  \frac{79}{6}  \frac{29}{2}  \frac{39}{4}  4  1
a = 2 0  \frac{7}{2}  \frac{67}{6}  \frac{45}{4}  \frac{27}{4}  \frac{5}{2}  \frac{1}{2}  0
a = 3 \frac{1}{2}  1  \frac{2}{3}  \frac{1}{6}  0  0  0  0

C_{a}(l, 13).

l = 5 l = 6 l = 7 l = 8 l = 9 l = 10 l = 11 l = 12
a = 1 \frac{1}{2}  \frac{9}{2}  16 \frac{295}{12} \frac{85}{4}  \frac{49}{4}  \frac{9}{2}  1
a = 2 \frac{1}{2}  \frac{125}{12} \frac{79}{4} \frac{253}{16} \frac{33}{4}  \frac{11}{4}  \frac{1}{2}  0
a = 3 1  \frac{17}{12}  \frac{3}{4}  \frac{1}{6}  0  0  0  0

C_{a}(l, 14).

l = 5 l = 6 l = 7 l = 8 l = 9 l = 10 l = 11 l = 12 l = 13
a = 1 0  2  \frac{49}{3}  \frac{73}{2} \frac{649}{16}  \frac{59}{2}  15  5  1
a = 2 \frac{3}{2}  13 \frac{365}{12} \frac{94}{3}  \frac{85}{4}  \frac{79}{8}  3  \frac{1}{2}  0
a = 3 \frac{7}{4}  3  \frac{15}{8}  \frac{5}{6}  \frac{1}{6}  0  0  0  0

C_{a}(l, 15).

l = 5 l = 6 l = 7 l = 8 l = 9 l = 10 l = 11 l = 12 l = 13 l = 14
a = 1 0  \frac{13}{4}  18 \frac{389}{8} \frac{206}{3} \frac{2975}{48} \frac{315}{8}  18  \frac{11}{2}  1
a = 2 \frac{1}{2}  \frac{33}{4} \frac{209}{6} \frac{439}{8} \frac{557}{12} \frac{221}{8}  \frac{93}{8}  \frac{13}{4}  \frac{1}{2}  0
a = 3 \frac{1}{2}  \frac{127}{36} \frac{13}{3}  \frac{19}{8}  \frac{11}{12}  \frac{1}{6}  0  0  0  0

C_{a}(l, 16).

l = 4 l = 5 l = 6 l = 7 l = 8 l = 9 l = 10 l = 11 l = 12 l = 13 l = 14 l = 15
a = 1 0  0  1  \frac{541}{36} \frac{343}{6} \frac{847}{8} 116 \frac{4309}{48}  51  \frac{85}{4}  6  1
a = 2 0  0  \frac{41}{4} \frac{139}{3} \frac{685}{8} \frac{2155}{24} \frac{2097}{32}  35  \frac{27}{2}  \frac{7}{2}  \frac{1}{2}  0
a = 3 0  \frac{3}{2}  \frac{23}{4} \frac{293}{36} \frac{143}{24} \frac{35}{12}  1  \frac{1}{6}  0  0  0  0
a = 4 \frac{1}{24}  0  0  0  0  0  0  0  0  0  0  0

C_{a}(l, 17).
l = 5 l = 6 l = 7 l = 8 l = 9 l = 10 l = 11 l = 12 l = 13 l = 14 l = 15 l = 16
a = 1 \frac{1}{24}  \frac{3}{2}  17 \frac{139}{2} \frac{595}{4} \frac{2383}{12} \frac{5841}{32} \frac{1999}{16} \frac{129}{2}  \frac{99}{4}  \frac{13}{2}  1
a = 2 0  \frac{11}{2} \frac{1013}{24} \frac{677}{6} \frac{2503}{16} \frac{413}{3} \frac{8567}{96} \frac{695}{16}  \frac{31}{2}  \frac{15}{4}  \frac{1}{2}  0
a = 3 0  \frac{9}{2}  \frac{91}{8} \frac{149}{12} \frac{379}{48}  \frac{7}{2}  \frac{13}{12}  \frac{1}{6}  0  0  0  0
a = 4 \frac{1}{24}  0  0  0  0  0  0  0  0  0  0  0

3 Unlabeled topologies for small k

In this section, we investigate the number of unlabeled topologies, with k ≤ 8 open sets, denoted by t_{N0}(n, k). Note that a T_{0}− topology must satisfy k > n, and since these topologies are calculated for n ≥ k, they are all non-T_{0}. We have the

Theorem 5. For n ≥ k, the numbers t_{N0}(n, k) satisfy the following identities:

t_{N0}(n, 2) = 1
t_{N0}(n, 3) = n − 1
t_{N0}(n, 4) = \frac{2n^{2} − 4n + 3}{4} + \frac{(−1)^{n}}{4}
t_{N0}(n, 5) = \frac{2n^{3} − 6n^{2} + 10n − 9}{12} − \frac{(−1)^{n}}{4}
t_{N0}(n, 6) = \frac{2n^{4} − 8n^{3} + 40n^{2} − 112n + 87}{48} + (−1)^{n} \frac{3}{16}
t_{N0}(n, 7) = \frac{2n^{5} − 10n^{4} + 100n^{3} − 560n^{2} + 1113n − 675}{240} + (−1)^{n} \frac{(n − 3)}{16}
t_{N0}(n, 8) = \frac{4n^{6} − 24n^{5} + 400n^{4} − 2820n^{3} + 8056n^{2} − 10386n + 5130}{2880} − (−1)^{n} \frac{(3n − 7)}{32} + \{\frac{n^{2}}{12}\}

Note that the number of partitions of n in to 2 and 3 summands, P (n, 2), P (n, 3) are given by P (n, 2) = ⌊\frac{n}{2}⌋ , P (n, 3) = \{\frac{n^{2}}{12} \}, where \{x\} is the nearest integer to x.

The proof of the previous theorem is based on the following lemma:

Lemma 6. We have

∑_{k=2}^{n−1} ⌊\frac{k}{2}⌋ = ⌊\frac{n}{2}⌋ ⌊\frac{n − 1}{2}⌋ = ⌊\frac{n}{2}⌋ (⌊\frac{n}{2}⌋ − \frac{(−1)^{n} + 1}{2})

∑_{k=2}^{n−2} k ⌊\frac{k}{2}⌋ = \frac{1}{12} ⌊\frac{n − 1}{2}⌋ (4n^{2} − (15 − 2(−1)^{n})n + 12 + \frac{3}{2}(1 − (−1)^{n}))

∑_{k=2}^{n−2} ⌊\frac{k}{2}⌋^{2} = \frac{(n − 2)}{4} (\frac{(n − 1)(n − 3)}{3} + \frac{(1 + (−1)^{n}}{2} )

∑_{k=2}^{n−2} ⌊\frac{k}{2}⌋ ⌊−\frac{k − 1}{2}⌋ = − ∑_{k=2}^{n−2} ⌊\frac{k}{2}⌋^{2} = −\frac{(n − 2)}{4} (\frac{(n − 1)(n − 3)}{3} + \frac{1 + (−1)^{n}}{2} )

∑_{k=3}^{n−1} ⌊\frac{k}{2}⌋ ⌊\frac{k − 1}{2}⌋ = ⌊\frac{n}{2}⌋ ⌊\frac{n − 2}{2}⌋ (\frac{2n − 5}{6} + \frac{(1 − (−1)^{n})}{3})

∑_{k=4}^{n−1} k ⌊\frac{k}{2}⌋ ⌊\frac{k − 2}{2}⌋ = \frac{1}{4} ⌊\frac{n}{2}⌋ ⌊\frac{n − 3}{2}⌋ (n^{2} − 2n + \frac{(1 − (−1)^{n})}{2})

∑_{k=4}^{n−1}(−1)^{k−1} ⌊\frac{k}{2}⌋ ⌊\frac{k − 2}{2}⌋ = −\frac{(n − 1)(n − 3)}{8}(1 − (−1)^{n})

Proof. First, note that

⌊\frac{k}{2}⌋ = \frac{2k − 1 + (−1)^{k}}{4}
⌊−\frac{k}{2}⌋ = − ⌊\frac{k}{2}⌋ − \frac{1 − (−1)^{k}}{2}
⌊\frac{k − 1}{2}⌋ = ⌊\frac{k}{2}⌋ − \frac{(−1)^{k} + 1}{2}.

So, the second formula of the lemma is

∑_{k=2}^{n−2} k ⌊\frac{k}{2}⌋ = ∑_{k=2}^{n−2} k (\frac{2k − 1 + (−1)^{k}}{4} ) .

Using the known summations ∑_{k}^{l} k^{j} and ∑_{k}^{l}(−1)^{k}k^{j}, we obtain

∑_{k=2}^{n−2} k ⌊\frac{k}{2}⌋ = ∑_{k=2}^{n−2} k (\frac{2k − 1 + (−1)^{k}}{4} )

= \frac{n^{3}}{6} − \frac{7n^{2}}{8} + \frac{35n}{24} − \frac{13}{16} − \frac{(−1)^{n−1}n}{8} + \frac{3(−1)^{n−1}}{16} .

This may be written

∑_{k=2}^{n−2} k ⌊\frac{k}{2}⌋ = \begin{cases}\frac{(n−2)(4n^{2}−13n+12)}{24}, if n = 2l; \\ \frac{(4n−5)(n−1)(n−3)}{24}, if n = 2l + 1. \end{cases}

In a more compact formula, the previous summation becomes

∑_{k=2}^{n−2} k ⌊\frac{k}{2}⌋ = \frac{1}{12} ⌊\frac{n − 1}{2}⌋ (4n^{2} − (15 − 2(−1)^{n})n + 12 + \frac{3}{2}(1 − (−1)^{n}))

For the fourth one, using the observations in the beginning of the proof, we obtain

∑_{k=2}^{n−2} ⌊\frac{k}{2}⌋ ⌊−\frac{k − 1}{2}⌋ = − ∑_{k=2}^{n−2} ⌊\frac{k}{2}⌋^{2} .

But

∑_{k=2}^{n−2} ⌊\frac{k}{2}⌋^{2} = ∑_{k=2}^{n−2} (\frac{2k − 1 + (−1)^{k}}{4} )^{2}

= \frac{(n − 2)}{4} (\frac{(n − 1)(n − 3)}{3} + \frac{(1 + (−1)^{n}}{2} ) .

The remaining cases are proved similarly.

Proof of Theorem 5.

Proof. Before starting the proof, we point out the following easy but important facts:

1) Two finite topologies are homeomorphic if and only if, as a poset, they have the same Hasse diagram and all the corresponding open sets have the same cardinality.

2) The number of unlabeled non-T_{0} chain topologies having k nontrivial open sets (i.e.; open sets different from ϕ and E) is \binom{n−1}{k}. This is also, the number of strictly increasing sequences having k terms, taken from a set of n integers. For the sake of simplicity and shortness, we performed the calculations using the floor brackets. The computations of t_{N0}(n, k) will be the same as in [2]: We list all the possible forms, and then count them. Calculation of t_{N0}(n, 3) is easily obtained: those are chains with three elements, their number is \binom{n−1}{1}. For t_{N0}(n, 4), we have two kinds of topologies: chains with 4 open sets and topologies having the form below

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

For the first one the number is \binom{n−1}{2}. In the second case, the total number of different non-T_{0} topologies is ⌊\frac{n}{2}⌋ , (this is also the number of partitions of n into exactly 2 summands; P (n, 2)). Furthermore

t_{N0}(n, 4) = \binom{n − 1}{2} + ⌊\frac{n}{2}⌋ = \binom{n − 1}{2} + P (n, 2) = \frac{2n^{2} − 4n + 3}{4} + \frac{(−1)^{n}}{4} .

For t_{N0}(n, 5), there are 3 forms: Chains and topologies having one of the two last forms as indicated in the figure below (note that the two last diagrams have the same number).

[figure: •; •; ∅; •; •; •; E; •; •; •; E; •; ∅; •; •; •; •; •; ∅; E; •; Figure 2]

For the chains, their number is \binom{n−1}{3}. For the remaining cases the number is counted as follows: take 2 ≤ k ≤ n − 1, and then partition into 2 parts, to obtain a topology of four open sets on a set of cardinality k. To obtain a topology on E, add the whole set E. The number of ways to do that is

∑_{k=2}^{n−1} ⌊\frac{k}{2}⌋ .

The previous number is counted twice because of the symmetry of the cases. By Lemma 6, this gives

2 ∑_{k=2}^{n−1} ⌊\frac{k}{2}⌋ = 2 ⌊\frac{n}{2}⌋ (2 ⌊\frac{n}{2}⌋ − (−1)^{n} − 1) = 2 ⌊\frac{n}{2}⌋ ⌊\frac{n − 1}{2}⌋

Thus, the total number in this case is

t_{N0}(n, 5) = \binom{n − 1}{3} + 2 ⌊\frac{n}{2}⌋ ⌊\frac{n − 1}{2}⌋
= \binom{n − 1}{3} + \frac{2n^{2} − 4n + 1}{4} − \frac{(−1)^{n}}{4}
= \frac{2n^{3} − 6n^{2} + 10n − 9}{12} − \frac{(−1)^{n}}{4}

For t_{N0}(n, 6), the forms are illustrated below

[figure: •; •; •; ∅; •; •; •; E; •; •; •; E; •; ∅; •; •; •; •; •; •; ∅; E; •; •]

[figure: •; •; A; •; •; E; •; ∅; •; •; •; A; •; C; •; B; E; D; •; ∅; •; Figure 3]

The number of chain topologies is \binom{n−1}{4}. The number of topologies corresponding to the next three graphs is counted as follows. Take 3 ≤ k ≤ n − 1, there are

\frac{1}{2} ⌊\frac{k}{2}⌋ (2 ⌊\frac{k}{2}⌋ − (−1)^{k} − 1) = ⌊\frac{k}{2}⌋ ⌊\frac{k − 1}{2}⌋

non-T_{0} topologies with 5 open sets, on a k-element set, having the second (or the third) form in Figure 2. A topology of the wanted form is obtained by adjoining the whole set E. This sum has to be taken three times. So, the wanted number is

3 ∑_{k=3}^{n−1} ⌊\frac{k}{2}⌋ ⌊\frac{k − 1}{2}⌋

using the fifth formula in Lemma 6, we obtain

3 ∑_{k=3}^{n−1} ⌊\frac{k}{2}⌋ ⌊\frac{k − 1}{2}⌋ = 3 ⌊\frac{n}{2}⌋ ⌊\frac{n − 2}{2}⌋ (\frac{2n − 5}{6} + \frac{(1 − (−1)^{n})}{3})

= \frac{1}{2} ⌊\frac{n}{2}⌋ ⌊\frac{n − 2}{2}⌋ (2n − 2(−1)^{n} − 3) .

For the number of topologies corresponding to the last graph in Figure 3, let 2 ≤ k = |C| ≤ n − 1. Partition it into two parts, k = l + j, |A| = l, |B| = j. To each partition of k, it corresponds two different topologies: τ_{1} = {ϕ, A_{1}, B_{1}, C, D_{1}, E}, |A_{1}| = l, |B_{1}| = j, |D_{1}| = n − k + j and τ_{2} = {ϕ, A_{2}, B_{2}, C, D_{2}, E}, |A_{2}| = j, |B_{2}| = l, |D_{2}| = n − k + l, unless l = j, in this case we have only one topology. So, the number of topologies corresponding to k is

α_{k} = \begin{cases}2 ⌊\frac{k}{2}⌋ , if k = 2l + 1; \\ 2 ⌊\frac{k}{2}⌋ − 1, if k = 2l. \end{cases}

The wanted number is ∑_{k=2}^{n−1} α_{k} = 1 + 2 + 3 + ⋯ + n − 2 = \binom{n − 1}{2}.

Finally, summing and replacing ⌊\frac{l}{2}⌋ by \frac{2l − 1 + (−1)^{l}}{4} , and the binomial coefficients by

their values we obtain

t_{N0}(n, 6) = \binom{n − 1}{4} + \binom{n − 1}{2} + \frac{1}{2} ⌊\frac{n}{2}⌋ ⌊\frac{n − 2}{2}⌋ (2n − 2(−1)^{n} − 3)
= \binom{n − 1}{4} + \binom{n − 1}{2} + \frac{4n^{3} − 18n^{2} + 20n − 3}{16} + (−1)^{n} \frac{3}{16}
= \frac{2n^{4} − 8n^{3} + 40n^{2} − 112n + 87}{48} + (−1)^{n} \frac{3}{16}

For t_{N0}(n, 7)), we have \binom{n−1}{4}) chain topologies. Insert the graph in Figure 1 into a chain of 4 elements (the number is counted 4 times): this gives the number

4 ∑_{k=2}^{n−3} \binom{n − k − 1}{2} ⌊\frac{k}{2}⌋ .

By Lemma 6, this number is

4 ∑_{k=2}^{n−3} \binom{n − k − 1}{2} ⌊\frac{k}{2}⌋ = 2 ∑_{k=2}^{n−3}(n − k − 1)(n − k − 2) ⌊\frac{k}{2}⌋

= 2(n^{2} − 3n + 2) ∑_{k=2}^{n−3} ⌊\frac{k}{2}⌋ − 2(n − 3) ∑_{k=2}^{n−3} ⌊\frac{k}{2}⌋ + 2 ∑_{k=2}^{n−3}(k^{2} + k) ⌊\frac{k}{2}⌋ .

= \frac{1}{3} ⌊\frac{n}{2}⌋ ⌊\frac{n − 2}{2}⌋ (n^{2} − 4n − (1 + (−1)^{n})(n − 4) + \frac{1 − (−1)^{n}}{2} )

Again, replacing ⌊\frac{l}{2}⌋ by its value, we obtain

\frac{1}{3} ⌊\frac{n}{2}⌋ ⌊\frac{n − 2}{2}⌋ (n^{2} − 4n − (1 + (−1)^{n})(n − 4) + \frac{1 − (−1)^{n}}{2} ) = \frac{4n^{4} − 32n^{3} + 80n^{2} − 64n + 6}{48}−\frac{1}{8}(−1)^{n}

The number corresponding to the graph below is is evaluated as follows:

[figure: •; •; •; •; •; •; •; Figure 4]

Take a subset of cardinality 2 ≤ k ≤ n − 2, then partition it into two parts, this is done by ⌊\frac{k}{2}⌋ and then put over it two subsets containing it, such that their union is the whole set, this can be done by ⌊\frac{n−k}{2}⌋, so the wanted number is

∑_{k=2}^{n−2} ⌊\frac{k}{2}⌋ ⌊\frac{n − k}{2} ⌋ = ⌊\frac{n}{2}⌋ ⌊\frac{n − 2}{2}⌋ \frac{(n − (−1)^{n})}{6}

= \frac{2n^{3} − 6n^{2} + n + 3}{48} + \frac{3(n − 1)}{48}(−1)^{n}

The number corresponding to the last case in t_{N0}(n, 6), with a least or a greatest element is (this is counted twice):

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

Summing all these numbers, we obtain t_{N0}(n, 7) as claimed.

For t_{N0}(n, 8), we have six forms: chains (\binom{n−1}{6}). Topologies such that their diagram is formed by three copies of the graph in Figure 1. Their number is 2\binom{n−1}{3}. Topologies in the figure corresponding to the last case in t_{N0}(n, 6), with a least and a greatest element added (counted three times) is 3\binom{n−1}{3}. The number of different and non homeomorphic topologies corresponding to the graph below, is counted as follows:

[figure: •; •; •; •; •; •; •; •; Figure 5]

The number of topologies with 7 open sets on a set of k > 3 elements, having the form in Figure 4, is

⌊\frac{k}{2}⌋ ⌊\frac{k − 2}{2}⌋ \frac{(k − (−1)^{k})}{6}.

In order to obtain a topology on E, with 8 open sets, we adjoin the whole set. Thus, the number is

∑_{k=4}^{n−1} ⌊\frac{k}{2}⌋ ⌊\frac{k − 2}{2}⌋ \frac{(k − (−1)^{k})}{6}.

The last sum is counted three times. We obtain

3 ∑_{k=4}^{n−1} ⌊\frac{k}{2}⌋ ⌊\frac{k − 2}{2}⌋ \frac{(k − (−1)^{k})}{6} = \frac{1}{2} ⌊\frac{n}{2}⌋ ⌊\frac{n − 2}{2}⌋ ⌊\frac{n − 3}{2}⌋ (\frac{n}{2} + \frac{(1 − (−1)^{n})}{4})

= \frac{2n^{4} − 12n^{3} + 16n^{2} + 6n − 9}{64} − \frac{3(2n − 3)}{64}(−1)^{n}.

Topologies formed by a chain and a copy of the graph in Figure 1 (a chain with four elements over the graph). These topologies are counted 5 times. This is counted as follows: For each 2 ≤ k ≤ n − 4, we may construct

\binom{n − k − 1}{3} ⌊\frac{k}{2}⌋

different topologies. Using the summation formulas of Lemma 6, the total number is

5 ∑_{k=2}^{n−4} \binom{n − k − 1}{3} ⌊\frac{k}{2}⌋ = \frac{1}{12} ⌊\frac{n}{2}⌋ ⌊\frac{n − 2}{2}⌋ ⌊\frac{n − 4}{2}⌋ (2n^{2} − (10 + 3(−1)^{n})n + 1 + \frac{15}{2}(1 + (−1)^{n}))

= \frac{4n^{5} − 50n^{4} + 220n^{3} − 400n^{2} + 256n − 15}{192} + \frac{15}{192}(−1)^{n}

The number of topologies corresponding to the boolean algebra (the figure below) is P (n, 3), the number of partitions of the integer n into 3 summands. Summing all these quantities, we obtain the desired formula.

[figure: •; •; •; •; •; •; •; •] Figure 6

4 Conclusion

In the first part of this paper, we computed T (n, k) for every n and k ≤ 17. Our method does not use the powerful tool of poset theory. It is somewhat direct and rests heavily on some elementary and simple diophantine equations. Calculations may be pushed till a reasonable range of k, (k ≤ 30 for example), and if refined, we may go far beyond this range.

In the second part of the paper, we encounter a difficulty to compute the numbers t_{N0}(n, k), since there is no method to deal with them, and there is no analogous formula, as for T_{0}(n, k). Here too, we may reach the range of k = 10 or k = 11. This is the project of a forthcoming paper.

5 Acknowledgement

We are very indebted to the anonymous referee for her (his) careful reading of the manuscript, corrections, valuable suggestions and comments which greatly improved the paper.

References

[1] P. S. Alexandrov, Diskrete Räume. Mat. Sb. (N.S.) 2 (1937), 501–518.

[2] M. Benoumhani, The number of topologies on a finite set, J. Integer Seq. 9 (2006), Article 06.2.6.

[3] G. Brinkmann and B. B. D. McKay, Posets on up to 16 points, Order 19 (2002), 147– 179.

[4] G. Brinkmann and B. D. McKay, Counting unlabelled topologies and transitive relations, J. Integer Sequences 8 (2005), Article 05.2.1.

[5] L. Comtet, Recouvrements, bases de filtre et topologies d’un ensemble fini. Compt. Rend. Acad. Sci. Paris 262 (1966), A 1091–1094.

[6] S. K. Das, A machine representation of finite T_{0} topologies. J. ACM 24 (1977), 676–692.

[7] M. Erné, Struktur-und Anzahlformeln für Topologien auf endlichen Mengen. Ph. D. Diss., University of Hannover, 1972. Manuscripta Math. 11 (1974), 221–259.

[8] M. Erné, On the cardinalities of finite topologies and the Number of antichains in partially ordered Sets, Discrete Math., 35 (1981), 113–133.

[9] M. Erné and K. Stege, Counting finite posets and topologies, Order 8 (1991), 247– 265. Extended version and numerical tables in: Technical Report 236 , Institute of Mathematics, University of Hannover, 1990.

[10] M. Erné and K. Stege, Combinatorial applications of ordinal sum decompositions, Ars Combinatoria 40 (1995), 65–88.

[11] J. W. Evans, F. Harary, and M. S. Lynn, On the computer enumeration of finite topologies, Comm. ACM. 10 (1967), 295–297.

[12] S. Finch, Transitive relations, topologies and partial orders, (2003), published electron-

    ically at http://algo.inria.fr/csolve/posets.pdf.

[13] Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics, Addison-Wesley, 1994.

[14] J. Heitzig and J. Reinhold, The number of unlabeled orders on fourteen elements. Order 17 (2000), 333–341.

[15] J. Knopfmacher, Note on finite topological spaces. J. Austral. Math. Soc. 9 (1969), 252–256.

[16] M. Kolli, Direct and elementary approach to enumerate topologies on finite set, J. Integer Seq. 10 (2007), Article 07.3.1.

[17] V. Krishnamurthy, On the number of topologies on a finite set, Amer. Math. Monthly, 73 (1966), 154–157.

[18] G. Pfeiffer, Counting transitive relations, J. Integer Sequences 7 (2004), Article 04.3.2.

[19] P. Renteln, On the enumeration of finite topologies, Journal of Combinatorics, Information System Sciences 19 (1994), 201–206.

[20] H. Sharp, Jr., Quasi-orderings and topologies on finite set, Proc. Amer. Math. Soc. 17 (1966), 1344–1349.

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

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

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

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

[24] K. Stege, Kombinatorische Anzahlbestimmungen Für Quasiordnungen und Topologien. Diploma thesis, University of Hannover, 1990.

[25] 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}, \underline{A008277}, and \underline{A122934}.)

Received September 11 2007; revised versions received October 18 2007; July 7 2009; January 19 2010; March 6 2010. Published in Journal of Integer Sequences, March 10 2010. Minor revision, March 18 2010.

Return to Journal of Integer Sequences home page.