\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf 
The Number of Topologies on a Finite Set}
\vskip 1cm
\large
Moussa Benoumhani\\
Faculty of Science\\
Department of Mathematics\\
Sana'a University \\
P.O. Box 14026 \\
Sana'a \\
Yemen \\
\href{mailto:benoumhani@yahoo.com}{\tt benoumhani@yahoo.com} \\
\end{center}

\vskip .2 in
\begin{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 \leq k\leq 12$,  as well as other results
concerning  $T_0$ topologies on $X$ having  $n+4\leq k \leq n+6$
open sets.
\end{abstract}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section] 


%\documentclass{article}
%\usepackage{amssymb}

\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{rem}[thm]{Remark}
\newcommand{\eps}{\varepsilon}
\newcommand{\To}{\longrightarrow}
\newcommand{\h}{\mathcal{H}}
\newcommand{\s}{\mathcal{S}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\J}{\mathcal{J}}
\newcommand{\M}{\mathcal{M}}
\newcommand{\W}{\mathcal{W}}
\newcommand{\X}{\mathcal{X}}
\newcommand{\BOP}{\mathbf{B}}
\newcommand{\BH}{\mathbf{B}(\mathcal{H})}
\newcommand{\KH}{\mathcal{K}(\mathcal{H})}
\newcommand{\Real}{\mathbb{R}}
\newcommand{\Complex}{\mathbb{C}}
\newcommand{\Field}{\mathbb{F}}
\newcommand{\RPlus}{\Real^{+}}
\newcommand{\Polar}{\mathcal{P}_{\s}}
\newcommand{\Poly}{\mathcal{P}(E)}
\newcommand{\EssD}{\mathcal{D}}
\newcommand{\Lom}{\mathcal{L}}
\newcommand{\States}{\mathcal{T}}
\newcommand{\abs}[1]{\left\vert#1\right\vert}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\seq}[1]{\left<#1\right>}
\newcommand{\norm}[1]{\left\Vert#1\right\Vert}
\newcommand{\essnorm}[1]{\norm{#1}_{\ess}}
%\input{tcilatex}
\renewcommand{\proof}{\par\medskip\noindent\textbf{Proof.\ }}
\newcommand{\eproof}{\ \ \raisebox{0pt}{$\blacksquare$}}%\par \hfill
\renewcommand{\binom}[2]{\left({{#1}\atop {#2}}\right)}
%\textwidth=15truecm \textheight=24truecm \voffset=-1truecm \hoffset=-1truecm
%\begin{document}


\section{Introduction}

Recall that a topology $\tau $ on the set $X\neq \phi $ is a
subset of $ P(X) $ that contains $\phi $ and $X$, and is closed
under union and finite intersection. A topology on $X$ is a
sublattice of $(P(X),\subseteq)$ with the maximum element $X,$
denoted by $1$, and the minimum element, which is $\phi $, 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 {\it 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 {\it partial order}. The subset $A \subset X$ of the
preordered set $X$ is called an {\it ideal} if $x\in A$ and $y\leq x$
implies $y \in 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\geq 4,$ the calculations are complicated. The online encyclopedia of N. J.
A. Sloane \cite{Sloane} gives the value of $T(n)$ for $1\leq n\leq 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\leq k\leq 2^n$, and $T(n,k)=|t(n,k)|$. So,
$T(n)=\sum\limits_{k\geq 2}T(n,k).$ Obviously, we have
\begin{eqnarray*}
T(n,2) &=&T(n,2^n)=1 \\
T(n,3) &=&2^n-2
\end{eqnarray*}

For $k\geq 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 \cite{Stanley} computed $T(n,k)$ for large values of $
k$, viz.; $3\cdot 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\leq k\leq 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 \cite{Sharp,Stanley,Sloane}.

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

\begin{defn}
The number of partitions of a finite set with $n$ elements into $k$ blocks,
is the {\it Stirling number of the second kind}. It is denoted $S(n,k)$.
\end{defn}

The explicit, and somewhat complicated formula for Stirling numbers of the
second kind is
\begin{equation}
S(n,k)=S_{n,\,k}=\frac 1{k!}\sum\limits_{j=0}^k(-1)^j\left(
\begin{array}{c}
k \\
j
\end{array}
\right) (k-j)^n.
\end{equation}

\begin{lem}
Let $\tau$ be a topology on a finite set $X$. Then
$\tau^{c}=\{A^{c},\,A\in \tau \}$ is also a topology on $X$.
\end{lem}

\begin{rem}
The previous lemma is not necessarily true if X is infinite. Note, also, if $%
\tau$ is a topology, it may happen that $\tau=\tau^{c}.$ Take
$X=\{a,\,b,\,c\}$, and $\tau=\{\phi ,\,X,\,\{a\},\,\{b,\,c\}\}.$
\end{rem}

\begin{defn}
A {\it chain topology} on $X$, is a topology whose open sets are totally ordered
by inclusion.
\end{defn}

\section{Topologies with small number of open sets}

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

\begin{lem}
(D. Stephen) Let $C(n,k)$ be the number of chain topologies on $X$
having $k$ open sets. Then
\begin{equation}
C(n,k)=\sum\limits_{l=1}^{n-1}\binom n  l C(l,k-1)=(k-1)!S(n,k-1)
\end{equation}
\end{lem}

\begin{proof}
This proof is shorter than that in Stephen \cite{Stephen}. 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 $\phi \neq A_1\subsetneqq A_2\subsetneqq
A_3 \ldots \subsetneqq A_k\subsetneqq X$, is associated with the
partition $(B_1,\,B_{2,\,}B_{3,\,} \ldots 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,\,} \ldots B_k)$ is an ordered partition, the chain
$\phi \neq A_1\subsetneqq A_2\subsetneqq A_3 \ldots \subsetneqq
A_{k-}\subsetneqq X$, where $A_1=B_1,\,A_i=A_{i-1}\cup B_i,\,2\leq
i\leq k-1,$ is associated with the partition
$(B_1,\,B_{2,\,}B_{3,\,} \ldots 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\subseteq X,\;1\leq |A|=l\leq 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=\sum\limits_{l=1}^{n-l}\binom n  l C(l,k-1)$.
\eproof
\end{proof}

\bigskip

Now we are ready to prove our main result.

\begin{thm}
For every $\,n\geq 1$, we have
\begin{eqnarray*}
T(n,4) &=&S_{n,\,2}+3!S_{n,\,3}=3^{n}-5\cdot 2^{n-1}+2 \\
T(n,5) &=&3!S_{n,\,3}+4!S_{n,\,4}=4^{n}-3^{n+1}+3\cdot 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} \\
&&\hspace{5truecm}+\,\frac{9}{2}.10!S_{n,\,10}+11!S_{n,\,11}.
\end{eqnarray*}
\end{thm}

\begin{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
$\tau =\{\phi
,\,X,A,B\}\in \,t(n,4),$ then either $\tau $ is a chain or has the form $%
( A\cap B=\phi$  and $A\cup B=X) $.
 \unitlength=1truemm
$$
\begin{picture}(40,30)(0,-5)
\put(-0.75,-5){$\bullet$} \put(2,-5){$\emptyset$}
 \put(0,-4){\line(0,1){10}}
\put(-0.75,5){$\bullet$} \put(2,5){$A$}
 \put(0,6){\line(0,1){10}}
 \put(-0.75,15){$\bullet$}
 \put(2,15){$B$}
 \put(0,15){\line(0,1){10}}
 \put(-0.75,24.5){$\bullet$}
 \put(2,24){$X$}
 %%%
 \put(39.25,0){$\bullet$} \put(39,-4){$\emptyset$}
 \put(40,1){\line(-1,1){10}}
\put(29.25,10){$\bullet$} \put(26,10){$A$}
 \put(30,11){\line(1,1){10}}
 \put(39.25,20){$\bullet$}
 \put(39,23){$X$}
 \put(40,21){\line(1,-1){10}}
 \put(49.25,10){$\bullet$}
 \put(52,10){$B$}
\put(40,1){\line(1,1){10}}
\end{picture}
$$
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:
$$
\unitlength=1truemm
\begin{picture}(40,40)(25,-13)
\put(-.75,-15){$\bullet$}  \put(0,-14){\line(0,1){10}}
  \put(-0.75,-5){$\bullet$} \put(2,-15){$\emptyset$}
 \put(0,-4){\line(0,1){10}}
\put(-0.75,5){$\bullet$} \put(2,5){$B$}
 \put(0,6){\line(0,1){10}}
\put(2,-5){$A$}
 \put(-0.75,15){$\bullet$}
 \put(2,15){$C$}
 \put(0,15){\line(0,1){10}}
 \put(-0.75,24.5){$\bullet$}
 \put(2,25){$X$}
 %%%
 \put(39.25,0){$\bullet$}
 \put(40,1){\line(-1,1){10}}
\put(29.25,10){$\bullet$} \put(26,10){$A$}
 \put(30,11){\line(1,1){10}}
 \put(39.25,20){$\bullet$}
 \put(39,23){$X$}
 \put(40,21){\line(1,-1){10}}
 \put(49.25,10){$\bullet$}
 \put(52,10){$B$}
\put(40,1){\line(1,1){10}} \put(40,1){\line(0,-1){10}}
\put(42,0){$C$}
 \put(39,-14){$\emptyset$}
\put(39.25,-10){$\bullet$}
%%%
%%%
 \put(79.25,-10){$\bullet$}
 \put(80,-9){\line(-1,1){10}}
\put(69.25,0){$\bullet$} \put(66,0){$A$}
 \put(70,1){\line(1,1){10}}
 \put(79.25,10){$\bullet$}
 \put(82,12){$C$}
 \put(80,11){\line(1,-1){10}}
 \put(89.25,0){$\bullet$}
 \put(92,0){$B$}
\put(80,-9){\line(1,1){10}} \put(80,11){\line(0,1){10}}
 \put(79.5,-14){$\emptyset$}
 \put(79,23){$X$}
\put(79.25,20){$\bullet$}
\end{picture}
$$

1) Chain topologies with 5 open sets.

2)$\left( \phi \mbox{ }\subset C \subset B,\,\mbox{ }\phi \mbox{
}\subset C\subset A,\,A\cup B=X\right) $ or

3)$\left( \phi \mbox{ }\subset A\subset C,\,\mbox{ }\phi \mbox{ }\subset B\subset
C,\,A\cup B=C\,\subsetneq X\right) .$

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\subsetneq X$ be
such that $|C|=$ $k,\,2\leq k\leq n-1$. This is chosen in $\binom nk$%
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 :

\[
\sum\limits_{k=2}^{n-1}  \binom n k \left( 2^{k-1}-1\right)
=\frac{3^n-3\cdot 2^n+3}2=\frac{3!S(n,3)}2\cdot
\]

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\cdot 2^n-1.
\]
For $T(n,6),$ we have 5 forms, as indicated in the figure below:
\par\noindent
 \unitlength=1truemm
\begin{picture}(40,40)(-10,-10)
\put(-.75,-25){$\bullet$}
 \put(0,-24){\line(0,1){10}}
\put(-.75,-15){$\bullet$}  \put(0,-14){\line(0,1){10}}
  \put(-0.75,-5){$\bullet$} \put(2,-25){$\emptyset$}
 \put(0,-4){\line(0,1){10}}
\put(-0.75,5){$\bullet$} \put(2,-5){$B$}
 \put(0,6){\line(0,1){10}}
\put(2,-15){$A$}
 \put(-0.75,15){$\bullet$}
 \put(2, 5){$C$}
 \put(0,15){\line(0,1){10}}
 \put(-0.75,24.5){$\bullet$}
 \put(2,15){$D$}
 \put(2,25){$X$}
 %%%2
 \put(39.25,0){$\bullet$}
 \put(40,1){\line(-1,1){10}}
\put(29.25,10){$\bullet$} \put(26,10){$C$}
 \put(30,11){\line(1,1){10}}
 \put(39.25,20){$\bullet$}
 \put(39,23){$X$}
 \put(40,21){\line(1,-1){10}}
 \put(49.25,10){$\bullet$}
 \put(52,10){$B$}
\put(40,1){\line(1,1){10}} \put(40,1){\line(0,-1){10}}
 \put(42,0){$A$}
 \put(42,-10){$D$}
 \put(39,-24){$\emptyset$}
\put(40,-9){\line(0,-1){10}} \put(39.25,-10){$\bullet$}
 \put(39.25,-20){$\bullet$}
%%%3
%%%
 \put(79.25,-10){$\bullet$}
 \put(80,-9){\line(-1,1){10}}
\put(69.25,0){$\bullet$} \put(66,0){$A$}
 \put(70,1){\line(1,1){10}}
 \put(79.25,10){$\bullet$}
 \put(82,12){$C$}
 \put(80,11){\line(1,-1){10}}
 \put(89.25,0){$\bullet$}
 \put(92,0){$B$}
\put(80,-9){\line(1,1){10}} \put(80,11){\line(0,1){10}}
 \put(80,-19){\line(0,1){10}}
 \put(79.5,-24){$\emptyset$}
 \put(79,23){$X$}
\put(79.25,20){$\bullet$}
 \put(82,-11){$D$}
 \put(79.25,-20){$\bullet$}
\end{picture}
\par
 \unitlength=1truemm
\begin{picture}(40,40)(90,-30)
\put(119.25,-25){$\bullet$}
 \put(120,-24){\line(-1,1){10}}
\put(109.25,-15){$\bullet$} \put(106,-15){$A$}
 \put(110,-14){\line(1,1){10}}
 \put(119.25,-5){$\bullet$}
 \put(122,-3){$C$}
 \put(120,-4){\line(1,-1){10}}
 \put(129.25,-15){$\bullet$}
 \put(132,-15){$B$}
\put(120,-24){\line(1,1){10}}
 \put(120,-4){\line(0,1){10}}%
 \put(120,6){\line(0,1){10}}%
 \put(122,5){$D$}
 \put(122,14){$X$}
\put(119.25,5){$\bullet$}
 \put(119,-29){$\emptyset$}
 \put(119.25,15){$\bullet$}
 %%%5
 \put(159.25,-25){$\bullet$}
 \put(160,-24){\line(-1,1){10}}
 \put(179.96,-4){\line(-1,1){10}}
\put(149.25,-15){$\bullet$} \put(146,-15){$A$}
 \put(150,-14){\line(1,1){20}}
 \put(159.25,-5){$\bullet$}
 \put(157,-3){$C$}
 \put(160,-4){\line(1,-1){10}}
 \put(169.25,-15){$\bullet$}
 \put(172,-15){$B$}
\put(160,-24){\line(1,1){20}}
 %\put(160,-4){\line(0,1){10}}%
 %\put(160,6){\line(0,1){10}}%
 \put(170,8){$X$}
 \put(182,-4){$D$}
\put(169.25,5){$\bullet$}
 \put(159,-29){$\emptyset$}
 \put(179.25,-5){$\bullet$}
\end{picture}


1) Chain topologies with 6 open sets.

2)$\left( A\cap B=\mbox{ }\phi ,\,A\cup B=C,\,A\subset C,\,C\cap D=B,\,C\cup D=X\right) $

3)$\left( \phi \mbox{ }\subsetneq A_1\subsetneq A_3\subsetneq A_4\subsetneq X,\mbox{and
}\,\phi \subsetneq A_2\subsetneq A_3\subsetneq A_4\subsetneq X,A_1\cap A_2=\phi \,\right)
,\,$ and its symmetric case.

4)$\phi \subsetneq A_{1}\subsetneq A_{2}\subsetneq A_{4}\subsetneq X,$and $%
\phi \subsetneq A_{1}\subsetneq A_{3}\subsetneq A_{4}\subsetneq
X,\,A_{2}\cup 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$ $\subsetneq X,$ such that $2\leq
\left\vert C\right\vert =k\leq n-1.$ We then partition $C$ in to two blocks $%
A,B$. To each partition $(A,B)$ corresponds two topologies:
$$\left( \phi
,\,A,\,B,\,\,A\cup B=C,\,A\cup (X-B),\,X\right)
$$
and
$$
\left( \phi ,\,A,\,B,\,A\cup B=C,\,B\cup (X-A),\,X\right) . $$
 So, the total number of
topologies in this case is
\[
2\sum\limits_{k=2}^{n-1}\binom n  k \left( 2^{k-1}-1\right)
=3^{n}-3.2^{n}+3=3!S(n,3).
\]
For the third case, we choose $A_3,\,2\leq \left| A_3\right| =k\leq 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\leq n-1$. The number of these choices is  $\binom nk\binom {n-k}
iS(k,2)$. Finally the total number for the third case and its reciprocal is
$$
2\sum\limits_{k=2}^{n-2}\sum\limits_{i=1}^{n-k-1}\binom nk\binom
{n-k} i\left( 2^{k-1}-1\right) =4^n-4\cdot
3^n+3\cdot2^{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. 
\eproof
\end{proof}


\section{Topologies with large number of open sets}

The following result is due to H. Sharp \cite{Sharp} and D. Stephen \cite{Stephen}.

\begin{thm}
For $n\geq 3,\,T(n,k)=0\,\,$for $3\cdot 2^{n-2}<k<2^{n}.$
\end{thm}

Sharp \cite{Sharp} 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\cdot 2^{n-2}).$

\begin{proof}
Since we are looking for a non-discrete topology $%
\tau $ having the maximum of open sets, it must not contain all the
singletons, so, there is an $a\in X,$ such that $\{a\}$ $\notin \tau $ .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,\,
\ldots, x_k\},$
$3\leq k\leq n-2$ must be removed. Their number is $\binom{n-2}k$. Finally, the total
number of the removed sets is
$$
\sum\limits_{k=0}^{n-2}\binom{n-2}k=2^{n-2}.
$$
The remaining elements form a topology having $2^n-2^{n-2}=3\cdot
2^{n-2}$ open sets.
\eproof
\end{proof}

