\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\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://oeis.org/#1}{\underline{#1}}}


\begin{document}

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


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

\begin{center}
\vskip 1cm{\LARGE\bf Direct and Elementary Approach to \\
\vskip .1in 
Enumerate Topologies on a Finite Set} \vskip 1cm \large
Messaoud Kolli\\
Faculty of Science\\
Department of Mathematics\\
King Khaled University\\
Abha\\
Saudi Arabia\\
\href{mailto:kmessaud@kku.edu.sa}{\tt kmessaud@kku.edu.sa} \\
\end{center}

\vskip .1in

\begin{abstract}
Let $\mathbb{E}$ be a set with $n$ elements, and let  $\tau (n,k)$
be the set of all labelled topologies on $\mathbb{E}$, having $k$
open sets, and $T(n,k)=\left\vert \tau (n,k)\right\vert $. In this
paper, we use a direct approach to compute $T(n,k)$ for all $n\geq
4$ and $k\geq 6\cdot 2^{n-4}$.
\end{abstract}

\vskip .1in

%\newtheorem{theorem}{Theorem}[section]
%\newtheorem{acknowledgement}[theorem]{Acknowledgement}
%\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
%\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}



\section{Introduction}
Let $\mathbb{E}$ be a set with $n$ elements. The problem of
determining the total number of labelled topologies $T(n)$ one can
define on $\mathbb{E}$ is still an open question.  Sharp
\cite{Sharp}, and Stephen \cite{Stephen} had shown that every
topology which is not discrete contains $k\leq 3\cdot 2^{n-2}$ open
sets, and that this bound is optimal. Stanley \cite{Stanley}
computed all labelled topologies on $\mathbb{E},$ with $k\geq 7\cdot
2^{n-4}$ open sets. In the opposite sense, Benoumhani
\cite{Benoumhani} computed, for all $n$, the total number of
labelled topologies with $k \leq 12$ open sets. In the other hand,
Ern\'e and Stege \cite{Erne-Stege} computed the total number of
topologies, for $n \leq 14$. In this paper, we use a direct approach
to compute all labelled topologies on $\mathbb{E}$ having $k\geq
6\cdot 2^{n-4}$ open sets. Furthermore, we confirm the results in
\cite{Sharp, Stanley, Stephen}. This work is a continuation of the
results of \cite{Benoumhani, Stanley}. Here is our approach. The set
$\tau (n,k)$ is partitioned into two disjoint
parts as follows:%
\begin{equation*}
\tau (n,k)=\tau _{1}(n,k)\cup \tau _{2}(n,k),
\end{equation*}
where
\begin{eqnarray*}
\tau _{1}(n,k) &=&\left\{ \tau =\left\{ \varnothing ,A_{1},\ldots,A_{k-2},~%
\mathbb{E}\right\} \in \tau (n,k),\text{ \ such that \ }\bigcap%
\limits_{i=1}^{k-2}A_{i}\neq \varnothing \right\} ,~\ \ \ \ \ \  \\
\ \tau _{2}(n,k) &=&\tau (n,k)-\tau _{1}(n,k).\ \ \ \
\end{eqnarray*}%
In Theorem~\ref{theorem2.1}, we prove that the cardinal
$T_{1}(n,k)=\left\vert \tau _{1}(n,k)\right\vert $ satisfies
\begin{equation*}
T_{1}(n,k)=\sum_{l=1}^{n-1}\binom{n}{l}T(l,k-1),~\ \ \ \ \ \ \
%T_{1}(n,k)=\sum_{l=1}^{n-1}\binom{n}{k}T(l,k-1),~\ \ \ \ \ \ \
\forall ~n\geq 1.
\end{equation*}%
This relation enables us to compute $T_{1}(n,k)$ for $k>5\cdot
2^{n-4}$. For the determination of the cardinal
$T_{2}(n,k)=\left\vert \tau _{2}(n,k)\right\vert ,$ we introduce the
notion of minimal open set (Definition~\ref{definition2.2}), and we
designate by $\tau _{2}(n,k,\alpha )$\textit{\ }the labelled
topologies in $\tau _{2}(n,k)$  having $\alpha \geq 2$\ minimal
open sets. In Lemma~\ref{lem2.6}, it is proved that if $k>5\cdot 2^{n-4}$ such that $%
k\neq 6\cdot 2^{n-4},~$and $k\neq 2^{n-1}$, then all the minimal open sets of $%
\tau $ are necessarily singletons. So, we can compute the numbers $%
T_{2}(n,k,\alpha )$ for all $~n\geq 4,~~~k\geq 6\cdot 2^{n-4},$ and
$~\alpha \geq 2.$

