<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\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}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

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

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}
\usepackage{algorithm, algpseudocode}
\usepackage{tikz}
\usepackage{capt-of}

\DeclareMathOperator{\Orb}{Orb}

\begin{document}

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

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

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
On the Number of Inequivalent Monotone \\
\vskip .1in
Boolean Functions of 8 Variables
}
\vskip 1cm
\large
Bart\l{}omiej Pawelski\\
Institute of Informatics\\
University of Gda\'nsk\\
Wita Stwosza 57 \\
80-952 Gda\'nsk \\
Poland\\
\href{mailto:bartlomiej.pawelski@ug.edu.pl}{\tt bartlomiej.pawelski@ug.edu.pl} 
\end{center}

\begin{abstract}
In this paper, we present algorithms for determining the number of fixed
points in the set of monotone Boolean functions under a given permutation
of input variables. Then, using Burnside's lemma, we determine the number
of inequivalent monotone Boolean functions of 8 variables. The number
obtained is 1,392,195,548,889,993,358.
\end{abstract}

    \section{Introduction}\label{sec:intro}

A monotone Boolean function (MBF) is any Boolean function that can be
    implemented using only conjunctions and disjunctions \cite{r7}. Let
    $D_n$ be the set of all monotone Boolean functions of $n$ variables,
    and $d_n$ the cardinality of this set; $d_n$ is also known as the
    $n$-th Dedekind number (sequence \seqnum{A000372} 
    in the OEIS ({\it On-Line Encyclopedia of Integer Sequences})).

Two Boolean functions are {\it equivalent\/} if the first function can
be transformed into the second function by any permutation of input
variables. Let $I_n$ be the set of all $n$ input variables of a Boolean
function. There are $n!$ possible permutations of $I_n$---therefore there
are at most $n!$ MBFs in one equivalence class. Let $R_n$ denote the set
of all equivalence classes of $D_n$ and let $r_n$ denote the cardinality
of this set; $r_n$ is described by OEIS sequence \seqnum{A003182}.

    In 1985, Chuchang and Shoben \cite{Ch1985} came up with the idea to
    calculate the $r_n$ using Burnside's lemma. In the following year they
    calculated $r_7$ \cite{Ch1986}. Their result was confirmed by Stephen
    and Yusun in 2012 \cite{r7}. In 2018, Assarpour \cite{assarpour}
    gave lower bound of $r_8$: namely, 1,392,123,939,633,987,512.

    In 1990, Wiedemann calculated $d_8$ \cite{Wied1991}. His result was
    confirmed in 2001 by Fidytek, Mostowski, Somla, and Szepietowski
    \cite{Fid2001}.

    In this paper we develop algorithms for counting fixed points in
    $D_n$ under a given permutation of $I_n$. Then, we use Burnside's
    lemma to calculate $r_8 = 1,392,195,548,889,993,358$.

\begin{table}[H] \centering {\renewcommand{\arraystretch}{1.1}
\begin{tabular}{l|l|l} $n$ &amp; $d_n$                        &amp;
$r_n$                     \\ \hline 0 &amp; 2                              &amp;
2                         \\ 1 &amp; 3                              &amp; 3
\\ 2 &amp; 6                              &amp; 5                         \\
3 &amp; 20                             &amp; 10                        \\ 4 &amp;
168                            &amp; 30                        \\ 5 &amp; 7,581
&amp; 210                       \\ 6 &amp; 7,828,354                      &amp;
16,353                    \\ 7 &amp; 2,414,682,040,998              &amp;
490,013,148               \\ 8 &amp; 56,130,437,228,687,557,907,788 &amp;
1,392,195,548,889,993,358 \\ \hline \end{tabular}} \caption{Known values
of $d_n$ and $r_n$.} \label{tab:values} \end{table}

\section{Idea of calculating \texorpdfstring{$r_n$}{rn} using Burnside's
lemma}

Burnside's lemma is a standard combinatorial tool for counting the orbits of set under group action. Let $G$ denote a finite group that acts upon a set $X$. Burnside's lemma asserts that the number of orbits $| X/G |$ with respect to the action equals the average size of the sets $X^g = \lbrace x \in X \ \vert \ gx = x \rbrace$ when ranging over each $g \in G$ \cite{drube, earl2014}:
\begin{equation}
| X/G | = \frac{1}{| G |} \sum_{g \in G} | X^g |.
\end{equation}

Define $S_n$ to be the symmetric group of $I_n$. Each permutation $\pi
\in S_n$ can be written as a product of disjoint cycles. Define the
{\it cycle type\/} of $\pi$ to be the tuple of lengths of its disjoint cycles
in increasing order. For example, the cycle type of permutation $\pi =
(1\;2)(3\;4\;5)$ is $(2,3)$, and its total length is 5. The number
of different cycle types in $S_n$ for the appropriate value of $n$ is
described by the OEIS sequence \seqnum{A000041}. For $n=7$ there are
15 cycle types, and for $n=8$ there are 22 cycle types (see the detailed
list in Table \ref{tab:r7results} and Table \ref{tab:r8results}).

In 1985, Chuchang and Shoben \cite{Ch1985} presented the following application of Burnside's lemma to calculate $r_n$:
\begin{equation}
r_n = \frac{1}{n!} \sum_{\pi \in S_n}^{} |\phi_n(\pi)|,
\end{equation}
where
\begin{itemize}
  \item $r_n$ = number of equivalence classes in $D_n$
  \item $\phi_n(\pi)$ = set of all fixed points in $D_n$ under permutation $\pi \in S_n$.