\bigskip

The following theorem gives the number of topologies for large $k$. The
notation $(n)_k=n(n-1) \cdots (n-k+1)$ is used.

\begin{thm}
(R. Stanley) For $n\geq 5,$ we have the following values
\begin{eqnarray*}
 T(n,3\cdot 2^{n-2}) &= &(n)_{2} \\
 T(n,5\cdot 2^{n-3})&= & (n)_{3} \\
 T(n,9\cdot 2^{n-4}) &=& \frac{5(n)_{5}}{6} \\
 T(n,17\cdot 2^{n-5}) & = & \frac{(n)_{5}}{12} \\
 T(n,15\cdot2^{n-5}) &=& (n)_{5} \\
 T(n,7\cdot 2^{n-4}) &= &\frac{9}{4}(n)_{5}+(n)_{5} \\
 T(n,2^{n-1}) &=&(n)_{4}+(n)_{3}+\frac{(n)_{2}}{2}.
\end{eqnarray*}
\end{thm}

\begin{proof}
We give only the proof of the first assertion, which is related to the
previous Theorem. The element $a$ is chosen in $\binom n1=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).$
\eproof
\end{proof}

\bigskip

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\leq k\leq n.$ R. Stanley
\cite{Stanley} determined $T_0(n,k)$ for $n+1\leq k\leq n+3$.
We now determine $%
T_0(n,n+4),\,T_0(n,n+5),\;T_0(n,n+6)$:\\