\bigskip

\section{Basic Results}

\begin{theorem}
\label{theorem2.1} For every integer $n>1,$ and $2\leq k\leq 2^{n},$
we have
\begin{equation*}
T_{1}(n,k)=\sum_{l=1}^{n-1}\binom{n}{l}T(l,k-1),
\end{equation*}
with the convention that $T(l,1)=0.$
\end{theorem}


\begin{proof}
Let $A\subset \mathbb{E}$, with $\left\vert A\right\vert =l\leq
n-1,$ and let $\tau ^{\prime }$ be a topology on $A$, and
having $k-1$ open sets. To this topology we associate the following one%
\begin{equation*}
\Phi _{A}(\tau ^{\prime })=\tau =\left\{ O\cup A^{c},~\ \ \ \ O\in
\tau ^{\prime }\right\} \cup \{\varnothing \}\text{.}
\end{equation*}%
Obviously $\Phi _{A}$ is an injective mapping on $\tau (l,k-1)$ into
$\tau _{1}(n,k).$ In the other hand, if $\left\vert A\right\vert
=\left\vert B\right\vert =l\leq n-1$ and $A\neq B$, then
\begin{equation*}
R(\Phi _{A})\cap R(\Phi _{B})=\varnothing ,
\end{equation*}%
where $R(\Phi _{A})$ is the image of $\Phi _{A}$. This shows that%
\begin{equation*}
T_{1}(n,k)\geq \sum_{l=1}^{n-1}\binom{n}{l}T(l,k-1).
\end{equation*}
Conversely, if $\tau =\left\{ \varnothing ,~A_{1},\ldots,\ A_{k-2},~\mathbb{E}%
\right\} \in \tau _{1}(n,k)$, with
$A_{1}=\bigcap\limits_{i=1}^{k-2}A_{i},$ then $\tau ^{\prime
}=\left\{ O-A_{1},~\ \ O\in \tau \right\} $ is a topology on
$A_{1}^{c},$ having $k-1$ open sets, and $\Phi _{A_{1}^{c}}(\tau
^{\prime })=\tau $. This shows the other inequality, and completes
the proof.
\end{proof}

\bigskip

The following definition will be needed in the sequel.

\begin{definition}
\label{definition2.2} Let $\tau =\left\{ \varnothing
,~A_{1},\ldots,\ A_{k-2},~\mathbb{E}\right\} \in \tau (n,k).$ The
element $A_{i}$ is called a minimal open set, if it satisfies:
\begin{equation*}
A_{i}\cap A_{j}=A_{i}~\ ~\ or ~\ ~\ \varnothing, \qquad \forall
~j=1,\ldots,k-2.
\end{equation*}
\end{definition}

\begin{remark}\rm{
i) A topology on $\mathbb{E}$ is a bounded lattice with
$(1=\mathbb{E},$ $0=\varnothing ).$ 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 $%
\tau _{1}(n,k)$ is the subset of topologies having exactly one
minimal open set.
\smallskip

ii) If $\tau \in \tau _{2}(n,k)$, then $\tau $ has at least two
minimal open sets.
\smallskip

iii) The space $\mathbb{E}$ is a union of $\alpha $
minimal open sets for the topology $\tau \in \tau (n,k)$ if and only if $%
k=2^{\alpha }.$
\smallskip

iv) If $\tau $ has $\alpha $ minimal open sets, then $%
k\geq 2^{\alpha }.$ }
\end{remark}


\begin{definition}
For $\alpha \geq 2$, we define
\begin{equation*}
\tau _{2}(n,k,\alpha )=\left\{ \tau \in \tau _{2}(n,k),~~\ \tau
\hbox{ has } \alpha \hbox{ minimal open sets } \right\} .
\end{equation*}
\end{definition}

\noindent Note that if $\alpha _{1}\neq \alpha _{2}$, then $\tau
_{2}(n,k,\alpha _{1})\cap \tau _{2}(n,k,\alpha _{2})=\varnothing $. So%
\begin{equation*}
T_{2}(n,k)=\sum_{\alpha \geq 2,~\ 2^{\alpha }\leq
~k}T_{2}(n,k,\alpha ).
\end{equation*}%
The computation of $T_{2}(n,k)$ is then equivalent to the computation of $%
T_{2}(n,k,\alpha ),$ for $\alpha \geq 2,$ under the condition
$2^{\alpha
}\leq ~k$ $.$ If $k=2^{\alpha},$ then%
\begin{equation*}
T_{2}(n,2^{\alpha },\alpha )=S(n,\alpha ),
\end{equation*}%
where $S(n,\alpha )$ is the Stirling number of the second kind.

\bigskip