\end{itemize}

They also used the fact that $|\phi_n(\pi)|$ is invariant under permutations with the same cycle type (also see \cite[Remark 287]{earl2014}).  We have
\begin{equation}
r_n = \frac{1}{n!} \sum_{i=1}^{k} \mu_i \phi(\pi_i),
\end{equation}
where
\begin{itemize}
  \item $k$ = number of different cycle types in $S_n$
  \item $i$ = index of the cycle type
  \item $\mu_i$ = number of permutations $\pi \in S_n$ with cycle type $i$
  \item $\pi_i$ = representative permutation $\pi \in S_n$ with cycle type $i$.
\end{itemize}

The formula for determining $\mu$ for each cycle type is as follows:
\begin{equation}
\mu_i = \frac{n!}{(l^{k_1}_1 \cdot l^{k_2}_2 \cdots l^{k_r}_r)(k_1! \cdot k_2! \cdots k_r!)}
\end{equation}
with cycle type of $r$ various lengths of cycles, and
$k_1$ cycles of length $l_1$, $k_2$ cycles of length $l_2, \ldots , k_r$ cycles of length $l_r$  \cite[Proposition 69]{earl2014}. 
Note that in this formula 1-cycles are not suppressed.
Precomputed values of $\mu$ can be found in the OEIS
sequence \seqnum{A181897}.

\section{Algorithms counting fixed points in \texorpdfstring{$D_n$}{Dn} under a given permutation of \texorpdfstring{$I_n$}{In}}

The most difficult subproblem to compute $r_n$ using Burnside's lemma is 
fast counting the fixed points of $D_n$ under a given permutation of $I_n$.

Let $B^n$ denote the power set of $I_n$. Each element in $B^n$ represents one of $2^n$ possible inputs of the Boolean function. Every permutation acting on $I_n$ regroups elements in $B^n$ and $D_n$. We use the notation
$\varnothing, x_1, x_2, x_1x_2, x_3, \ldots, x_1 x_2 x_3 \cdots x_n$ to describe elements in $B^n$.
We represent each Boolean function of $n$ variables by the binary string of length $2^n$. Each $i$-th bit of function in this representation is Boolean output where the argument is an element from $B^n$ standing in the same position.
    
For example, consider the following truth table:

\begin{table}[H]
\centering
{\renewcommand{\arraystretch}{1.2}
\begin{tabular}{c|c|c|c|c|c|c|c}
$\varnothing$ &amp; $x_1$ &amp; $x_2$ &amp; $x_1 x_2$ &amp; $x_3$ &amp; $x_1 x_3$ &amp; $x_2 x_3$ &amp; $x_1 x_2 x_3$  \\ \hline
0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 1 &amp; 1 &amp; 1 \\
\end{tabular}}
\caption{MBF of three variables that returns true iff $x_3$ is true.} \label{tab:table1}
\end{table}

MBF from Table \ref{tab:table1} can be represented as integer 15 for more convenient computer processing. All 6 MBFs in $D_2$ written as integers are: 0, 1, 3, 5, 7 and 15.
 
 For counting fixed points in $D_n$ after acting with a specific permutation $\pi \in S_n$ it is necessary to lift $\pi \in S_n$ to $\pi' \in S_{B^n}$. For example, consider permutation $\pi = (1\;2\;3)$ and look at how it regroups elements in $B^3$:

\begin{table}[H]
\centering
{\renewcommand{\arraystretch}{1.2}
\begin{tabular}{c|c|c|c|c|c|c|c|c}
&amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 \\
\hline
$(1)$ &amp; $\varnothing$ &amp; $x_1$ &amp; $x_2$ &amp; $x_1 x_2$ &amp; $x_3$ &amp; $x_1 x_3$ &amp; $x_2 x_3$ &amp; $x_1 x_2 x_3$  \\
\hline
$(1\;2\;3)$ &amp; $\varnothing$ &amp; $x_3$ &amp; $x_1$ &amp; $x_1 x_3$ &amp; $x_2$ &amp; $x_2 x_3$ &amp; $x_1 x_2$ &amp; $x_1 x_2 x_3$  \\
\end{tabular}}
\caption{Regrouping elements in $B^3$ under $\pi = (1\;2\;3)$.} \label{tab:table4}
\end{table}

Therefore $\pi = (1\;2\;3)$ lifts to $\pi'(0)(1\;2\;4)(3\;6\;5)(7)$. Each cycle designates points belonging to the same orbit. Points in each orbit are set to the same value in each $x \in \phi_n(\pi)$.

In this case, two conditions must be met: each function in $\phi_n(\pi)$ under $\pi = (1\;2\;3)$ has to have:

\begin{itemize}
  \item 1-st, 2-nd and 4-th bit set on the same value
  \item 3-rd, 5-th and 6-th bit set on the same value
\end{itemize}

Hence, all members of $\phi_3(\pi)$ under $\pi = (1\;2\;3)$ can be simply found by iteration through all 20 elements in $D_3$ and checking which are satisfying the above conditions:

\begin{table}[H]
\centering
{\renewcommand{\arraystretch}{1.2}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\cline{2-9}
\multicolumn{1}{c}{} &amp; \multicolumn{8}{|c|}{$n$-th bit of MBF} \\
\cline{1-9}
MBF written as integer &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 \\
\hline
0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0  \\
\hline
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1   \\
\hline
23 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 1 &amp; 1 &amp; 1   \\
\hline
127 &amp; 0 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1   \\
\hline
255 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1    \\
\hline
\end{tabular}}
\caption{List of five fixed points in $D_3$ under $\pi = (1\;2\;3)$.} \label{tab:table5}
\end{table}