\begin{thm}
We have
\begin{eqnarray*}
T_{0}(n,n+4) &=&\frac{(n-3)(n^{2}+15n+20)}{48}n!,\,\,\,n\geq 3. \\
T_{0}(n,n+5) &=&\frac{n^{4}+26n^{3}+35n^2-478n-248}{384}n!,\;n \geq 4,\;T_{0}(3,8)=1.\\
&&\hspace{7.5truecm}\\
T_{0}(n,n+6) &=&\frac{n^{5}-15n^{4}+1885n^3-15265n^2+53954n-97680}{3840}n!,\;n \geq 5\\
&&\hspace{7.5truecm}
\end{eqnarray*}
\end{thm}

\begin{minipage}{6truecm}
{\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.
\end{minipage}
\hfill
\begin{minipage}{6truecm}
\unitlength=.75truemm
\begin{picture}(40,30)(5,-5)
\put(39.25,-.10){$\bullet$} %\put(39,-4){$\emptyset$}
 \put(40,1){\line(-1,1){10}}
\put(29.25,10){$\bullet$} %\put(26,10){$A$}
 \put(30,11){\line(1,1){10}}
 \put(39.25,20){$\bullet$}
 %\put(39,23){$X$}
 \put(40,21){\line(1,-1){10}}
 \put(49.25,10){$\bullet$}
 %\put(52,10){$B$}
\put(40,1){\line(1,1){10}}
\end{picture} Figure 1
\end{minipage}

\bigskip

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

\unitlength=.5truemm
\begin{picture}(120,150)(-20,-50)
\put(-1.5,-1.05){$\bullet$} %\put(39,-4){$\emptyset$}
 \put(0,0){\line(1,1){30}}
\put(8.25,8.5){$\bullet$} %\put(26,10){$A$}
 \put(0,0){\line(-1,1){10}}
 \put(-11.5,8.5){$\bullet$}
 %\put(39,23){$X$}
 \put(-10,10){\line(1,1){30}}
 \put(-1.5,18.5){$\bullet$}
 %\put(52,10){$B$}
\put(0,20){\line(1,-1){10}}
 \put(10,30){\line(1,-1){10}}
 \put(20,40){\line(1,-1){10}}
 \put(8.5,28.5){$\bullet$}
  \put(18.5,38.5){$\bullet$}
  \put(18.25,18.5){$\bullet$}
  \put(28.25,28.5){$\bullet$}
  \put(0,0){\line(0,-1){20}}
  \put(-1.5,-10.55){$\bullet$}
  \put(-1.5,-20.55){$\bullet$}
  \put(-.55,-27.5){$\vdots$}
  \put(0,-30){\line(0,-1){10}}
  \put(-1.5,-31.55){$\bullet$}
  \put(-1.5,-41.55){$\bullet$}
  %%%
  \put(18.5,48.5){$\bullet$}
  \put(18.25,58.5){$\bullet$}
  %  \put(0,0){\line(0,-1){20}}
  \put(-1.5,-10.55){$\bullet$}
  \put(-1.5,-20.55){$\bullet$}
  \put(19.25,63.5){$\vdots$}
  \put(20,40){\line(0,1){20}}
  \put(20,71){\line(0,1){10}}
  \put(18.5,80.5){$\bullet$}
  \put(18.5,70.5){$\bullet$}
  %%% Number 2
\put(58.5,-1.05){$\bullet$} %\put(39,-4){$\emptyset$}
 \put(60,0){\line(1,1){20}}
\put(68.25,8.5){$\bullet$} %\put(26,10){$A$}
 \put(60,0){\line(-1,1){10}}
 \put(48.5,8.5){$\bullet$}
 %\put(39,23){$X$}
 \put(50,10){\line(1,1){30}}
 \put(58.5,18.5){$\bullet$}
 %\put(52,10){$B$}
\put(60,20){\line(1,-1){10}}
 \put(60,40){\line(1,-1){20}}
 \put(20,40){\line(1,-1){10}}
 \put(68.5,28.5){$\bullet$}
  \put(78.5,38.5){$\bullet$}
  \put(78.25,18.5){$\bullet$}
  \put(58.25,38.5){$\bullet$}
  \put(60,40){\line(1,1){10}}
  \put(-1.5,-10.55){$\bullet$}
  \put(-1.5,-20.55){$\bullet$}
  \put(59.45,-27.5){$\vdots$}
  \put(70,50){\line(1,-1){10}}
  \put(68.5,48.55){$\bullet$}
  \put(58.5,-41.55){$\bullet$}
  %%%
  \put(68.5,58.5){$\bullet$}
  \put(68.25,68.5){$\bullet$}
  \put(60,0){\line(0,-1){20}}
  \put(58.5,-10.55){$\bullet$}
  \put(58.5,-20.55){$\bullet$}
  \put(69.25,73.5){$\vdots$}
  \put(70,50){\line(0,1){20}}
  \put(70,81){\line(0,1){10}}
  \put(68.5,90.5){$\bullet$}
  \put(68.5,80.5){$\bullet$}
   \put(58.5,-31.55){$\bullet$}
  \put(60,-30){\line(0,-1){10}}
  %%% Number 3
  \put(118.5,-1.05){$\bullet$}
 \put(120,0){\line(1,1){10}}
\put(128.25,8.5){$\bullet$}
 \put(120,0){\line(-1,1){10}}
 \put(108.5,8.5){$\bullet$}
 \put(110,10){\line(1,1){10}}
 \put(118.5,18.5){$\bullet$}
\put(120,20){\line(1,-1){10}}
%%%
 \put(118.5,18.95){$\bullet$}
 \put(120,20){\line(1,1){10}}
\put(128.25,28.5){$\bullet$}
 \put(120,20){\line(-1,1){10}}
 \put(108.5,28.5){$\bullet$}
 \put(110,30){\line(1,1){10}}
 \put(118.5,38.5){$\bullet$}
\put(120,40){\line(1,-1){10}}
%%%
 \put(118.5,38.95){$\bullet$}
 \put(120,40){\line(1,1){10}}
\put(128.25,48.5){$\bullet$}
 \put(120,40){\line(-1,1){10}}
 \put(108.5,48.5){$\bullet$}
 \put(110,50){\line(1,1){10}}
 \put(118.5,58.5){$\bullet$}
\put(120,60){\line(1,-1){10}}
 \put(118.5,68.5){$\bullet$}
 \put(119.45,-27.5){$\vdots$}
 \put(120,0){\line(0,-1){20}}
  \put(118.5,-10.55){$\bullet$}
  \put(118.5,-20.55){$\bullet$}
  \put(119.25,73.5){$\vdots$}
  \put(120,60){\line(0,1){10}}
  \put(120,81){\line(0,1){10}}
  \put(118.5,90.5){$\bullet$}
  \put(118.5,80.5){$\bullet$}
   \put(118.5,-31.55){$\bullet$}
  \put(120,-30){\line(0,-1){10}}
  \put(118.5,-41.55){$\bullet$}

\end{picture}

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 $\displaystyle \frac{(n+3)(n-4)}{2}n!$,
in the second we have $\displaystyle \frac{(2n-9)(n-4)+1}{2}n!$ in
the third case the number is $\displaystyle
\frac{(n-4)(n-5)(n-6)}{8}n!$. In the fourth case, $\displaystyle
\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 $\displaystyle \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:
$\displaystyle 2(n^{2}-6n+6)n!$ in the first case . $\displaystyle
\frac{(n-5)(n-6)(n+1)}{4}n!$ in the second case. The number in the
third case is $\displaystyle \frac{(n-5)(n^{2}-12n+38)}{4}n!$. The
number in the fourth case is $\displaystyle
\frac{(n-5)(n-6)(n-7)(n-8)}{192}n!$.The number in the fifth case
is $\displaystyle \frac{(n-5)(n-6)(n-7)(n-8)(n-9)}{3840}n!$.
%In the sixth case, we have a copy of a boolean algebra and a copy of
%the graph in figure 1. The total number in this case is  
%??? . In the
%last one we have$\displaystyle \frac{(n^2+5n-12)}{12}n!$
%topologies.
In the last  case , we have a copy of a boolean
algebra and a copy of the graph in Figure 1.  The total
number in this case is $\displaystyle
\frac{(n^2+5n-12)}{12}n!$.
The total number is obtained by computing all
topologies in all cases. \hfill
\eproof
\vskip -.5in

\begin{minipage}{6truecm}
\par\noindent
 \unitlength=1truemm
\begin{picture}(50,60)(-50,0)
  \put(9.25,15){$\bullet$}
  \put(9.25,25){$\bullet$}
  \put(-10.55,25){$\bullet$}
   \put(-10.55,15){$\bullet$}
\put(-0.75,5){$\bullet$}
 \put(0,6){\line(1,1){10}}
 \put(0,6){\line(0,1){10}}
 \put(0,26){\line(0,1){10}}
  \put(0,6){\line(-1,1){10}}
   \put(0,16){\line(-1,1){10}}
    \put(0,16){\line(1,1){10}}
    \put(0,26){\line(-1,-1){10}}
    \put(0,36){\line(1,-1){10}}
    \put(0,36){\line(-1,-1){10}}
    \put(0,26){\line(1,-1){10}}
 \put(10,16){\line(0,1){10}}
 \put(-10,16){\line(0,1){10}}
 \put(-0.75,15){$\bullet$}
 \put(-0.75,35){$\bullet$}
 \put(-0.75,24.5){$\bullet$} Figure 2
 \end{picture}
\end{minipage}

\bigskip\bigskip

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
\begin{thm} 
We have
\begin{eqnarray*}
T_0^h(n,n+4)&=& \frac{(n-3)(n^{2}-3n+8)}{6},\;n\geq 3.\\
T_0^h(n,n+5)&=& \frac{(n-1)(n-3)(n^{2}-6n+32)}{24},\;n\geq 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 \geq 5,\;T_0^h(4,10)=2.\\
&&\hspace{7.5truecm}
\end{eqnarray*}
\end{thm}

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
\begin{eqnarray*}
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\,\,\; \mbox {for }12<k<16.
\end{eqnarray*}

So, $T(4)=355.$
\section{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)\neq
0$, for $2\leq k\leq 2^{n-2}.$ It is easy to prove that $T(n,k)\neq 0$, for $%
2\leq k\leq 2n.$

\section{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.

\begin{thebibliography}{9}
\bibliographystyle{plain}



\bibitem{Sharp}  H. Sharp, Jr., Cardinality of finite topologies, \textit{J.
Combinatorial Theory} \textbf{5} (1968), 82--86.

\bibitem{Sloane}  N.~J.~A. Sloane, Online Encyclopedia of Integer Sequences, \\
\href{http://www.research.att.com/~njas/sequences/index.html}{\tt http://www.research.att.com/\symbol{126}njas/sequences/index.html}.

\bibitem{Stanley}  R. Stanley, On the number of open sets of finite topologies,
\textit{J. Combinatorial Theory }\textbf{10} (1971) 75--79.

\bibitem{Stephen}
D. Stephen, Topology on finite sets, \textit{Amer.\ Math.\ Monthly}
\textbf{75} (1968) 739--741.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 \textit{Mathematics Subject Classification}:
Primary 11B73; Secondary 11B65.\ \

\noindent \emph{Keywords:} Labeled topology, Stirling number .

\bigskip \hrule \bigskip

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

\bigskip \hrule\bigskip

\vspace*{+.1in}
\noindent
Received August 29 2005;
revised version received May 20 2006.  
Published in {\it Journal of Integer Sequences}, May 24 2006.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}