\begin{lemma} Let  $n\geq 1$, $\alpha
\geq 2$. Then $\tau _{2}(n,k,\alpha )$ is empty, for
$k>2^{n-1}+2^{\alpha -1}.$ In addition, this bound is optimal:
\begin{equation*}
\tau _{2}(n,2^{n-1}+2^{\alpha -1},\alpha )\neq \varnothing .
\end{equation*}
\end{lemma}


\begin{proof}
We argue by contradiction. Suppose that $\tau \in \tau
_{2}(n,k,\alpha )$, and write it as
\begin{equation*}
\tau =\left\{ \varnothing ,~A_{1},\ldots,A_{\alpha
},\ldots,\mathbb{E}\right\} ,
\end{equation*}%
where $A_{1},...,A_{\alpha }$ are the $\alpha $ minimal open sets of $\tau $%
. Put $A=\bigcup\limits_{i=1}^{\alpha }A_{i}$, the topology $\tau
^{\prime }=\left\{ O-A,~\ \ O\in \tau \right\} $ on $A^{c}$ has at
least $\left\lceil k~2^{1-\alpha }-1\right\rceil $ open sets. In the
other hand, $\left\vert A^{c}\right\vert \leq n-\alpha $, and since
$\tau ^{\prime }$ is at most the discrete topology, we obtain
\begin{equation*}
k~2^{1-\alpha }-1\leq \left\vert \tau ^{\prime }\right\vert \leq
2^{n-\alpha }.
\end{equation*}%
This contradiction proves that $\tau _{2}(n,k,\alpha )$ is empty.
The second assertion will be proved in the next section.
\end{proof}

\bigskip

\begin{lemma}
\label{lem2.6} Let $\tau \in \tau _{2}(n,k,\alpha),$ with $k>5\cdot
2^{n-4}$, $k\neq 6\cdot 2^{n-4}$, and $k\neq 2^{n-1}$. Then, all the
minimal open sets of $\tau $ are singletons.
\end{lemma}

\bigskip

\begin{proof} Let $\tau =\left\{ \varnothing ,\
A_{1},\ldots,A_{\alpha },\ldots,\mathbb{E}\right\} \in \tau
_{2}(n,k,\alpha ),$
where $A_{1},\ldots,A_{\alpha }$ are its minimal open sets, and suppose that $%
A=\bigcup\limits_{i=1}^{\alpha }A_{i}$ has more than $\alpha +1$
elements. The same argument used in the previous Lemma gives $5\cdot
2^{n-4}<k\leq 2^{n-2}+2^{\alpha -1}$. This last inequality is
possible only for $\alpha =n-1 $ or $\alpha =n-2.$ In the first
case, $\mathbb{E}$ is a union of $n-1$ minimal open sets, so
$k=2^{n-1}$, which is excluded. In the second, necessarily $k=6\cdot
2^{n-4},$ which is also excluded. So, all the minimal open sets of
$\tau $ are singletons.
\end{proof}



\section{Computation}

Firstly, we compute $T_{2}(n,k,\alpha )$, for $k\geq 6\cdot 2^{n-4}$
and $\alpha \geq 2$. We use the notation
\begin{equation*}
(n)_{l}=n(n-1)\cdots(n-l+1),
\end{equation*}%
and we convenient that if $l>n$, then $(n)_l=0$. We start by the number of topologies $\tau \in \tau _{2}(n,k,\alpha )$%
, such that $\tau $ 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\cdot 2^{n-4}$. If $k=2^{n-1}$, then $\alpha =n-1$ and the
number of these topologies is
$$
S(n,n-1)=\dfrac{(n)_{2}}{2}.
$$
If $k=6\cdot 2^{n-4}$, we have $\alpha =n-2,$ and the number of
these topologies is
$$
2(n-2)\binom{n}{n-2}\binom{n-2}{1}=(n-2)~(n)_{3}.
$$