\subsection{Generating the set of all fixed points in \texorpdfstring{$D_n$}{Dn} under permutation of cycle type of total length \texorpdfstring{$n$}{n}}

\def\drawconnections{\draw (0,0) -- (-2,2);
    \draw (0,0) -- (2,2);
    \draw (-2,2) -- (-3,4);
    \draw (-2,2) -- (-1,4);
    \draw (-2,2) -- (1,4);
    \draw (2,2) -- (1,4);
    \draw (2,2) -- (3,4);
    \draw (2,2) -- (-1,4);
    \draw (-3,4) -- (-2,6);
    \draw (-1,4) -- (-2,6);
    \draw (-1,4) -- (2,6);
    \draw (1,4) -- (2,6);
    \draw (1,4) -- (-2,6);
    \draw (3,4) -- (2,6);
    \draw (-2,6) -- (0,8);
    \draw (2,6) -- (0,8);}

\def\dospace{\hspace{0.684cm}}

Instead of doing a naive lookup in $D_n$ for functions satisfying given conditions, we can generate $\phi_n(\pi)$ directly. 

Given a poset $P = (X, \leq)$, downset of $P$ is such a subset $S \subseteq X$ that for each $x \in S$ all elements from $X \le x \in S$. $D_n$ is equivalent to the set of all downsets of $B^n$---therefore each element in $D_n$ is equivalent to some downset of $B^n$ \cite{campo}.

Two conditions must be met to generate MBF which is the fixed point in $D_n$ under the given permutation $\pi$:

\begin{itemize}
  \item All points in the same orbit of $\pi'$ should be set to the same value---0 or 1.
  \item Value of points must respect the order of set inclusion.
\end{itemize}

For example, consider permutation $\pi = (1\;2)(3\;4)$. After lifting it into permutation of $B^4$, we get $\pi' = (0)(1\;2)(3)(4\;8)(5\;10)(6\;9)(7\;11)(12)(13\;14)(15)$.

Now, let us transform this permutation into a binary poset of orbits ordered by set inclusion. Orbits in the following example are represented by their smallest representative:

\begin{center}

    \begin{tikzpicture}[scale=0.6]

    \drawconnections{}

    \draw[fill] (0,0) circle (.1cm) node[right] {$0$};
    \draw[fill] (-2,2) circle (.1cm) node[left] {$1$};
    \draw[fill] (-3,4) circle (.1cm) node[right] {$3$};
    \draw[fill] (2,2) circle (.1cm) node[right] {$4$};
    \draw[fill] (-1,4) circle (.1cm) node[left] {$5$};
    \draw[fill] (1,4) circle (.1cm) node[right] {$6$};
    \draw[fill] (-2,6) circle (.1cm) node[left] {$7$};
    \draw[fill] (3,4) circle (.1cm) node[right] {$12$};
    \draw[fill] (2,6) circle (.1cm) node[right] {$13$};
    \draw[fill] (0,8) circle (.1cm) node[right] {$15$};

    \end{tikzpicture}
    \captionof{figure}{Poset of orbits of $B_4$ under $\pi = (1\;2)(3\;4)$ ordered by set inclusion.}
    
\end{center}