\noindent The remaining topologies of $\tau _{2}(n,k,\alpha )$ have
the property that all their minimal open sets are singletons. For
this, let $\tau \in $ $\tau _{2}(n,k,\alpha )$
\begin{equation*}
\tau =\left\{ \varnothing ,\ A_{1},\ldots,A_{\alpha
},\ldots,\mathbb{E}\right\} .
\end{equation*}%
Put $\alpha =n-i,~~0\leq i\leq n-2$, and $A=\cup _{i=1}^{\alpha
}A_{i}$ .
The topology $\tau ^{\prime }=\left\{ O-A,~\ \ O\in \tau \right\} $ (on $%
A^{c}$), can be written as follows:%
\begin{equation*}
\tau ^{\prime }=\left\{ \varnothing ,~C_{1},\ldots,C_{m}\right\} ,~\
\ \ m\in \left\{ 0,1,2,\ldots,5\cdot 2^{i-3}-1,~3\cdot
2^{i-2}-1,~2^{i}-1\right\} .
\end{equation*}
To reconstruct $\tau $ from $\tau ^{\prime }$, we remark that every
$C_{j}$, if it exists, generates $2^{i_{j}}$ open sets in $\tau $,
with $i_{j}\leq
n-i-1.$ So, the number $k$ has necessarily the form:%
\begin{equation*}
k=2^{n-i}+2^{i_{1}}+2^{i_{2}}+...+2^{i_{m}},
\end{equation*}%
where the integers $i_{j}$ , $\ 1\leq j\leq m$ can be dependant. Our
approach is that for all $\alpha ,~2\leq \alpha \leq n$, we
determine all possibilities of the number $k$, and next the number
of all these topologies.

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

\bigskip

For \underline{$\alpha =n-1.$} $A^{c}$ $=\left\{ x\right\} $; so $m=1$, and $%
\tau ^{\prime }=\left\{ \varnothing ,C_{1}=\left\{ x\right\}
\right\} $. All
the possibilities of $k$ are given by%
\begin{equation*}
k=2^{n-1}+2^{n-1-j},~\ \ 1\leq j\leq n-1.
\end{equation*}%
The number of these topologies is
\begin{equation*}
T_{2}(n,2^{n-1}+2^{n-1-j},n-1)=n\binom{n-1}{j}=\frac{(n)_{j+1}}{j!},~\
\ 1\leq j\leq n-1.
\end{equation*}

For \underline{$\alpha =n-2.$} $A^{c}$ $=\left\{ x,y\right\},$ $\tau
^{\prime }=\left\{ \varnothing ,C_{1},\ldots,C_{m}\right\} ,~$with$\
\ \ m=1,2$ or $3.$

If $m=1,$ $\tau ^{\prime }=\left\{ \varnothing ,~C_{1}=\left\{
x,y\right\} \right\} $. Since we are supposing $k\geq 6\cdot
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\cdot 2^{n-4},$ and the number of these
topologies is
$$
\binom{n}{n-2}\binom{n-2}{1}=\dfrac{(n)_{3}}{2}.
$$


\noindent If $m=2,$ $\tau ^{\prime }$ $=\left\{ \varnothing
,C_{1}=\left\{ x\right\} ,C_{2}=\left\{ x,y\right\} \right\} $ \ \ \
\ or \ \ \ \ $\tau ^{\prime }=\left\{ \varnothing ,C_{1}=\left\{
y\right\} ,C_{2}=\left\{ x,y\right\} \right\}.$ Here we have two
categories of solutions:

\smallskip