Now it is only necessary to generate all downsets of this poset. In this case, the number of all downsets is 28:

    \begin{center}
    \begin{tikzpicture}[scale=0.19]
    \drawconnections{}
    \draw[black, fill=white] (0,0) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-2,2) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-3,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (2,2) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-1,4) circle (.5cm) node[left] {};
    \draw[black, fill=white] (1,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (3,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (0,8) circle (.5cm) node[right] {};
    
    \end{tikzpicture} \dospace{} \begin{tikzpicture}[scale=0.19]
    \drawconnections{}
    \draw[black, fill=black] (0,0) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-2,2) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-3,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (2,2) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-1,4) circle (.5cm) node[left] {};
    \draw[black, fill=white] (1,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (3,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (0,8) circle (.5cm) node[right] {};

    \end{tikzpicture} \dospace{} \begin{tikzpicture}[scale=0.19]
    \drawconnections{}
    \draw[black, fill=black] (0,0) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-2,2) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-3,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (2,2) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-1,4) circle (.5cm) node[left] {};
    \draw[black, fill=white] (1,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (3,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (0,8) circle (.5cm) node[right] {};

    \end{tikzpicture} \dospace{} \begin{tikzpicture}[scale=0.19]
    \drawconnections{}
    \draw[black, fill=black] (0,0) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-2,2) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-3,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (2,2) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-1,4) circle (.5cm) node[left] {};
    \draw[black, fill=white] (1,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (3,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (0,8) circle (.5cm) node[right] {};
    \end{tikzpicture} \dospace{} \begin{tikzpicture}[scale=0.19]
    \drawconnections{}
    \draw[black, fill=black] (0,0) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-2,2) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-3,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (2,2) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-1,4) circle (.5cm) node[left] {};
    \draw[black, fill=white] (1,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (3,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (0,8) circle (.5cm) node[right] {};
    \end{tikzpicture} \dospace{} \begin{tikzpicture}[scale=0.19]
    \drawconnections{}
    \draw[black, fill=black] (0,0) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-2,2) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-3,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (2,2) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-1,4) circle (.5cm) node[left] {};
    \draw[black, fill=white] (1,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-2,6) circle (.5cm) node[right] {};
    \draw[black, fill=black] (3,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (0,8) circle (.5cm) node[right] {};
    \end{tikzpicture} \dospace{} \begin{tikzpicture}[scale=0.19]
    \drawconnections{}
    \draw[black, fill=black] (0,0) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-2,2) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-3,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (2,2) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-1,4) circle (.5cm) node[left] {};
    \draw[black, fill=white] (1,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (3,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (0,8) circle (.5cm) node[right] {};
    \end{tikzpicture}
    
   \bigskip 
    
    \begin{tikzpicture}[scale=0.19]
    \drawconnections{}
    \draw[black, fill=black] (0,0) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-2,2) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-3,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (2,2) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-1,4) circle (.5cm) node[left] {};
    \draw[black, fill=white] (1,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (3,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (0,8) circle (.5cm) node[right] {};
    \end{tikzpicture} \dospace{} \begin{tikzpicture}[scale=0.19]
    \drawconnections{}
    \draw[black, fill=black] (0,0) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-2,2) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-3,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (2,2) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-1,4) circle (.5cm) node[left] {};
    \draw[black, fill=white] (1,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (3,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (0,8) circle (.5cm) node[right] {};
    \end{tikzpicture} \dospace{} \begin{tikzpicture}[scale=0.19]
    \drawconnections{}
    \draw[black, fill=black] (0,0) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-2,2) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-3,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (2,2) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-1,4) circle (.5cm) node[left] {};
    \draw[black, fill=white] (1,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (3,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (0,8) circle (.5cm) node[right] {};
    \end{tikzpicture} \dospace{} \begin{tikzpicture}[scale=0.19]
    \drawconnections{}
    \draw[black, fill=black] (0,0) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-2,2) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-3,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (2,2) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-1,4) circle (.5cm) node[left] {};
    \draw[black, fill=black] (1,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (3,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (0,8) circle (.5cm) node[right] {};
    \end{tikzpicture} \dospace{} \begin{tikzpicture}[scale=0.19]
    \drawconnections{}
    \draw[black, fill=black] (0,0) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-2,2) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-3,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (2,2) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-1,4) circle (.5cm) node[left] {};
    \draw[black, fill=black] (1,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (3,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (0,8) circle (.5cm) node[right] {};
    \end{tikzpicture} \dospace{} \begin{tikzpicture}[scale=0.19]
    \drawconnections{}
    \draw[black, fill=black] (0,0) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-2,2) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-3,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (2,2) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-1,4) circle (.5cm) node[left] {};
    \draw[black, fill=black] (1,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (3,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (0,8) circle (.5cm) node[right] {};
    \end{tikzpicture} \dospace{} \begin{tikzpicture}[scale=0.19]
    \drawconnections{}
    \draw[black, fill=black] (0,0) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-2,2) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-3,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (2,2) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-1,4) circle (.5cm) node[left] {};
    \draw[black, fill=black] (1,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (3,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (0,8) circle (.5cm) node[right] {};
    \end{tikzpicture}
    
   \bigskip 
    
    \begin{tikzpicture}[scale=0.19]
    \drawconnections{}
    \draw[black, fill=black] (0,0) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-2,2) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-3,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (2,2) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-1,4) circle (.5cm) node[left] {};
    \draw[black, fill=black] (1,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (3,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (0,8) circle (.5cm) node[right] {};
    \end{tikzpicture} \dospace{} \begin{tikzpicture}[scale=0.19]
    \drawconnections{}
    \draw[black, fill=black] (0,0) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-2,2) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-3,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (2,2) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-1,4) circle (.5cm) node[left] {};
    \draw[black, fill=white] (1,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-2,6) circle (.5cm) node[right] {};
    \draw[black, fill=black] (3,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (0,8) circle (.5cm) node[right] {};
    \end{tikzpicture} \dospace{} \begin{tikzpicture}[scale=0.19]
    \drawconnections{}
    \draw[black, fill=black] (0,0) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-2,2) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-3,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (2,2) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-1,4) circle (.5cm) node[left] {};
    \draw[black, fill=white] (1,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-2,6) circle (.5cm) node[right] {};
    \draw[black, fill=black] (3,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (0,8) circle (.5cm) node[right] {};
    \end{tikzpicture} \dospace{} \begin{tikzpicture}[scale=0.19]
    \drawconnections{}
    \draw[black, fill=black] (0,0) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-2,2) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-3,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (2,2) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-1,4) circle (.5cm) node[left] {};
    \draw[black, fill=white] (1,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-2,6) circle (.5cm) node[right] {};
    \draw[black, fill=black] (3,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (0,8) circle (.5cm) node[right] {};
    \end{tikzpicture} \dospace{} \begin{tikzpicture}[scale=0.19]
    \drawconnections{}
    \draw[black, fill=black] (0,0) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-2,2) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-3,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (2,2) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-1,4) circle (.5cm) node[left] {};
    \draw[black, fill=white] (1,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-2,6) circle (.5cm) node[right] {};
    \draw[black, fill=black] (3,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (0,8) circle (.5cm) node[right] {};
    \end{tikzpicture} \dospace{} \begin{tikzpicture}[scale=0.19]
    \drawconnections{}
    \draw[black, fill=black] (0,0) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-2,2) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-3,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (2,2) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-1,4) circle (.5cm) node[left] {};
    \draw[black, fill=black] (1,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-2,6) circle (.5cm) node[right] {};
    \draw[black, fill=black] (3,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (0,8) circle (.5cm) node[right] {};
    \end{tikzpicture} \dospace{} \begin{tikzpicture}[scale=0.19]
    \drawconnections{}
    \draw[black, fill=black] (0,0) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-2,2) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-3,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (2,2) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-1,4) circle (.5cm) node[left] {};
    \draw[black, fill=black] (1,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-2,6) circle (.5cm) node[right] {};
    \draw[black, fill=black] (3,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (0,8) circle (.5cm) node[right] {};
    \end{tikzpicture}
    
   \bigskip 
    
    \begin{tikzpicture}[scale=0.19]
    \drawconnections{}
    \draw[black, fill=black] (0,0) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-2,2) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-3,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (2,2) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-1,4) circle (.5cm) node[left] {};
    \draw[black, fill=black] (1,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-2,6) circle (.5cm) node[right] {};
    \draw[black, fill=black] (3,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (0,8) circle (.5cm) node[right] {};
    \end{tikzpicture} \dospace{} \begin{tikzpicture}[scale=0.19]
    \drawconnections{}
    \draw[black, fill=black] (0,0) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-2,2) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-3,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (2,2) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-1,4) circle (.5cm) node[left] {};
    \draw[black, fill=black] (1,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-2,6) circle (.5cm) node[right] {};
    \draw[black, fill=black] (3,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (0,8) circle (.5cm) node[right] {};
    \end{tikzpicture} \dospace{}\begin{tikzpicture}[scale=0.19]
    \drawconnections{}
    \draw[black, fill=black] (0,0) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-2,2) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-3,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (2,2) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-1,4) circle (.5cm) node[left] {};
    \draw[black, fill=black] (1,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-2,6) circle (.5cm) node[right] {};
    \draw[black, fill=black] (3,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (0,8) circle (.5cm) node[right] {};
    \end{tikzpicture} \dospace{} \begin{tikzpicture}[scale=0.19]
    \drawconnections{}
    \draw[black, fill=black] (0,0) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-2,2) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-3,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (2,2) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-1,4) circle (.5cm) node[left] {};
    \draw[black, fill=black] (1,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-2,6) circle (.5cm) node[right] {};
    \draw[black, fill=black] (3,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (0,8) circle (.5cm) node[right] {};
    \end{tikzpicture} \dospace{} \begin{tikzpicture}[scale=0.19]
    \drawconnections{}
    \draw[black, fill=black] (0,0) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-2,2) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-3,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (2,2) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-1,4) circle (.5cm) node[left] {};
    \draw[black, fill=black] (1,4) circle (.5cm) node[right] {};
    \draw[black, fill=white] (-2,6) circle (.5cm) node[right] {};
    \draw[black, fill=black] (3,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (0,8) circle (.5cm) node[right] {};
    \end{tikzpicture} \dospace{} \begin{tikzpicture}[scale=0.19]
    \drawconnections{}
    \draw[black, fill=black] (0,0) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-2,2) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-3,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (2,2) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-1,4) circle (.5cm) node[left] {};
    \draw[black, fill=black] (1,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-2,6) circle (.5cm) node[right] {};
    \draw[black, fill=black] (3,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (2,6) circle (.5cm) node[right] {};
    \draw[black, fill=white] (0,8) circle (.5cm) node[right] {};
    \end{tikzpicture} \dospace{} \begin{tikzpicture}[scale=0.19]
    \drawconnections{}
    \draw[black, fill=black] (0,0) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-2,2) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-3,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (2,2) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-1,4) circle (.5cm) node[left] {};
    \draw[black, fill=black] (1,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (-2,6) circle (.5cm) node[right] {};
    \draw[black, fill=black] (3,4) circle (.5cm) node[right] {};
    \draw[black, fill=black] (2,6) circle (.5cm) node[right] {};
    \draw[black, fill=black] (0,8) circle (.5cm) node[right] {};
    \end{tikzpicture}

\end{center}
The set of structures thus obtained is equivalent to $\phi_4(\pi)$ under $\pi = (1\;2)(3\;4)$. One can unpack the downsets obtained thereby to the integer representation of MBF of $2^n$ length.

This algorithm is being used only to generate $\phi_n(\pi)$ when $\pi$ has a cycle type of total length $n$---for example, we use Algorithm 1 to generate $\phi_4(\pi)$ under $\pi = (1\;2)(3\;4)$, but to generate $\phi_5(\pi)$ under the same permutation it is cheaper computationally to use Algorithm 2.

\begin{algorithm}[H]
\caption{Generate $\phi_{n}(\pi)$ under permutation of cycle type of total length $n$}
    \hspace*{\algorithmicindent} \textbf{Input:} Cycle type $i$ of total length $n$ \\
    \hspace*{\algorithmicindent} \textbf{Output:} Set $S = \phi_{n}(\pi)$
\begin{algorithmic}[1]
\State Determine representative $\pi \in S_n$  of cycle type $i$
\State Lift $\pi$ into $\pi' \in S_{B^n}$
\State Generate set $\Orb_i$ containing all orbits in $\pi'$
\State Order $\Orb_i$ into poset $P$ by set inclusion
\State Initialize set $S$ of downsets of $P$
\State Add two downsets: \{\} and \{0\} to $S$
\ForAll {\textbf{elements} $a \in P $}
\ForAll {\textbf{elements} $b \in S $}
\If{({$b$} $\cup$ $a$) is downset of $P$}
  \State Add downset ({$b$} $\cup$ $a$) to $S$
\EndIf
\EndFor
\EndFor
\end{algorithmic}
\end{algorithm}

\subsection{Generating the set of all fixed points in \texorpdfstring{$D_{n+1}$}{D(n-1)} under permutation of cycle type of total length \texorpdfstring{$n$}{n}}

Each $\omega$ in $D_{n+1}$ can be split into two functions ($\alpha$, $\beta$) from $D_n$. Moreover, there is a relation $\alpha \preceq \beta$, which means that for every $i$-th bit $\alpha_i \leq \beta_i$ \cite{Bakoev, Fid2001}. For all $\pi \in S_n$, as $\phi_{n+1}(\pi)$ is subset of $D_{n+1}$, each $\omega$ in $\phi_{n+1}(\pi)$ can be split into two functions ($\alpha$, $\beta$).

Constructing $\omega$ from $\alpha$ is simply adding new variable $(x_{n+1})$ to $\alpha$. $\beta$ contains data about each possible intersection of $\alpha$ with $(x_{n+1})$. Hence, $\alpha$ clearly belongs to $\phi_{n}(\pi)$---same as $\beta$, as its variables are regrouped in the same way. Only difference between them is additional variable $(x_{n+1})$ which is fixed point of $\pi$, added to each element in $\beta$.

\begin{table}[H]
\centering
\begin{tabular}{c|c|c|c|c|c|c|c|c}
&amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 \\
\hline
$(1)$ &amp; $\varnothing$ &amp; $x_1$ &amp; $x_2$ &amp; $x_1 x_2$ &amp; $x_3$ &amp; $x_1 x_3$ &amp; $x_2 x_3$ &amp; $x_1 x_2 x_3$  \\
\hline
$(1\;2)$ &amp; $\varnothing$ &amp; \textbf{$x_2$} &amp; $x_1$ &amp; $x_1 x_2$ &amp; $x_3$ &amp; $x_2 x_3$ &amp; $x_1 x_3$ &amp; $x_1 x_2 x_3$  \\
\end{tabular}
\caption{Regrouping of elements in $B^3$ under $\pi = (1\;2)$.} \label{tab:regroupB3}
\end{table}

Hence, we can take advantage of well-known algorithms for determining Dedekind numbers (for example \cite{Fid2001, Wied1991}), but instead of giving $D_n$ on input, $\phi_n(\pi)$ will be given.

To construct Algorithm 2 we use a similar approach that was used by Fidytek et al. \cite[Algorithm 1]{Fid2001}. Note that any algorithm from \cite{Fid2001} will do the job, however, other algorithms don't return a set, but its cardinality.

\begin{algorithm}[H]
\caption{Generating $\phi_{n+1}(\pi)$ under permutation $\pi$ of cycle type of total length $n$}
    \hspace*{\algorithmicindent} \textbf{Input:} Cycle type $i$ of total length $n$ \\
    \hspace*{\algorithmicindent} \textbf{Output:} Set $S = \phi_{n+1}(\pi)$
\begin{algorithmic}[1]
\State Use Algorithm 1 to generate $S' = \phi_n(\pi)$
\State Convert all elements in $S'$ to integers of length $2^n$ bits
\State Initialize set $S$ of integers of length $2^{n+1}$ bits
\ForAll {\textbf{elements} $a \in S' $}
\ForAll {\textbf{elements} $b \in S' $}
\If{($a$ $|$ $b$) = $b$} \Comment{``$|$" is bitwise ``OR"}
  \State Add integer (($a$ $&lt;&lt;$ $2^n$) $|$ $b$) to $S$ \Comment{``$&lt;&lt;$" is logical shift}
\EndIf
\EndFor
\EndFor
\end{algorithmic}
\end{algorithm}

\subsection{Determining \texorpdfstring{$|\phi_8(\pi)|$}{number of fixed points in D8} under \texorpdfstring{$\pi = (1\;2)(3\;4)(5\;6)(7\;8)$}{permutation of cycle type (1 2)(3 4)(5 6)(7 8)}}

Determining $|\phi_8(\pi)|$ under $\pi = (1\;2)(3\;4)(5\;6)(7\;8)$
is too memory-intensive for Algorithm 1 considering the resources
at hand. The width of the poset of orbits of the superset of
$\pi = (1\;2)(3\;4)(5\;6)(7\;8)$ is 38, so the weak lower bound of
$|\phi_8(\pi)|$ is $2^{38} = $ 274877906944. In practice, even the machine
with 128GB RAM is insufficient to store such a number of downsets---so
there was a need to develop a better algorithm for this particular case.

The idea of a cheaper calculation of this number was based on Wiedemann's approach \cite{Wied1991}. He used the fact that each function from $D_{n+2}$ can be split into 4 functions from $D_n$: $\alpha_w, \beta_w, \gamma_w, \delta_w$, and there are following dependencies: $\alpha_w \preceq \beta_w \preceq \delta_w$, $\alpha_w \preceq \gamma_w \preceq \delta_w$.

We use a similar approach based on splitting each function from $\phi_{n+2}(\pi)$ into 4 parts. We focus on a special case---when $\pi \in S_{n+2}$ is the product of disjoint 1-cycles and at least one 2-cycle. Let $\tau$ denote such the permutation. In other words, $\tau = \tau_1 \cdots \tau_x$, and $\tau_x$ is 2-cycle: $(n\!+\!1\;n\!+\!2)$. Let $\sigma$ denote permutation such that $\sigma \circ \tau_x = \tau$.

We can split each function from $\phi_{n+2}(\pi)$ into the following functions: $\alpha, \delta \in \phi_n(\sigma)$ and $\beta, \gamma \in D_n$. Moreover, $\alpha \preceq \beta \preceq \delta$, $\alpha \preceq \gamma \preceq \delta$, and $\gamma = \beta((1\;2))$.

For example, $\tau = (1\;2)(3\;4)$ lifts to $\tau'$(0)(1 2)(3)(4 8)(5 10)(6 9)(7 11)(12)(13 14)(15). $\sigma = (1\;2)$. Using the above approach we break it down into three parts:

\begin{itemize}
  \item $\alpha$ as (0)(1 2)(3); being function from $\phi_2(\sigma)$
  \item $\beta \gamma$ as (4 8)(5 10)(6 9)(7 11) being pairs of functions from $D_n$ such that $\gamma = \beta((1\;2))$
  \item $\delta$ as (12)(13 14)(15), being function from $\phi_2(\sigma)$.
\end{itemize}

Knowing how each function in $\phi_{n+2}(\tau)$ can be split into two functions from $D_n$ and two functions from $\phi_{n}(\sigma)$, we can derive Algorithm 3:

\begin{algorithm}[H]
\caption{Determining $|\phi_{n+2}(\tau)|$}
    \hspace*{\algorithmicindent} \textbf{Input:} $D_n$ and $\phi_n(\sigma)$ \\
    \hspace*{\algorithmicindent} \textbf{Output:} $|\phi_{n+2}(\tau)|$
\begin{algorithmic}[1]
\State Initialize $k = 0$,
\ForAll {$\beta \in D_n $}
\State Determine $\gamma= \beta((1\;2))$
\State Initialize $down = 0$, $up = 0$
\ForAll {$\alpha \in \phi_n(\sigma)$}
  \If{$(\alpha \preceq (\beta \ | \ \gamma))$} \Comment{``$|$" is bitwise ``OR"}
    \State $down$ = $down$ + $1$
    \EndIf
\EndFor
\ForAll {$\delta \in \phi_n(\sigma)$}
  \If{$((\beta \ \&amp; \ \gamma) \preceq \delta)$} \Comment{``\&amp;" is bitwise ``AND"}
    \State $up = up + 1$
    \EndIf
\EndFor
\State $k = k + up \cdot down$
\EndFor
\end{algorithmic}
\end{algorithm}

As all above-described algorithms are sufficient to count $|\phi_8(\pi)|$ for all $\pi \in S_8$, we do not explore a more generalized case of Algorithm 3---when $\pi$ has at least one disjoint 2-cycle. Performing calculations using a similar approach should speed-up counting, but the relation between $\beta$ and $\gamma$ is more complex than in above-described special case. However, derivation of such a generalized algorithm seems essential in the future computation of $r_9$--but it will only be countable after computation of $d_9$.

\section{Implementation and results}

The algorithms were implemented in Java and run on a computer with an Intel Core i7-9750H processor. The results were tested and compared with the results of Chuchang and Shoben \cite{Ch1986} for $r_7$. We found two misprints in their paper, clearly made during the typing process. Namely, it says that $\mu_{11}$ is 540 (instead of 504), and $\phi_7(\pi_3)$ is 20688224 (instead of 2068224). We give therefore a complete, correct table of detailed calculation results for $r_7$. The total computation time of $r_8$ was approximately a few minutes (with $d_8$ precomputed).


\begin{table}[H]
\centering
    {\renewcommand{\arraystretch}{1.1}
    \begin{tabular}{c*{3}{c}c}
    $i$              &amp; $\pi_i$ &amp; $\mu_i$ &amp; $\phi_7(\pi_i)$ \\
    \hline
        1    &amp; (1)              &amp; 1     &amp; 2414682040998  \\
        2    &amp; (12)             &amp; 21    &amp; 2208001624  \\
        3    &amp; (123)            &amp; 70   &amp; 2068224  \\
        4    &amp; (1234)           &amp; 210   &amp; 60312  \\
        5    &amp; (12345)          &amp; 504  &amp; 1548  \\
        6    &amp; (123456)         &amp; 840  &amp; 766  \\
        7    &amp; (1234567)        &amp; 720  &amp; 101  \\
        8    &amp; (12)(34)         &amp; 105   &amp; 67922470  \\
        9    &amp; (12)(345)        &amp; 420  &amp; 59542  \\
        10   &amp; (12)(3456)       &amp; 630  &amp; 26878  \\
        11   &amp; (12)(34567)      &amp; 504  &amp; 264  \\
        12   &amp; (123)(456)       &amp; 280  &amp; 69264  \\
        13   &amp; (123)(4567)      &amp; 420  &amp; 294  \\
        14   &amp; (12)(34)(56)     &amp; 105   &amp; 12015832  \\
        15   &amp; (12)(34)(567)    &amp; 210  &amp; 10192  \\
        
        \hline
    \end{tabular}}
    \[ r_7 = \frac{1}{5040} \sum_{i=1}^{k = 15} \mu_i \phi_7(\pi_i) = 490013148 \]
    \caption{Detailed calculation results for $r_7$.} \label{tab:r7results}
    \end{table}


\begin{table}[H]
\centering
    {\renewcommand{\arraystretch}{1.1}
    \begin{tabular}{c*{3}{c}c}
    $i$              &amp; $\pi_i$ &amp; $\mu_i$ &amp; $\phi_8(\pi_i)$ \\
    \hline
        1    &amp; (1)              &amp; 1     &amp; 56130437228687557907788  \\
        2    &amp; (12)             &amp; 28    &amp; 101627867809333596  \\
        3    &amp; (123)            &amp; 112   &amp; 262808891710  \\
        4    &amp; (1234)           &amp; 420   &amp; 424234996  \\
        5    &amp; (12345)          &amp; 1344  &amp; 531708  \\
        6    &amp; (123456)         &amp; 3360  &amp; 144320  \\
        7    &amp; (1234567)        &amp; 5760  &amp; 3858  \\
        8    &amp; (12345678)       &amp; 5040  &amp; 2364  \\
        9    &amp; (12)(34)         &amp; 210   &amp; 182755441509724  \\
        10   &amp; (12)(345)        &amp; 1120  &amp; 401622018  \\
        11   &amp; (12)(3456)       &amp; 2520  &amp; 93994196  \\
        12   &amp; (12)(34567)      &amp; 4032  &amp; 21216  \\
        13   &amp; (12)(345678)     &amp; 3360  &amp; 70096  \\
        14   &amp; (123)(456)       &amp; 1120  &amp; 535426780  \\
        15   &amp; (123)(4567)      &amp; 3360  &amp; 25168  \\
        16   &amp; (123)(45678)     &amp; 2688  &amp; 870  \\
        17   &amp; (1234)(5678)     &amp; 1260  &amp; 3211276  \\
        18   &amp; (12)(34)(56)     &amp; 420   &amp; 7377670895900  \\
        19   &amp; (12)(34)(567)    &amp; 1680  &amp; 16380370  \\
        20   &amp; (12)(34)(5678)   &amp; 1260  &amp; 37834164  \\
        21   &amp; (12)(345)(678)   &amp; 1120  &amp; 3607596  \\
        22   &amp; (12)(34)(56)(78) &amp; 105   &amp; 2038188253420  \\
        
        \hline
    \end{tabular}}
    \[ r_8 = \frac{1}{40320} \sum_{i=1}^{k = 22} \mu_i \phi_8(\pi_i) = 1392195548889993358 \]
    \caption{Detailed calculation results for $r_8$.} \label{tab:r8results}
    \end{table}
    
    
\begin{thebibliography}{99}

    \bibitem{assarpour}
    {A. Assarpour},
    \emph{List, Sample, and Count},
    Ph.D.\ thesis, CUNY Graduate Center, 2018.
    Available at
    \url{https://academicworks.cuny.edu/gc_etds/2869}.
    
    \bibitem{Bakoev} V. Bakoev, One more way for counting monotone Boolean functions, in {\em Thirteenth International Workshop on Algebraic and Combinatorial Coding Theory}, Pomorie, Bulgaria (2012), pp.\ 47--52. Available at \url{http://www.moi.math.bas.bg/moiuser/~ACCT2012/b8.pdf}. 

    \bibitem{campo}
    F. a Campo, Relations between powers of Dedekind numbers and exponential sums related to them, \emph{J. Integer Sequences} {\bf 21} (2018),
    \href{https://cs.uwaterloo.ca/journals/JIS/VOL21/Campo/campo3.html}{Article 18.4.4}.

    \bibitem{Ch1985}
C. C. Liu and S. B. Hu, A mechanical algorithm of equivalent
classification for free distributive lattices, \emph{Chinese J. Comput.}
{\bf 3} (2) (1985), 128--135.   In Chinese.

    \bibitem{Ch1986}
C. C. Liu and S. B. Hu, A note on the problem of computing the number
of equivalence classes of free distributive lattices, \emph{J. Wuhan
Univ. Natur. Sci. Ed.} (1986), no.~1, 13--17.   in Chinese.

    \bibitem{drube}
    P. Drube and P. Pongtanapaisan, Annular non-crossing matchings, \emph{J. Integer Sequences} {\bf 19} (2016),
    \href{https://cs.uwaterloo.ca/journals/JIS/VOL19/Drube/drube3.html}{Article 16.2.4}.

    \bibitem{earl2014}
    R. Earl, Groups and group actions, lecture notes. Available at \url{https://courses-archive.maths.ox.ac.uk/node/view_material/43836}.

    \bibitem{Fid2001}
    R. Fidytek, A. W. Mostowski, R. Somla, and A. Szepietowski,
    Algorithms counting monotone Boolean functions,
    \emph{Inform. Process. Lett.}
    {\bf 79} (2001), 203--209.

    \bibitem{oeis}
    N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences,
    2022.  Available at \url{https://oeis.org}.

    \bibitem{r7}
    T. Stephen and T. Yusun, Counting inequivalent monotone Boolean functions, \emph{Discrete Appl. Math.}, {\bf 167} (2014), 15--24.
    
    \bibitem{Wied1991} D. Wiedemann, A computation of the eighth Dedekind number, {\em Order} {\bf 8} (1991), 5--6.
    
    \end{thebibliography}

    \bigskip
    \hrule
    \bigskip
    
    \noindent 
    2010 \emph{Mathematics Subject Classification}:~Primary 06E30.
    
    \medskip
    
    \noindent 
    \emph{Keywords}:~Dedekind number,
    monotone Boolean function,
    inequivalent monotone Boolean function.
    
    \bigskip
    \hrule
    \bigskip
    
    \noindent 
    (Concerned with sequences 
\seqnum{A000041},
\seqnum{A000372},
\seqnum{A003182}, and
\seqnum{A181897}.)
    
\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received March 29 2022;
revised versions received  April 6 2022; August 15 2022; August 19 2022; August 23 2022; August 31 2022.
Published in {\it Journal of Integer Sequences}, September 21 2022.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                

</pre></body></html>