a) $C_{1}$ generates $2^{n-3}$ open sets, and $C_{2}$ generates $%
2^{n-3-j},0\leq j\leq n-3$, \ open sets. Hence%
\begin{equation*}
k=2^{n-2}+2^{n-3}+2^{n-3-j}=6\cdot 2^{n-4}+2^{n-3-j},~\ \ 0\leq
j\leq n-3.
\end{equation*}%
The number of such topologies is
$$
2(j+1)\binom{n}{n-2}\binom{n-2}{j+1}=\dfrac{(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\cdot 2^{n-4},$ and the
number in this case is
$$
2~\binom{n}{n-2}\binom{n-2}{2}=\dfrac{(n)_{3}}{2}.
$$


\noindent If $m=3,$ $~\ \tau ^{\prime }=\left\{ \varnothing
,C_{1}=\left\{ x\right\} ,C_{2}=\left\{ y\right\} ,C_{3}=\left\{
x,y\right\} \right\} $. There are $8$ categories of solutions:

\bigskip

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\cdot 2^{n-4},$ and the wanted
number is
$$
\binom{n}{n-2}\binom{n-2}{1}=\dfrac{(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\leq j\leq n-3$.  So, $%
k=2^{n-2}+2^{n-3}+2^{n-3-j}+2^{n-3-j}=6\cdot 2^{n-4}+2^{n-2-j},~\ \
\ \ 1\leq j\leq n-3$, and the number of these topologies is
$$
2(j+1)\binom{n}{n-2} \binom{n-2}{j+1}=\dfrac{(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\cdot 2^{n-4}$, and the number of
these topologies is
$$
2\binom{n}{n-2}\binom{n-2}{2}=\dfrac{(n)_{4}}{2}.
$$


d) $C_{1}$ generates $2^{n-3}$ open sets, $C_{2}$ generates
$2^{n-2-j},$  $2\leq j\leq 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\cdot 2^{n-4}+3\cdot
2^{n-3-j},~\ \ \ \ 2\leq j\leq n-3$. The number of these topologies
is
$$
2(j+1)\binom{n}{n-2} \binom{n-2}{j+1}=\dfrac{(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\cdot 2^{n-4}$, and the number of
these topologies is
$$
\binom{n}{n-2}\binom{n-2}{2}=\dfrac{(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\cdot 2^{n-5}$, and the number
of these topologies is
$$
6 \binom{n}{n-2}\binom{n-2}{3}=\dfrac{(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\cdot 2^{n-4}$, and the number of
these topologies is
$$
6\binom{n}{n-2}\binom{n-2}{3}= \dfrac{(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\cdot 2^{n-6}$, and the number
of these topologies is
$$
6 \binom{n}{n-2}\binom{n-2}{4}= \dfrac{(n)_{6}}{8}.
$$
All the other cases give $k<6\cdot 2^{n-4}$. We resume all these
results in the next statement.


\begin{theorem}
Let  $n\geq 4$, and $\alpha =n-2$. Then we have
\begin{center}
\begin{equation*}
\begin{tabular}{|c|c|}
\hline $k$ & $T_{2}(n,k,n-2)$ \\ \hline $6\cdot 2^{n-4}$ &
$(n-1)(n)_{3}+\dfrac{1}{2}(n)_{5}$ \\ \hline $6\cdot 2^{n-4}+1$ &
$(n)_{3}$ \\ \hline
$6\cdot 2^{n-4}+2^{n-3-j},~\ \ \ \ 4\leq j\leq n-4$ & $\dfrac{(n-2)~(n)_{j+3}}{%
(j+1)!}$ \\ \hline
$6\cdot 2^{n-4}+3\cdot 2^{n-3-j},~\ \ 5\leq j\leq n-3$ & $\dfrac{(n)_{j+3}}{j!}$ \\
\hline $25\cdot 2^{n-6}$ &
$\dfrac{7}{24}(n)_{6}+\dfrac{1}{24}(n)_{7}$
\\ \hline $51\cdot 2^{n-7}$ & $\dfrac{1}{24}(n)_{7}$ \\ \hline
$13\cdot 2^{n-5}$ & $(n)_{5}+\dfrac{1}{6}(n)_{6}$ \\ \hline $27\cdot
2^{n-6}$ & $\dfrac{1}{6}(n)_{6}$ \\ \hline $7\cdot 2^{n-4}$ &
$\dfrac{5~}{4}(n)_{4}+\dfrac{1}{2}(n)_{5}$ \\ \hline $15\cdot
2^{n-5}$ &
$\dfrac{1}{2}(n)_{5}$ \\ \hline $2^{n-1}$ & $(n)_{3}+(n)_{4}$ \\
\hline $9\cdot 2^{n-4}$ & $\dfrac{1}{2}(n)_{4}$ \\ \hline $10\cdot
2^{n-4}$ & $\dfrac{1}{2}(n)_{3}$ \\ \hline
\end{tabular}%
\end{equation*}
\end{center}
All other topologies in $\tau _{2}(n,k,n-2)$ have $k<6\cdot 2^{n-4}$
open sets.
\end{theorem}

\bigskip

\noindent We use the same reasoning as above, to show the following
theorem.

\begin{theorem}
Let $n\geq 5,$ and $\alpha =n-i,~~3\leq i\leq ~n-2$. Then, the
following results hold.

For $\alpha =n-3$, if  $n=5$, we have
\begin{equation*}
\begin{tabular}{|c|c|c|c|c|c|}
\hline $k$ & $12$ & $13$ & $14$ & $15$ & $18$ \\ \hline
$T_{2}(5,k,2)$ & $360$ & $60$ & $180$ & $60$ & $20$ \\ \hline
\end{tabular}%
\end{equation*}%
If  $n\geq 6$, we have
\begin{equation*}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
$k$ & $6\cdot 2^{n-4}$ & $25\cdot 2^{n-6}$ & $13\cdot 2^{n-5}$ & $27\cdot 2^{n-6}$ & $%
7\cdot 2^{n-4}$ & $15\cdot 2^{n-5}$ & $9\cdot 2^{n-4}$ \\ \hline
$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}$ &  &  &  &  &  &  \\ \hline
\end{tabular}
\end{equation*}
For $\alpha =n-4,$ and $n\geq 6$
\begin{equation*}
\begin{tabular}{|c|c|c|c|c|}
\hline $k$ & $25\cdot 2^{n-6}$ & $13\cdot 2^{n-5}$ & $27\cdot
2^{n-6}$ & $17\cdot 2^{n-5}$ \\ \hline
$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}$ \\ \hline
\end{tabular}
\end{equation*}
 For $\alpha =n-i,~~5\leq i\leq n-2,$ and
$n\geq 7$
\begin{equation*}
\begin{tabular}{|c|c|c|c|}
\hline
$k$ & $6\cdot 2^{n-4}+2^{n-i-1}$ & $6\cdot 2^{n-4}+3\cdot 2^{n-i-2}$ & $%
2^{n-1}+2^{n-i-1} $ \\ \hline
$T_{2}(n,k,n-i)$ & $\dfrac{\left( n-2\right) }{(i-1)!}~(n)_{i+1}$ & $\dfrac{1%
}{(i-1)!}~(n)_{i+2}$ & $\dfrac{(n)_{i+1}}{i!}$ \\ \hline
\end{tabular}%
\end{equation*}%
All other topologies in $\tau _{2}(n,k,n-i),~~3\leq i\leq n-2,$ have
$k<6\cdot 2^{n-4}$ open sets.
\end{theorem}


Now, we compute $T_{1}(n,k)$, for $k>5\cdot ~2^{n-4}$.

\begin{theorem}
For all $n\geq 5,$  and  $k>5\cdot ~2^{n-4}$, we have:
\begin{eqnarray*}
T_{1}(n,2^{n-1}+1)&=&n, \\
T_{1}(n,3\cdot 2^{n-3}+1)&=&(n)_{3}, \\
T_{1}(n,5\cdot 2^{n-4}+1)&=&(n)_{4}, \\
T_{1}(n,k)&=&0, otherwise.
\end{eqnarray*}
\end{theorem}

\begin{proof}
Obviously, we have $T_{1}(n,2^{n-1}+1)=nT(n-1,2^{n-1})=n$,
$T_{1}(n,3\cdot 2^{n-3}+1)=nT(n-1,3\cdot 2^{n-3})=n\left( n-1\right)
_{2}=(n)_{3},$ and $T_{1}(n,5\cdot 2^{n-4}+1)=nT(n-1,5\cdot
2^{n-4})=n(n-1)_{3}=(n)_{4}$. If $k>2^{n-1}+1$, we have
$T(l,k-1)=0,$ for $1\leq l\leq n-1$, so $T_{1}(n,k)=0.$ If $5\cdot
2^{n-4}+1< k <2^{n-1}+1$, and $k$ $\neq 3\cdot 2^{n-3}+1$, the
Theorem~\ref{theorem2.1} yields $T_{1}(n,k)=nT(n-1,k-1)$. But we
know that $T(n-1,k-1)=0$, for $5\cdot 2^{n-4}<k-1<2^{n-1}$, and $k
\neq 3\cdot 2^{n-3}+1$; so we deduce $T_{1}(n,k)=0$, and the proof
is complete.
\end{proof}

\bigskip

Now, we can give the number of all labelled topologies with $k\geq
6\cdot 2^{n-4} $ open sets.

\begin{theorem}
Suppose that $n\geq 7,$ then the total number of labelled
topologies, with $k\geq 6\cdot 2^{n-4}$ open sets, is given by
\begin{center}
\begin{equation*}
\begin{tabular}{|c|c|c|c|}
\hline $k$ & $T_{2}(n,k)$ & $T_{1}(n,k)$ & $T(n,k)$ \\ \hline
$6\cdot 2^{n-4}$ & $(n-1)(n)_{3}+(n)_{4}+$ & $0$ & $(n-1)(n)_{3}+(n)_{4}$ \\
& $3~(n)_{5}+\dfrac{5}{4}(n)_{6}$ &  & $+3~(n)_{5}+\dfrac{5}{4}(n)_{6}$ \\
\hline $6\cdot 2^{n-4}+1$ & $(n)_{3}$ & $(n)_{3}$ & $2~(n)_{3}$ \\
\hline $6\cdot 2^{n-4}+2^{n-3-j},~4\leq j\leq n-4$ &
$\dfrac{2~(n-2)~(n)_{j+3}}{(j+1)!}$ & $0$ &
$\dfrac{2~(n-2)(n)_{j+3}}{(j+1)!}$ \\ \hline $6\cdot 2^{n-4}+3\cdot
2^{n-3-j},~5\leq j\leq n-3$ & $\dfrac{2}{j!}(n)_{j+3}$ & $0$ &
$\dfrac{2~(n)_{j+3}}{j!}$ \\ \hline
$25\cdot 2^{n-6}$ & $\dfrac{n+14}{24}(n)_{6}+\dfrac{1}{24}(n)_{7}$ & $0$ & $%
\dfrac{\left( n+14\right) (n)_{6}}{24}+\dfrac{(n)_{7}}{24}$ \\
\hline
$51\cdot 2^{n-7}$ & $\dfrac{1}{12}(n)_{7}$ & $0$ & $\dfrac{1}{12}(n)_{7}$ \\
\hline
$13\cdot 2^{n-5}$ & $2~(n)_{5}+\dfrac{1}{3}(n)_{6}$ & $0$ & $2~(n)_{5}+\dfrac{1}{%
3}(n)_{6}$ \\ \hline $27\cdot 2^{n-6}$ & $\dfrac{1}{2}(n)_{6}$ & $0$
& $\dfrac{1}{2}(n)_{6}$ \\ \hline
$7\cdot 2^{n-4}$ & $\dfrac{9~}{4}(n)_{4}+(n)_{5}$ & $0$ & $\dfrac{9~}{4}%
(n)_{4}+(n)_{5}$ \\ \hline $15\cdot 2^{n-5}$ & $(n)_{5}$ & $0$ &
$(n)_{5}$ \\ \hline
$2^{n-1}$ & $\dfrac{1}{2}(n)_{2}+(n)_{3}+(n)_{4}$ & $0$ & $\dfrac{1}{2}%
(n)_{2}+(n)_{3}+(n)_{4}$ \\ \hline $2^{n-1}+1$ & $n$ & $n$ & $2~n$
\\ \hline
$2^{n-1}+2^{n-j-1},~5\leq j\leq n-2$ & $\dfrac{2}{j!}(n)_{j+1}$ & $0$ & $%
\dfrac{2}{j!}(n)_{j+1}$ \\ \hline
$17\cdot 2^{n-5}$ & $\dfrac{1}{12}(n)_{5}$ & $0$ & $\dfrac{1}{12}(n)_{5}$ \\
\hline $9\cdot 2^{n-4}$ & $\dfrac{5}{6}(n)_{4}$ & $0$ &
$\dfrac{5}{6}(n)_{4}$ \\ \hline $10\cdot 2^{n-4}$ & $(n)_{3}$ & $0$
&
$(n)_{3}$ \\ \hline $3\cdot 2^{n-2}$ & $(n)_{2}$ & $0$ & $(n)_{2}$ \\
\hline $2^{n}$ & $1$ & $0$ & $1$ \\ \hline
\end{tabular}
\end{equation*}
\end{center}
For $n=6$, the total number of labelled topologies having $k \geq
24$ open sets is given by
\begin{center}
\begin{equation*}
\begin{tabular}{|cccc|}
\hline $k$ & \multicolumn{1}{|c}{$\left\vert \tau
_{2}(6,k)\right\vert $} & \multicolumn{1}{|c}{$\left\vert \tau
_{1}(6,k)\right\vert $} & \multicolumn{1}{|c|}{$\left\vert \tau
(6,k)\right\vert $} \\ \hline $24$ & \multicolumn{1}{|c}{$4020$} &
\multicolumn{1}{|c}{$0$} & \multicolumn{1}{|c|}{$4020$} \\ \hline
$25$ & \multicolumn{1}{|c}{$480$} & \multicolumn{1}{|c}{$120$} &
\multicolumn{1}{|c|}{$600$} \\ \hline $26$ &
\multicolumn{1}{|c}{$1680$} & \multicolumn{1}{|c}{$0$} &
\multicolumn{1}{|c|}{$1680$} \\ \hline $27$ &
\multicolumn{1}{|c}{$360$} & \multicolumn{1}{|c}{$0$} &
\multicolumn{1}{|c|}{$360$} \\ \hline $28$ &
\multicolumn{1}{|c}{$1530$} & \multicolumn{1}{|c}{$0$} &
\multicolumn{1}{|c|}{$1530$} \\ \hline $30$ &
\multicolumn{1}{|c}{$720$} & \multicolumn{1}{|c}{$0$} &
\multicolumn{1}{|c|}{$720$} \\ \hline $32$ &
\multicolumn{1}{|c}{$495$} & \multicolumn{1}{|c}{$0$} &
\multicolumn{1}{|c|}{$495$} \\ \hline $33$ &
\multicolumn{1}{|c}{$6$} & \multicolumn{1}{|c}{$6$} &
\multicolumn{1}{|c|}{$12$} \\ \hline $34$ &
\multicolumn{1}{|c}{$60$} & \multicolumn{1}{|c}{$0$} &
\multicolumn{1}{|c|}{$60$} \\ \hline $36$ &
\multicolumn{1}{|c}{$300$} & \multicolumn{1}{|c}{$0$} &
\multicolumn{1}{|c|}{$300$} \\ \hline $40$ &
\multicolumn{1}{|c}{$120$} & \multicolumn{1}{|c}{$0$} &
\multicolumn{1}{|c|}{$120$} \\ \hline $48$ &
\multicolumn{1}{|c}{$30$} & \multicolumn{1}{|c}{$0$} &
\multicolumn{1}{|c|}{$30$} \\ \hline $64$ & \multicolumn{1}{|c}{$1$}
& \multicolumn{1}{|c}{$0$} & \multicolumn{1}{|c|}{$1$} \\ \hline
\end{tabular}
\end{equation*}
\end{center}
For $n=5$, the total number of labelled topologies having $k \geq
12$ open sets is given by
\begin{center}
\begin{equation*}
\begin{tabular}{|c|c|c|c|}
\hline $k$ & $\left\vert \tau _{2}(5,k)\right\vert $ & $\left\vert
\tau _{1}(5,k)\right\vert $ & $\left\vert \tau (5,k)\right\vert $ \\
\hline $12$ & $660$ & $0$ & $660$ \\ \hline $13$ & $180$ & $60$ &
$240$ \\ \hline $14$ & $390$ & $0$ & $390$ \\ \hline $15$ & $120$ &
$0$ & $120$ \\ \hline $16$ & $190$ & $0$ & $190$ \\ \hline $17$ &
$5$ & $5$ & $10$ \\ \hline $18$ & $100$ & $0$ & $100$ \\ \hline $20$
& $60$ & $0$ & $60$ \\ \hline $24$ & $20$ & $0$ & $20$ \\ \hline
$32$ & $1$ & $0$ & $1$ \\ \hline
\end{tabular}
\end{equation*}
\end{center}
For $n=4$, the total number of labelled topologies having $k \geq 6$
open sets is given by
\begin{center}
\begin{equation*}
\begin{tabular}{|cccccccc|}
\hline $k=$ & \multicolumn{1}{|c}{$6$} & \multicolumn{1}{|c}{$7$} &
\multicolumn{1}{|c}{$8$}& \multicolumn{1}{|c}{$9$}&
\multicolumn{1}{|c}{$10$} & \multicolumn{1}{|c}{$12$} &
\multicolumn{1}{|c|}{$16$} \\
\hline $\left\vert \tau _{2}(4,k)\right\vert $ &
\multicolumn{1}{|c}{$72$} &
\multicolumn{1}{|c}{$30$} & \multicolumn{1}{|c}{$54$} & \multicolumn{1}{|c}{$%
16$} & \multicolumn{1}{|c}{$24$} & \multicolumn{1}{|c}{$12$} &
\multicolumn{1}{|c|}{$1$} \\
\hline $\left\vert \tau _{1}(4,k)\right\vert $ &
\multicolumn{1}{|c}{$0$} & \multicolumn{1}{|c}{$24$} &
\multicolumn{1}{|c}{$0$} & \multicolumn{1}{|c}{$4 $} &
\multicolumn{1}{|c}{$0$} & \multicolumn{1}{|c}{$0$} &
\multicolumn{1}{|c|}{$0$} \\ \hline $\left\vert \tau
(4,k)\right\vert $ & \multicolumn{1}{|c}{$72$} &
\multicolumn{1}{|c}{$54$} & \multicolumn{1}{|c}{$54$} & \multicolumn{1}{|c}{$%
20$} & \multicolumn{1}{|c}{$24$} & \multicolumn{1}{|c}{$12$} &
\multicolumn{1}{|c|}{$1$} \\ \hline
\end{tabular}
\end{equation*}
\end{center}
All the others topologies on $\mathbb{E}$ have $k<6\cdot 2^{n-4}$
open sets.
\end{theorem}



\begin{thebibliography}{10}
\bibitem{Benoumhani}
M. Benoumhani, The number of topologies on a finite set,
\emph{Journal of Integer sequences} \textbf{9} (2006).

\bibitem{Erne-Stege}
M. Erne, K. Stege, Counting finite posets and topologies,
\emph{Order} \textbf{8} (1991), 247--265.

\bibitem{Sharp}
 H. Sharp. Jr, Cardinality of finite topologies,
\emph{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. P. Stanley,  On the number of open sets of finite topologies,
\emph{J. Combinatorial Theory} \textbf{10} (1971), 74--79.

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

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05A15;
Secondary 06A07, 06A99.

\noindent \emph{Keywords: } 
binary relation, enumeration, finite set,
finite topology, partial order, posets.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received April 19 2006;
revised version received  February 28 2007.
Published in {\it Journal of Integer Sequences}, March 19 2007.

\bigskip
\hrule
\bigskip

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

\end{document}

