\documentclass[12pt,reqno]{article}
\usepackage{comment}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage{bm}
\usepackage{enumitem}
\usepackage{longtable}  
\usepackage{multirow}   
\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}
\DeclareMathOperator{\sig}{sig}
\DeclareMathOperator{\wt}{wt}
\DeclareMathOperator{\nd}{nd}
\DeclareMathOperator{\BM}{BM}
\DeclareMathOperator{\BU}{BU}
\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}}}
\newcommand{\sym}[1]{{\sf #1}}

\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  
Counting Unate and Monotone Boolean\\
Functions Under Restrictions of \\
\vskip .13in
Balancedness and Non-Degeneracy}
\vskip 1cm
\large
Aniruddha Biswas and Palash Sarkar\\
Indian Statistical Institute \\
203, B.T.Road\\
Kolkata 700108\\
India \\
\href{mailto:email}{\tt aniruddhabiswas535@gmail.com} \\
\href{mailto:email}{\tt palash@isical.ac.in} \\
\end{center}

\vskip .2 in

\begin{abstract}
	We consider the problem of counting the numbers of functions in various sub-classes of unate and monotone Boolean functions under the restrictions of 
balancedness and non-degeneracy. Further, we also consider the problem of counting the numbers of inequivalent and NPN-inequivalent functions in these sub-classes.
\end{abstract}

\section{Introduction \label{sec-intro} }
For a positive integer $n$, an $n$-variable Boolean function $f$ is a map $f:\{0,1\}^n\rightarrow \{0,1\}$. A Boolean function $f$ is said to be  monotone increasing
(resp., decreasing) in the $i$-th variable if 
$$f(x_1,\ldots,x_{i-1},0,x_{i+1},\ldots,x_n)\leq f(x_1,\ldots,x_{i-1},1,x_{i+1},\ldots,x_n)$$ 
$$(\mbox{resp., }f(x_1,\ldots,x_{i-1},0,x_{i+1},\ldots,x_n)\geq f(x_1,\ldots,x_{i-1},1,x_{i+1},\ldots,x_n))$$
for all possible $x_1,\ldots,x_{i-1},x_{i+1},\ldots,x_n\in\{0,1\}$. 

The function $f$ is said to be {\it locally monotone} or {\it unate}, if for each $i\in \{1,\ldots,n\}$, it is either monotone increasing or monotone decreasing in the $i$-th
variable. The function $f$ is said to be {\it monotone increasing} (or, simply {\it monotone}) if for each $i\in \{1,\ldots,n\}$, it is monotone increasing in the $i$-th variable.

A Boolean function is {\it degenerate} on some variable if its output does not depend on the variable, and it is said to be {\it non-degenerate} if it is not degenerate on any of the
variables. A Boolean function is said to be {\it balanced} if it takes the values 0 and 1 equal number of times. 
The number of $n$-variable balanced Boolean functions is ${2^n\choose 2^{n-1}}$ (see \seqnum{A037293}).

The number of $n$-variable monotone Boolean functions, denoted as $D(n)$, is said to be the $n$-th {\it Dedekind number} after Dedekind~\cite{Dedekind1897103} who posed the problem of counting the number of $n$-variable monotone Boolean functions 
in 1897. The value of $D(n)$ is known for $n\leq 9$ (see~\cite{ListINtSequence,Dedekind1897103,Church,Ward,berman,Wiedemann19915,DBLP:journals/ipl/FidytekMSS01,jakel2023computation,vanhirtum2023computation} and \seqnum{A000372}). 
Kisielewicz~\cite{Kisielewicz1988139} gave a closed form summation formula for $D(n)$. However, Korshunov~\cite{Korshunov2003929} pointed out that using the formula to compute 
$D(n)$ has the same complexity as direct enumeration of all $n$-variable monotone Boolean functions. 
The inverse binomial transform of $D(n)$ gives the number of $n$-variable non-degenerate monotone Boolean functions and hence the latter quantities are 
also known for $n\leq 9$ (see \seqnum{A006126}). 

Two Boolean functions on the same number of variables are said to be {\it equivalent} if one can be obtained from the other by a permutation of variables. Two Boolean functions on the same number of variables are said to be {\it NPN-equivalent} if one can be obtained from the other by a combination of the following operations:
a permutation of the variables, negation of a subset of the variables, and negation of the output.
Both of the above two notions of equivalence partition the set of all $n$-variable Boolean functions into equivalence classes. The number of equivalence classes is also said to be
the number of inequivalent functions under the appropriate notion of equivalence. 
It is of interest to count the number of inequivalent Boolean functions satisfying some prescribed properties. 
For example, the number of inequivalent $n$-variable monotone Boolean functions is known for $n$ up to $9$ 
(see~\seqnum{A003182}, Stephen and Yusun~\cite{STEPHEN201415} and Pawelski~\cite{DBLP:journals/tit/Pawelski24}). 
Another example is the number of $n$-variable NPN-inequivalent unate functions (see \seqnum{A003183} and Baugh \cite{baugh72}). 

The focus of the present work is on counting unate and monotone Boolean functions under various restrictions. 
For $n\leq 5$, it is possible to enumerate all $n$-variable Boolean functions. Consequently, the problem of counting various sub-classes of $n$-variable
Boolean functions become a reasonably simple problem. Non-triviality of counting Boolean functions arises for $n\geq 6$. 

The problem of counting unate functions reduces to the problem of counting monotone Boolean functions. This follows from the work of Baumann and 
Strass~\cite{DBLP:journals/logcom/BaumannS17}. (We were unaware of the work of Baumann and Strass when we obtained the relation between the numbers of unate and 
monotone Boolean functions.) Since the numbers of $n$-variable monotone Boolean functions are known for $n\leq 9$, these values provide the numbers of $n$-variable unate 
functions for $n\leq 9$. The numbers of $n$-variable unate functions are available from \seqnum{A245079}. We updated \seqnum{A245079} by providing the value for $n=9$ and 
correcting the values for $n=7$ and $n=8$.

We show that the problem of counting balanced unate functions reduces to the problem of counting balanced monotone Boolean functions. The number of $n$-variable balanced 
monotone Boolean functions is known for $n\leq 7$ (see \seqnum{A341633} and Church~\cite{church1965enumeration}). Consequently, we obtain the numbers of $n$-variable balanced 
unate functions for $n\leq 7$. We further extend these results to obtain the numbers of non-degenerate balanced monotone Boolean functions, non-degenerate unate functions, 
and non-degenerate balanced unate functions. 

Unlike the situation for counting functions, the problem of counting the number of inequivalent unate functions does not reduce to the problem of counting the number of 
inequivalent monotone Boolean functions. So to count the number of inequivalent unate functions, we used a method to generate all $n$-variable unate functions and applied a 
filtering to the obtained set. This allowed us to obtain the numbers of inequivalent $n$-variable unate and balanced unate functions for $n\leq 6$. Moreover, we obtain the numbers of inequivalent $n$-variable balanced monotone Boolean functions, non-degenerate balanced monotone Boolean functions, non-degenerate unate 
functions, and non-degenerate balanced unate functions for $n\leq 6$. 

The results that we present for monotone Boolean functions and unate functions are summarized in Table~\ref{tab:counting-results}. For each entry of the table, we provide the
corresponding sequence number of the On-Line Encyclopedia of Integer Sequences (OEIS)~\cite{ListINtSequence}. The word ``New'' in the column 
entitled ``Comment'' indicates that the sequence was added to OEIS based on the present paper, while the word ``Updated'' indicates that the existing entry was updated based
on the present paper.
\subsection{Outline of the paper}
In Section~\ref{sec-math} we describe the preliminaries and prove the mathematical results required to obtain the various counts. In Section~\ref{sec-fn-cnt} we address
the problem of counting various sub-classes of monotone Boolean functions and unate functions and in Section~\ref{sec-enum} we take up the problem of counting the numbers
of inequivalent unate and monotone Boolean functions possessing a combination of several properties. Finally, Section~\ref{sec-conclu} discusses some possible future research
problems.
\section{Mathematical results \label{sec-math} }
We fix some terminology and the notation. The cardinality of a finite set $S$ will be denoted by $\#S$. 
For $x,y\in \{0,1\}$, by $xy$ and $x\oplus y$ we will denote the AND and XOR operations respectively, and by $\overline{x}$ we will denote the complement (or negation) of $x$. 

Elements of $\{0,1\}^n$, for $n\geq 2$, are $n$-bit strings (or vectors) and are denoted using bold font. Given $n\geq 2$ and $1\leq i\leq n$, let $\mathbf{e}_i$
 denote the $n$-bit string whose $i$-th bit is 1 and is 0 elsewhere.

Let $f$ be an $n$-variable Boolean function. 
The {\it weight} $\wt(f)$ of $f$ is the size of its support, i.e., $\wt(f)=\#\{\mathbf{x}: f(\mathbf{x})=1\}$. We can uniquely represent an $n$-variable Boolean function $f$ by a binary string of length $2^n$ in the following manner: for 
$0\leq i<2^n$, the $i$-th bit of the string is the value of $f$ on the $n$-bit binary representation of $i$. We use the same notation $f$ to 
denote the string representation of $f$. So $f_0\cdots f_{2^n-1}$ is the bit string of length $2^n$ that represents $f$.

\begin{table}[H]
\centering
\small
\renewcommand{\arraystretch}{0.9}
\resizebox{0.9\textwidth}{!}{%
\begin{tabular}{|p{4cm}|p{6cm}|p{2cm}|p{2.5cm}|}
\hline
\textbf{Property} & \textbf{Description} & \textbf{OEIS Number} & \textbf{Comment} \\
\hline

\multirow{4}{4cm}{Monotone Boolean Functions} 
& Number of $n$-variable non-degenerate balanced monotone Boolean functions for $n \leq 7$ & \seqnum{A371722} & New \\
\cline{2-4}
& Number of equivalence classes of $n$-variable balanced monotone Boolean functions for $n \leq 7$ & \seqnum{A371717} & New \\
\cline{2-4}
& Number of equivalence classes of $n$-variable non-degenerate balanced monotone Boolean functions for $n \leq 7$ & \seqnum{A371718} & New \\
\cline{2-4}
& Number of NPN-equivalence classes of $n$-variable balanced monotone Boolean functions for $n \leq 6$ & \seqnum{A378300} & New \\
\hline

\multirow{8}{4cm}{Unate Functions} 
& Number of $n$-variable balanced unate functions for $n \leq 7$ & \seqnum{A373690} & New \\
\cline{2-4}
& Number of $n$-variable non-degenerate balanced unate functions for $n \leq 7$ & \seqnum{A373697} & New \\
\cline{2-4}
& Number of inequivalent $n$-variable unate functions for $n \leq 6$ & \seqnum{A372495} & New \\
\cline{2-4}
& Number of inequivalent $n$-variable non-degenerate unate functions for $n \leq 6$ & \seqnum{A374399} & New \\
\cline{2-4}
& Number of inequivalent $n$-variable balanced unate functions for $n \leq 6$ & \seqnum{A374400} & New \\
\cline{2-4}
& Number of inequivalent $n$-variable non-degenerate balanced unate functions for $n \leq 6$ & \seqnum{A374401} & New \\
\cline{2-4}
& Number of $n$-variable unate functions for $n = 7, 8, 9$ & \seqnum{A245079} & Updated \\
\cline{2-4}
& Number of non-degenerate $n$-variable unate Boolean functions for $n = 9$ & \seqnum{A305000} & Updated \\
\hline

\multirow{2}{4cm}{Misc.} 
& Number of non-degenerate $n$-variable balanced Boolean functions & \seqnum{A378302} & New \\
\cline{2-4}
& Number of labeled antichains of finite sets spanning $n = 9$ vertices with singleton edges allowed (obtained as an inverse binomial transform of \seqnum{A305000}). & \seqnum{A304999} & Updated \\
\hline

\end{tabular}
}
	\caption{Summary of new and updated sequences obtained in this work.} \label{tab:counting-results}
\end{table}

Let $\overline{f}$ denote the negation of $f$, i.e., $\overline{f}(\mathbf{x})=1$ if and only if $f(\mathbf{x})=0$. Let
$f^r$ be a Boolean function defined as $f^r(x_1,\ldots,x_n)=f(\overline{x}_1,\ldots,\overline{x}_n)$. The bit string representation of $f^r$ is the
reverse of the bit string representation of $f$. 

Let $g$ and $h$ be two $n$-variable Boolean functions having string representations $g_0\cdots g_{2^n-1}$ and $h_0\cdots h_{2^n-1}$. 
We write $g\leq h$ if $g_i\leq h_i$ for $i=0,\ldots,2^n-1$. From $g$ and $h$, it is possible to construct an $(n+1)$-variable function $f$ whose
string representation is obtained by concatenating the string representations of $g$ and $h$. We denote this construction as $f=g||h$. For
$(x_1,\ldots,x_{n+1})\in\{0,1\}^{n+1}$, we have
\begin{align}\label{eqn-concat}
	f(x_1,\ldots,x_{n+1}) & =  \overline{x}_1g(x_2,\ldots,x_{n+1}) \oplus x_1h(x_2,\ldots,x_{n+1}).
\end{align}

For $n\geq 1$, an $n$-variable Boolean function $f$ is said to be {\it non-degenerate} on the $i$-th variable, for $1\leq i\leq n$, if there is an $\bm{\alpha}\in\{0,1\}^n$ such that
$f(\bm{\alpha})\neq f(\bm{\alpha}\oplus \mathbf{e}_i)$. The function $f$ is said to be non-degenerate if it is non-degenerate on all the $n$ variables.


By a property $\mathcal{P}$ of the set of all Boolean functions, we mean a subset of the set of all Boolean functions. For example, the property $\mathcal{P}$
could be the property of being balanced, being monotone, being unate, being non-degenerate, or a combination of these properties, where a combination of properties
is given by the intersection of the corresponding subsets of Boolean functions. For $n\geq 0$, let $P_n$ denote the number of $n$-variable Boolean functions
possessing the property $\mathcal{P}$, and let $\nd\!\mbox{-}\!P_n$ denote the number of $n$-variable non-degenerate Boolean functions possessing the property
$\mathcal{P}$. Since an $n$-variable function can be non-degenerate on $i$ variables for some $i\in \{0,\ldots,n\}$ and the $i$ variables can be chosen from the
$n$ variables in ${n\choose i}$ ways, we obtain the following result, which shows that the sequence $\{P_n\}_{n\geq 0}$ is given by the binomial transform of 
the sequence $\{\nd\!\mbox{-}\!P_n\}_{n\geq 0}$.
\begin{proposition}\label{prop-nd}
	For every property $\mathcal{P}$ of Boolean functions,
	\begin{align}\label{eqn-nd}
		P_n & = \sum_{i=0}^n {n\choose i} \nd\!\mbox{-}P_i.
	\end{align}
	Consequently,
	\begin{align}\label{eqn-nd-inv}
		\nd\!\mbox{-}P_n & = \sum_{i=0}^n (-1)^{n-i}{n\choose i} P_i.
        \end{align}
\end{proposition}

For $n\geq 0$, let $A_n=2^{2^n}$ be the number of all $n$-variable Boolean functions, and let $B_n={2^n\choose 2^{n-1}}$ be the number
of $n$-variable balanced Boolean functions. Let $\nd\!\mbox{-}\!A_n$ be the number of all non-degenerate $n$-variable Boolean functions, and $\nd\!\mbox{-}\!B_n$ 
be the number of all non-degenerate $n$-variable balanced Boolean functions. Using Proposition~\ref{prop-nd}, we obtain

$$\nd\!\mbox{-}\!A_n = \sum_{i=0}^n (-1)^{n-i}{n\choose i} \cdot 2^{2^i} \quad \text{and} \quad \nd\!\mbox{-}\!B_n = \sum_{i=0}^n (-1)^{n-i}{n\choose i} \cdot {2^i\choose 2^{i-1}}$$.

The entry for the number of non-degenerate $n$-variable Boolean functions is already in OEIS (\seqnum{A000618}). Using the 
above formula, we obtain the number of nondegenerate balanced Boolean functions of $n$ variables (see Table~\ref{tab-nd-balanced-Boolean}).
\begin{remark}\label{rem-BS-sp-case}
	Baumann and Strass~\cite{DBLP:journals/logcom/BaumannS17} (see Proposition~10 and Corollary~11) proved the special case of Proposition~\ref{prop-nd} where 
	$\mathcal{P}$ is the property of being monotone.
\end{remark}

\begin{table}
\centering
	{\scriptsize
	\begin{tabular}{|c|r|}
		\hline
		$n$ & \multicolumn{1}{c|}{$\nd\!\mbox{-}\!B_n$} \\\hline
		0 & 0\\ \hline
		1 & 2\\ \hline
		2 & 2\\ \hline
		3 & 58\\ \hline
		4 & 12618\\ \hline
		5 & 601016690\\ \hline
		6 & 1832624137336299922\\ \hline
        7 & 23951146041928082853307218802404658090\\ \hline
        8 & 5768658823449206338089748357862286887548602533639737369730665340966207267034\\ \hline
	\end{tabular}
	\caption{Number of non-degenerate $n$-variable balanced Boolean functions for $0 \leq n \leq 8$ [\seqnum{A378302}].}
	\label{tab-nd-balanced-Boolean}
	}
\end{table}

For $n\geq 0$, let $M_n$, $\BM_n$, $U_n$, and $\BU_n$, denote the numbers of $n$-variable monotone, balanced-monotone, unate, and balanced-unate Boolean functions
respectively, and further let $\nd\!\mbox{-}\!M_n$, $\nd\!\mbox{-}\!\BM_n$, $\nd\!\mbox{-}U_n$, and $\nd\!\mbox{-}\!\BU_n$, denote the corresponding numbers
of non-degenerate functions. The relations between the number of $n$-variable functions possessing one of these properties and the number of non-degenerate
$n$-variable functions possessing the corresponding property are obtained from Proposition~\ref{prop-nd}. Note that $M_n$ is the $n$-th Dedekind number $D(n)$.

The following result relates the numbers of monotone and unate Boolean functions.
\begin{proposition}
\label{prop-m-u}
For $n\geq 0$, the following holds.
        \begin{align}
        \nd\!\mbox{-}U_n & = 2^n \cdot \nd\!\mbox{-}M_n, \label{eqn-m-u-nd} \\
        \nd\!\mbox{-}\!\BU_n & = 2^n \cdot \nd\!\mbox{-}\!\BM_n, \label{eqn-m-u-b-nd} \\
        U_n & \leq 2^n \cdot M_n, \label{eqn-m-u} \\
     \BU_n & \leq 2^n \cdot \BM_n. \label{eqn-m-u-b}
       \end{align}

\end{proposition}
\begin{proof}
	First we consider~\eqref{eqn-m-u-nd} and~\eqref{eqn-m-u-b-nd}. We prove~\eqref{eqn-m-u-nd}, the proof of~\eqref{eqn-m-u-b-nd} being similar. 

	Let $f$ be an $n$-variable monotone Boolean function. Then it is easy to see that for every $\bm{\alpha}\in\{0,1\}^n$, the $n$-variable function
	$f_{\bm{\alpha}}$ is unate, where $f_{\bm{\alpha}}$ is defined as $f_{\bm{\alpha}}(\mathbf{x})=f(\mathbf{x}\oplus \bm{\alpha})$ for all $\mathbf{x}\in \{0,1\}^n$. 
	The proof of~\eqref{eqn-m-u-nd} follows from the following claim.

	\vspace{5pt}
	
	\noindent{\em Claim:} If $f$ is monotone Boolean function, then the $2^n$ possible functions $f_{\bm{\alpha}}$ corresponding to the $2^n$ possible $\bm{\alpha}$'s are 
	distinct if and only if $f$ is non-degenerate. 
	
	\vspace{5pt}
	
	\noindent{\em Proof of the claim:} 
	Suppose $f$ is degenerate on the $i$-th variable. Then $f$ and $f_{\mathbf{e}_i}$ are equal. This proves one side of the claim. 
	So suppose that $f$ is non-degenerate. We have to show that for $\bm{\alpha}\neq \bm{\beta}$, $f_{\bm{\alpha}}$ and $f_{\bm{\beta}}$ are distinct. 
	Let if possible $f_{\bm{\alpha}}$ and $f_{\bm{\beta}}$ be equal.
	Note that since $f$ is non-degenerate, both $f_{\bm{\alpha}}$ and $f_{\bm{\beta}}$ are also non-degenerate. 
	Since $\bm{\alpha}=(\alpha_1,\ldots,\alpha_n)$ and $\bm{\beta}=(\beta_1,\ldots,\beta_n)$ are distinct, there is a $j$ in $\{1,\ldots,n\}$ such that $\alpha_j\neq \beta_j$. 
	Suppose without loss of generality that $\alpha_j=0$ and $\beta_j=1$. Since $f$ is monotone, it is monotone increasing in all variables and hence in the $j$-th
	variable. Further, since $\alpha_j=0$, the function $f_{\bm{\alpha}}$ is monotone increasing in the $j$-th variable and since $\beta_j=1$, the function $f_{\bm{\beta}}$ is monotone
	decreasing in the $j$-th variable. Since $f_{\bm{\alpha}}$ is monotone increasing in the $j$-th variable, for all 
	$\mathbf{y}=(y_1,\ldots,y_n)\in \{0,1\}^n$ with $y_j=0$, we have $f_{\bm{\alpha}}(\mathbf{y})\leq f_{\bm{\alpha}}(\mathbf{y}\oplus \mathbf{e}_j)$. Further, since
	$f_{\bm{\alpha}}$ is non-degenerate, in particular it is non-degenerate on the $j$-th variable. Therefore, equality cannot hold everywhere, i.e., there is a 
	$\mathbf{z}=(z_1,\ldots,z_n)\in \{0,1\}^n$ with $z_j=0$, such that 
	$f_{\bm{\alpha}}(\mathbf{z})=0$ and $f_{\bm{\alpha}}(\mathbf{z}\oplus \mathbf{e}_j)=1$. Since $f_{\bm{\alpha}}$ and $f_{\bm{\beta}}$ are assumed to be equal,
	it follows that $f_{\bm{\beta}}(\mathbf{z})=0$ and $f_{\bm{\beta}}(\mathbf{z}\oplus \mathbf{e}_j)=1$. This contradicts the fact that 
	$f_{\bm{\beta}}$ is monotone decreasing in the $j$-th variable, and proves the claim. 

	Next we consider~\eqref{eqn-m-u} and~\eqref{eqn-m-u-b}. We provide the proof of~\eqref{eqn-m-u}, and the proof of~\eqref{eqn-m-u-b} being similar.
From~\eqref{eqn-m-u-nd} and Proposition~\ref{prop-nd} we obtain~\eqref{eqn-m-u} using the following calculation.
\begin{align}
U_n & =  \sum_{i=0}^{n} {n\choose i} \nd\!\mbox{-}U_i = \sum_{i=0}^{n} {n\choose i} \cdot 2^i \cdot \nd\!\mbox{-}\!M_i \label{eqn-u-n} \\
& \leq  2^n \cdot \sum_{i=0}^{n} {n\choose i} \nd\!\mbox{-}\!M_i = 2^n\cdot M_n. \nonumber
\end{align}
\end{proof}

\subsection{Relation to the results of Baumann and Strass}
	Corollary~7 of Baumann and Strass~\cite{DBLP:journals/logcom/BaumannS17} states~\eqref{eqn-u-n}. Baumann and Strass obtain Corollary~7 from Theorem~5 and Proposition~6
	of their paper. (Baumann and Strass state Theorem~5 to be the main result of their paper.)
	The approach of Baumann and Strass to prove~\eqref{eqn-u-n} is different from our approach.
	As a result, the proofs of Theorem~5 and Proposition~6 in Baumann and Strass' paper are quite a bit longer than the direct and simpler proof of Proposition~\ref{prop-m-u}.


Baumann and Strass~\cite{DBLP:journals/logcom/BaumannS17} provide an informal argument that suggests that~\eqref{eqn-m-u-nd} holds. 
In particular, after Corollary~11, Baumann and Strass mentioned the following.
\begin{quote}
bipolar Boolean functions have two choices for each non-redundant argument, namely, it can be either monotone or anti-monotone. Consequently, in case of $i$
non-redundant arguments we have to consider the additional factor $2^i$. 
\end{quote}
We note that while the above suggests that~\eqref{eqn-m-u-nd} holds, it is not sufficient to prove~\eqref{eqn-m-u-nd}. There are subtleties to the counting argument that
the proof of the claim in Proposition~\ref{prop-m-u} covers.

Finally, we note that Baumann and Strass~\cite{DBLP:journals/logcom/BaumannS17} did not obtain~\eqref{eqn-m-u-b-nd}, which gives the relation between non-degenerate balanced 
unate functions and non-degenerate balanced monotone Boolean functions.

Next, we record two known facts about monotone Boolean functions. 
\begin{proposition}[Bakoev~\cite{mono_gen}]\label{fact_mono}
Let $g$ and $h$ be $n$-variable Boolean functions and $f=g||h$. Then $f$ is a monotone Boolean function if and only if $g$ and $h$ are both monotone Boolean functions 
and $g\leq h$.   
\end{proposition}
\begin{proposition}[\seqnum{A003183}]\label{fact_2}
	If $f$ is a monotone Boolean function, then $\overline{f^{r}}$ is also a monotone Boolean function.
\end{proposition}

Before proceeding further, we present some results on unate and monotone Boolean functions that are useful in our enumeration strategy. 
The first result is the analog of Proposition~\ref{fact_mono} for unate functions.
\begin{proposition}\label{unate_proposition}
Let $g$ and $h$ be $n$-variable functions and $f=g||h$. Then $f$ is an unate function if and only if $g$ and $h$ are both unate functions satisfying the following
	two conditions.
	\begin{enumerate}[label=(\alph*)]
		\item For each variable, both $g$ and $h$ are either monotone increasing, or both are monotone decreasing. 
		\item Either $g\leq h$ or $h\leq g$.      
	\end{enumerate}
\end{proposition}
\begin{proof}
	First, consider the proof of the ``if'' part. Suppose $g$ and $h$ are unate functions satisfying the stated condition. We have to show that for each variable,
	$f$ is either monotone increasing, or monotone decreasing. Consider the variable $x_1$. If $g\leq h$, then from~\eqref{eqn-concat},
	$f$ is monotone increasing on $x_1$, while if $g\geq h$, then again from~\eqref{eqn-concat}, it follows that $f$ is monotone decreasing on $x_1$. Now consider
	a variable $x_i$, with $i\geq 2$. If $g$ and $h$ are both monotone increasing on $x_i$, then $f$ is also monotone increasing on $x_i$, while if $g$ and $h$ are 
	both monotone decreasing on $x_i$, then $f$ is also monotone decreasing on $x_i$. Since for each variable, $f$ is either monotone increasing, or
	monotone decreasing, it follows that $f$ is a unate function.

	For the converse, suppose that $f$ is a unate function. Then for each variable $x_i$, where $i\geq 1$, $f$ is either monotone increasing or monotone decreasing. 
	From~\eqref{eqn-concat}, it
	follows that for each variable $x_i$, where $i\geq 2$, $g$, and $h$ are either both monotone increasing, or both monotone decreasing. So, in particular, $g$ and $h$ are
	unate. If $f$ is monotone increasing for $x_1$, then $g\leq h$ and if $f$ is monotone decreasing for $x_1$, then $g\geq h$. 
\end{proof}

\begin{proposition}\label{prop2} 
	If $f$ is a unate function then $\overline{f}$ is also a unate function. 
\end{proposition}
\begin{proof}
	The proof is by induction on the number of variables $n$. The base case is $n=1$ and is trivial. Suppose the result holds for some $n\geq 1$. 
	Suppose that $f$ is an $(n+1)$-variable unate function. Then $f$ can be written as $f=g||h$, where $g$ and $h$ are $n$-variable unate functions satisfying the conditions
	in Proposition~\ref{unate_proposition}. Then $\overline{f}=\overline{g}||\overline{h}$. By induction hypothesis, $\overline{g}$ and $\overline{h}$
	are $n$-variable unate functions and the conditions in Proposition~\ref{unate_proposition} hold for $\overline{g}$ and $\overline{h}$. So $\overline{f}$ is
	a unate function.
\end{proof}

For $0\leq w\leq 2^n$, let $M_{n,w}$ (resp., $U_{n,w}$) be the number of $n$-variable monotone (resp., unate) Boolean functions of weight $w$.

\begin{proposition}\label{prop4}
    For every $n\geq 1$ and weight $w\in[0,2^n]$,  we have $M_{n,w}=M_{n,2^n-w}$. 
\end{proposition}
\begin{proof}
	Proposition~\ref{fact_2} sets up a one-one correspondence between $n$-variable monotone Boolean functions having weight $w$ and $n$-variable monotone Boolean functions having weight $2^n-w$. 
	This shows that $M_{n,w}=M_{n,2^n-w}$.
\end{proof}

\begin{proposition}\label{prop3}
    For every $n\geq 1$ and weight $w\in[0,2^n]$, we have $U_{n,w}=U_{n,2^n-w}$. 
\end{proposition}
\begin{proof}
	Proposition~\ref{prop2} sets up a one-one correspondence between $n$-variable unate functions having weight $w$ and $n$-variable unate functions having weight $2^n-w$. 
	This shows that $U_{n,w}=U_{n,2^n-w}$.
\end{proof}

\subsection{Equivalence \label{subsec-eq}}
We recall the definition of equivalence of Boolean functions. Two Boolean functions are said to be {\it equivalent} if they have the same number of variables and one can be obtained 
from the other by a permutation of variables. Let $\mathcal{P}$ be a property of Boolean functions. The set $\mathcal{P}$ is partitioned into equivalence classes by the notion of
equivalence. For $n\geq 0$, let $[P]_n$ denote the number of equivalence classes of $n$-variable functions possessing the property $\mathcal{P}$.
Also, let $\nd\!\mbox{-}[P]_n$ denote the number of equivalence classes of non-degenerate $n$-variable functions possessing the property $\mathcal{P}$.

\begin{remark}\label{rem-n=0=eq}
	We assume that for $n=0$, there are two equivalence classes of $n$-variable, non-degenerate, monotone (and hence unate), and unbalanced Boolean functions given 
	by $[0]$ and $[1]$. 
\end{remark}

We have the following analog of Proposition~\ref{prop-nd}.
\begin{proposition}\label{prop-nd-eq}
	Let $\mathcal{P}$ be a property of Boolean functions that is closed under permutation of variables (i.e., if $f$ is in $\mathcal{P}$ and $g$ is obtained
	from $f$ by applying a permutation to the variables, then $g$ is also in $\mathcal{P}$). Then 
	\begin{align}\label{eqn-nd-eq}
		[P]_n & =  \sum_{i=0}^n \nd\!\mbox{-}[P]_i.
	\end{align}
	Consequently, we have $\nd\!\mbox{-}[P]_n = [P]_n - [P]_{n-1}$.
\end{proposition}

For $n\geq 0$, let $[A]_n$ denote the number of equivalence classes of $n$-variable Boolean functions and $[B]_n$ denote the number of equivalence classes of $n$-variable
balanced Boolean functions. The values of $[A]_n$ and $[B]_n$ can be obtained using Polya's theory (see for example Roberts and Tesman~\cite[Sec.\ 8.3, p.\ 457]{RT09}). Let
$\nd\!\mbox{-}[A]_n$ denote the number of equivalence classes of $n$-variable non-degenerate Boolean functions and $\nd\!\mbox{-}[B]_n$ denote the
number of equivalence classes of $n$-variable non-degenerate balanced Boolean functions. Using Proposition~\ref{prop-nd-eq}, it follows that 
$\nd\!\mbox{-}[A]_n=[A]_n - [A]_{n-1}$ and $\nd\!\mbox{-}[B]_n=[B]_n - [B]_{n-1}$.

For $n\geq 0$, let $[M]_n$, $[\BM]_n$, $[U]_n$ and $[\BU]_n$ denote the numbers of equivalence classes of $n$-variable monotone, balanced-monotone, unate, and 
balanced-unate functions respectively and let 
$\nd\!\mbox{-}[M]_n$, $\nd\!\mbox{-}[\BM]_n$, $\nd\!\mbox{-}[U]_n$, and $\nd\!\mbox{-}[\BU]_n$  denote the corresponding numbers of equivalence classes of non-degenerate functions. 
The following result is the analogue of Proposition~\ref{prop-m-u}. 
\begin{proposition}\label{prop-m-u-eq}
For $n\geq 0$, the following holds.
	\begin{align}
		\nd\!\mbox{-}[U]_n & \leq  2^n \cdot \nd\!\mbox{-}[M]_n, \label{eqn-m-u-nd-eq} \\
		\nd\!\mbox{-}[\BU]_n & \leq  2^n \cdot \nd\!\mbox{-}[\BM]_n, \label{eqn-m-u-nd-b-eq} \\
		\mbox{$[U]$}_n & \leq  2^n \cdot [M]_n, \label{eqn-m-u-eq} \\
		\mbox{$[\BU]$}_n & \leq  2^n \cdot [\BM]_n, \label{eqn-m-u-b-eq} 
	\end{align}
\end{proposition}
The relations given by~\eqref{eqn-m-u-eq} and~\eqref{eqn-m-u-b-eq} are analogues of~\eqref{eqn-m-u} and~\eqref{eqn-m-u-b} respectively. 
However, unlike~\eqref{eqn-m-u-nd} and~\eqref{eqn-m-u-b-nd}, we do not have equality in~\eqref{eqn-m-u-nd-eq} and~\eqref{eqn-m-u-nd-b-eq}.
The reason is that two distinct input translations of a non-degenerate monotone Boolean function can lead to two unate functions that are equivalent.
An example is the following. Suppose $f(X_1,X_2)=X_1X_2$, i.e., $f$ is the AND function. Let $g(X_1,X_2)=f(1\oplus X_1, X_2)=(1\oplus X_1)X_2$ and 
$h(X_1,X_2)=f(X_1,1\oplus X_2)=X_1(1\oplus X_2)$. Then $g(X_1,X_2)=h(X_2,X_1)$, i.e., $g$ and $h$ are distinct, but equivalent unate functions obtained 
by distinct input translations from the monotone Boolean function $f$.

Let $f$ and $g$ be two $n$-variable Boolean functions. We say that $f$ and $g$ are {\it NN-equivalent} if one can be obtained from the other by some combination
of the following two operations: negation of a subset of the inputs, and negation of the output.
\begin{proposition}\label{prop-NN-mono}
Let $f$ and $g$ be two $n$-variable monotone Boolean functions. Then $f$ is NN-equivalent to $g$ if and only if either $f=g$ or $g$ is obtained from $f$
by negation of the output and negation of all the variables on which $f$ is non-degenerate.

Consequently, every NN-equivalence class of $n$-variable monotone Boolean functions contains exactly two functions.
\end{proposition}
\begin{proof}
The ``if'' part follows from the definition of NN-equivalence, and we only need to prove the ``only if'' part. So suppose that $f$ is NN-equivalent to $g$ and assume
	$f\neq g$ (as otherwise there is nothing to prove). 

	If $f$ is degenerate on some variable, then negating this variable does not change $f$. So we need to consider only the variables on which $f$ is non-degenerate.

	If $f$ is the constant function 0 (resp., 1), then $g$ is necessarily the constant function 1 (resp., 0). Next, suppose $f$ is non-degenerate on exactly one
	variable, say $X_1$. Since $g\neq f$ and $g$ is NN-equivalent to $f$, there are three possibilities for $g$, namely 
	$1\oplus f(X_1,\ldots)$, $f(1\oplus X_1,\ldots)$ and $1\oplus f(1\oplus X_1,\ldots)$. Using the fact that $f$ is monotone, it is easy to argue that the
	first two possibilities do not give rise to monotone Boolean functions, while the third possibility is a monotone Boolean function. Since $g$ is also monotone, it follows
	that $g$ must be equal to $1\oplus f(1\oplus X_1,\ldots)$.
	Now suppose that $f$ is non-degenerate on exactly two variables, say $X_1$ and $X_2$. Since $g\neq f$ and $g$ is NN-equivalent to $f$, there are seven
	possibilities for $g$. Among these, only $1\oplus f(1\oplus X_1,1\oplus X_2,\ldots)$ is monotone, while the other six are not. In more details,
	$f(1\oplus X_1,X_2,\ldots)$ is not monotone on $X_1$, 
	$f(X_1,1\oplus X_2,\ldots)$ is not monotone on $X_2$,
	$f(1\oplus X_1,1\oplus X_2,\ldots)$ is not monotone on both $X_1$ and $X_2$,
	$1\oplus f(1\oplus X_1,X_2,\ldots)$ is not monotone on $X_2$, 
	$1\oplus f(X_1,1\oplus X_2,\ldots)$ is not monotone on $X_1$, and
	$1\oplus f(X_1,X_2,\ldots)$ is not monotone on both $X_1$ and $X_2$.
	The above argument easily extends to the case where $f$ is non-degenerate on $r\geq 1$ variables giving us the desired result.
\end{proof}

\begin{proposition}\label{prop-NN-unate-mono}
	The following holds.
	\begin{enumerate}[label=(\alph*)]
		\item For $n\geq 0$, the number of NN-inequivalent $n$-variable unate functions is equal to the number of NN-inequivalent $n$-variable monotone Boolean 
			functions. Consequently, the number of NPN-inequivalent $n$-variable unate functions is equal to the number of NPN-inequivalent $n$-variable
			monotone Boolean functions.
		\item For $n\geq 0$, the number of NN-inequivalent $n$-variable balanced unate functions is equal to the number of NN-inequivalent $n$-variable balanced 
			monotone Boolean functions. Consequently, the number of NPN-inequivalent $n$-variable balanced unate functions is equal to the number of 
			NPN-inequivalent $n$-variable balanced monotone Boolean functions.
	\end{enumerate}
\end{proposition}
\begin{proof}
We prove only the first point since the proof of the second point is similar. 

For every $n$-variable unate function $f$, by appropriately negating some of the inputs and also possibly the output, we obtain a monotone Boolean function $g$. This sets up
a one-one correspondence between the class of NN-equivalent unate functions containing $f$ and the class of NN-equivalent monotone Boolean functions containing $g$. So
the number of NN-inequivalent $n$-variable unate functions is equal to the number of NN-inequivalent $n$-variable monotone Boolean functions. 
	
The result on NPN-inequivalent functions follows since the one-one correspondence described above continues to hold when the notion of equivalence is extended by 
also considering the permutation of input variables.
\end{proof}

\section{Counting functions \label{sec-fn-cnt}}
In this section, we consider the problem of counting various sub-classes of monotone and unate Boolean functions.

\subsection{Monotone Boolean functions \label{subsec-fn-cnt-monotone}}
The values of $\BM_n$ are known for $n\leq 7$ (see \seqnum{A341633}). From these values, using Proposition~\ref{prop-nd}, we can obtain the values of $\nd\!\mbox{-}\!\BM_n$ for $n\leq 7$.
We present the obtained values of $\nd\!\mbox{-}\!\BM_n$ in Table~\ref{tab-b-m}.
\begin{table}
\centering
	{
	\begin{tabular}{|c|r|r|}
		\hline
		$n$ & \multicolumn{1}{c|}{$\BM_n$} & \multicolumn{1}{c|}{$\nd\!\mbox{-}\!\BM_n$} \\ \hline
		0 & 0 & 0\\ \hline
		1 & 1 & 1\\ \hline
		2 & 2 & 0\\ \hline
		3 & 4 & 1\\ \hline
		4 & 24 & 16\\ \hline
		5 & 621 & 526  \\ \hline
		6 & 492288 & 488866  \\ \hline
		7 & 81203064840 & 81199631130 \\ \hline
	\end{tabular}
	\caption{Number of $n$-variable balanced monotone and non-degenerate balanced monotone Boolean functions for $0\leq n\leq 7$ [\seqnum{A341633}, \seqnum{A371722}]. \label{tab-b-m}}
	}
\end{table}

\subsection{Unate functions \label{subsec-unate-cnt}}
Baumann and Strass~\cite{DBLP:journals/logcom/BaumannS17} showed that the problem of counting unate functions reduces to the problem of counting monotone Boolean functions.
Using Proposition~\ref{prop-nd}, this reduction can be seen as follows. First note that obtaining $U_n$ reduces to the problem of obtaining $\nd\!\mbox{-}U_i$, for 
$0\leq i\leq n$. From~\eqref{eqn-m-u-nd}, obtaining $\nd\!\mbox{-}U_i$ reduces to the problem of obtaining $\nd\!\mbox{-}\!M_i$ for $0\leq i\leq n$. Another application
of Proposition~\ref{prop-nd} reduces the problem of obtaining $\nd\!\mbox{-}\!M_i$ to that of obtaining $M_j$ for $0\leq j\leq i$. So to obtain
$U_n$, it is sufficient to know $M_i$ for $0\leq i\leq n$. Since the values of $M_i$ are known for $0\leq i\leq 9$, these provide the
values of $U_n$ for $0\leq n\leq 9$.
Due to the recent independent computation of $M_9$ by Van Hirtum et al.~\cite{vanhirtum2023computation} and J\"{a}kel~\cite{jakel2023computation},
we are able to obtain the value of $U_9$.
From the values $U_n$ for $0\leq n\leq 9$, using Proposition~\ref{prop-nd}, we obtain the values of $\nd\!\mbox{-}U_n$ for
$0\leq n\leq 9$. Table~\ref{tab-unate} shows the values of $U_n$ and $\nd\!\mbox{-}U_n$.
\begin{table}
\centering
	{\scriptsize
	\begin{tabular}{|c|r|r|}
		\hline
		$n$ & \multicolumn{1}{c|}{$U_n$} & \multicolumn{1}{c|}{$\nd\!\mbox{-}U_n$} \\ \hline
		0 &2 & 2\\ \hline
		1 & 4& 2\\ \hline
		2 &14 & 8\\ \hline
		3 & 104 & 72\\ \hline
		4 &2170 & 1824\\ \hline
		5 &230540 & 220608\\ \hline
		6 & 499596550 & 498243968\\ \hline
		7 & 309075799150640& 309072306743552\\ \hline
		8 &14369391928071394429416818 &14369391925598802012151296 \\ \hline
		9 & 146629927766168786368451678290041110762316052 & 146629927766168786239127150948525247729660416\\ \hline
	\end{tabular}
	\caption{Number of $n$-variable unate and non-degenerate unate functions for $0\leq n\leq 9$ 
	[\seqnum{A245079}, \seqnum{A305000}]. \label{tab-unate}}
	}
\end{table}

Similarly, using Proposition~\ref{prop-nd} and~\eqref{eqn-m-u-b-nd}, the problem of counting balanced unate functions reduces to the problem
of counting balanced monotone Boolean functions. Since the values of $\BM_i$ are known for for $0\leq i\leq 7$, we can obtain the values of 
$\BU_n$ for $0\leq n\leq 7$. Using Proposition~\ref{prop-nd}, this gives us the values of $\nd\!\mbox{-}\!\BU_n$ for $0\leq n\leq 7$. 
Table~\ref{tab-bal-unate} shows the values of $\BU_n$ and $\nd\!\mbox{-}\!\BU_n$.

\begin{table}
\centering
	{
	\begin{tabular}{|c|r|r|}
		\hline
		$n$ & \multicolumn{1}{c|}{$\BU_n$} & \multicolumn{1}{c|}{$\nd\!\mbox{-}\!\BU_n$} \\ \hline
		0 &0 &0 \\ \hline
		1 & 2 & 2 \\ \hline
		2 &4 &0 \\ \hline
		3 &14 &8 \\ \hline
		4 &296 &256 \\ \hline
		5 &18202 & 16832\\ \hline
		6 & 31392428& 31287424\\ \hline
		7 & 10393772159334 &10393552784640 \\ \hline
	\end{tabular}
	\caption{Number of $n$-variable balanced unate and non-degenerate balanced unate functions for $0\leq n\leq 7$ [\seqnum{A373690}, \seqnum{A373697}]. \label{tab-bal-unate}}
	}
\end{table}


\section{Counting equivalence classes of functions \label{sec-enum} }
In this section, we present the results on the numbers of equivalence classes of certain subsets of unate and monotone Boolean functions.

\subsection{Filtering procedure \label{subsec-filter}}
The basic problem of enumerating equivalence classes is the following. 
Let $\mathcal{S}$ be a subset of the set of all $n$-variable Boolean functions. Given $\mathcal{S}$, we wish to generate a set $\mathcal{T}\subseteq \mathcal{S}$ of functions
such that no two functions in $\mathcal{T}$ are equivalent, and each function in $\mathcal{S}$ is equivalent to some function in $\mathcal{T}$. The technique for such
filtering is the following. 

Given a permutation $\pi$ of $\{1,\ldots,n\}$, we define a permutation $\pi^{\star}$ of $\{0,\ldots,2^n-1\}$ as follows. For $i\in \{0,\ldots,2^n-1\}$, let 
$(i_1,\ldots,i_n)$ be the $n$-bit binary representation of $i$. Then $\pi^{\star}(i)=j$, where the $n$-bit binary representation of $j$ is
$(j_{\pi(1)},\ldots,j_{\pi(n)})$. 
Given an $n$-variable function $f$, let $f^\pi$ denote the function such that for all $(x_1,\ldots,x_n)\in\{0,1\}^n$, the equation $f^\pi(x_1,\ldots,x_n)=f(x_{\pi(1)},\ldots,x_{\pi(n)})$ holds.
Suppose $f_0\cdots f_{2^n-1}$ is the bit string representation of $f$. Then the bit string representation of $f^\pi$ is
$f_{\pi^\star(0)}\cdots f_{\pi^\star(2^n-1)}$. 

Note that for each permutation $\pi$, the permutation $\pi^\star$ can be pre-computed and stored as an array say $P[0,\ldots,2^n-1]$. Suppose the bit string
representation of $f$ is stored as an array $A[0,\ldots,2^n-1]$. Then the bit string representation of $f^\pi$ is obtained as the array $B[0,\ldots,2^n-1]$, where
$B[i]=A[P[i]]$, for $i=0,\ldots,2^n-1$. So obtaining $f^{\pi}$ becomes simply a matter of array re-indexing. 

Suppose the set of functions $\mathcal{S}$ to be filtered is given as a list of string representations of the functions. We incrementally generate $\mathcal{T}$ as 
follows. The first function in $\mathcal{S}$ is moved to $\mathcal{T}$. We iterate over the other functions in $\mathcal{S}$. For a function $f$ in $\mathcal{S}$, we generate
$f^\pi$ for all permutations $\pi$ of $\{1,\ldots,n\}$ using the technique described above. For each such $f^\pi$, we check whether it is present in $\mathcal{T}$.
If none of the $f^{\pi}$'s are present in $\mathcal{T}$, then we append $f$ to $\mathcal{T}$. At the end of the procedure, $\mathcal{T}$ is the desired set of functions.

The check for the presence of $f^\pi$ in $\mathcal{T}$ involves a search in $\mathcal{T}$. This is done using binary search. To apply binary search on a list, it 
is required that the list be sorted. To ensure this, we initially ensure that $\mathcal{S}$ is sorted (either by generating it in a sorted manner, or by sorting
it after generation). This ensures that at every point, $\mathcal{T}$ is also a sorted list, so that binary search can be applied. 

The reviewer of the paper suggested the following alternative method. Initially, $\mathcal{T}$ is empty. As the algorithm proceeds $\mathcal{S}$ shrinks in size. 
The idea is the following. Pick the next function $f$ from $\mathcal{S}$; for each permutation $\pi$ of $\{1,\ldots,n\}$, generate $f^\pi$ and drop $f^\pi$ from 
$\mathcal{S}$ (if it is present); move $f$ to $\mathcal{T}$. Since $\mathcal{S}$ shrinks in size as the algorithm proceeds, this method is in general faster
than the above method. We have implemented both methods and obtained experimental support for the speed improvement. 

\subsection{Monotone Boolean functions\label{subsec-monotone-eq}}
For $n\geq 0$, the numbers $[M]_n$ of equivalence classes of $n$-variable monotone Boolean functions form entry \seqnum{A003182} of OEIS.
Using Proposition~\ref{prop-nd-eq}, it is possible to find the numbers $\nd\!\mbox{-}[M]_n$ of equivalence classes of $n$-variable monotone Boolean functions (see \seqnum{A006602}).

For $0 \leq n \leq 6$, we obtain the numbers $[\BM]_n$ of equivalence classes of $n$-variable balanced monotone Boolean functions by applying the filtering procedure described 
in Section~\ref{subsec-filter} after enumerating the class of balanced monotone Boolean functions. This method, however, requires too much time to compute $[\BM]_7$.
The techniques of Van Hirtum~\cite{vanHirtum_thesis} provide a faster method. Although Van Hirtum~\cite{vanHirtum_thesis} did not explicitly 
mention it, the associated code provides the values of $[\text{BM}]_n$, for $n=1,\ldots,7$.
By applying Proposition~\ref{prop-nd-eq}, we then obtain $\nd\!\mbox{-}[\BM]_n$ for $n=1,\ldots,7$. Table~\ref{tab-b-m-eq} shows the values of $[\BM]_n$ and $\nd\!\mbox{-}[\BM]_n$.
\begin{table}
\centering
	{\scriptsize
	\begin{tabular}{|c|r|r|}
		\hline
		$n$ & \multicolumn{1}{c|}{$[\BM]_n$} & \multicolumn{1}{c|}{$\nd\!\mbox{-}[\BM]_n$} \\ \hline
		0 &0 & 0\\ \hline
		1 & 1& 1\\ \hline
		2 & 1& 0\\ \hline
		3 & 2& 1\\ \hline
		4 & 4& 2\\ \hline
		5 & 16&12 \\ \hline
		6 & 951&935 \\ \hline
		7 & 16440466 &16439515 \\ \hline
	\end{tabular}
	\caption{Number of equivalence classes of $n$-variable balanced monotone and non-degenerate balanced monotone Boolean functions for $0\leq n\leq 7$ [\seqnum{A371717}, \seqnum{A371718}]. \label{tab-b-m-eq}}
	}
\end{table}

\subsection{Unate functions\label{subsec-unate-eq}}
In the case of counting functions, the problems of counting unate and balanced unate functions reduce to the problems of counting monotone and balanced monotone Boolean functions respectively. In the case of counting equivalence classes of functions, such reduction is no longer possible (using the results that we could prove).
	The reason is that, unlike~\eqref{eqn-m-u-nd}, which expresses the number of non-degenerate unate functions in terms of the number of non-degenerate
	monotone Boolean functions, the relation~\eqref{eqn-m-u-nd-eq} only provides an upper bound on the number of equivalence classes of non-degenerate unate
	functions in terms of the number of equivalence classes of non-degenerate monotone Boolean functions. 
	
In view of the above, for counting equivalence classes of unate functions, we resorted to the technique of enumerating unate functions and then using the
	technique described in Section~\ref{subsec-filter} to obtain the number of equivalence classes. 

	The technique of generating all unate functions is based on Proposition~\ref{unate_proposition}. Along with the string representation of an unate
	function, we also need to record whether the function is increasing or decreasing in each of its variables. This is recorded as the signature of the function.
	The special cases of the two constant functions cause some complications in the definition of the signature. 

For an $n$-variable unate function $f$, we define its signature, denoted $\sig(f)$, to be an element of $\{0,1\}^n\cup \{\mathfrak{z},\mathfrak{o}\}$ in the 
following manner. If $f$ is the constant function $1$, then $\sig(f)=\mathfrak{o}$, if $f$ is the constant function $0$, then 
$\sig(f)=\mathfrak{z}$; otherwise $\sig(f)$ is an $n$-bit string $\alpha$, where for $i=1,\ldots,n$, 
$\alpha_i=1$ if $f$ is monotone increasing in the variable $x_i$, and $\alpha_i=0$ if $f$ is monotone decreasing in the variable $x_i$. 
The signature $\sig(f)$ encodes whether $f$ is monotone increasing or monotone decreasing on each variable. The function $f$ is both monotone increasing
and monotone decreasing in all the variables if and only if it is a constant function. The signatures of the constant functions are defined appropriately.

For enumeration, the bit string representation of the functions is used. An unate function and its signature are stored as a pair. 
Consider the following recursive algorithm to generate all $n$-variable unate functions and their signatures for $n\geq 1$. 
At the base step, i.e., for $n=1$, store the four pairs of 1-variable unate functions and their signatures as $(00,\mathfrak{z})$, 
$(01,1)$, $(10,0)$, and $(11,\mathfrak{o})$. Suppose that for some $n\geq 1$, we have already generated all $n$-variable
unate functions and their signatures. The generation of all $(n+1)$-variable unate functions and their signatures are done as follows. For every two
function-signature pairs $(g,\sig(g))$ and $(h,\sig(h))$, where $g$ and $h$ are $n$-variable unate functions (which are not necessarily distinct), perform the 
following checks: 
\begin{enumerate}
	\item Whether at least one of $\sig(g)$ or $\sig(h)$ is equal to either $\mathfrak{z}$ or $\mathfrak{o}$ (i.e., whether at least one of
		$g$ or $h$ is a constant function).
	\item $\sig(g)=\sig(h)=\alpha$, and either $g\leq h$ or $h\leq g$ holds. 
\end{enumerate}
If either of the checks passes, then generate $f=g||h$, and determine $\sig(f)$ as follows.
\begin{displaymath}
\sig(f) = \begin{cases}
\mathfrak{z}, & \text{if  $\sig(g)=\sig(h)=\mathfrak{z}$;} \\
\mathfrak{o}, & \text{if  $\sig(g)=\sig(h)=\mathfrak{o}$;} \\
1^{n+1},   & \text{if  $\sig(g)=\mathfrak{z}$,  $\sig(h)=\mathfrak{o}$;} \\
0^{n+1},   & \text{if  $\sig(g)=\mathfrak{o}$,  $\sig(h)=\mathfrak{z}$;} \\
1||\alpha, & \text{if  $\sig(g)=\mathfrak{z}$,  $\sig(h)=\alpha\in \{0,1\}^n$;} \\
0||\alpha, & \text{if  $\sig(g)=\mathfrak{o}$, $\sig(h)=\alpha\in \{0,1\}^n$;} \\
1||\alpha, & \text{if  $\sig(g)=\alpha\in \{0,1\}^n$, $\sig(h)=\mathfrak{o}$;} \\
0||\alpha, & \text{if $\sig(g)=\alpha\in \{0,1\}^n$,  $\sig(h)=\mathfrak{z}$;} \\
1||\alpha, & \text{if  $g\leq h$, $\sig(g)=\sig(h)=\alpha \in \{0,1\}^n$;} \\
0||\alpha, & \text{if  $g\geq h$, $\sig(g)=\sig(h)=\alpha \in \{0,1\}^n$.}
\end{cases}
\end{displaymath}

Store $(f,\sig(f))$. Proposition~\ref{unate_proposition} assures us that this recursive procedure generates all $(n+1)$-variable unate functions and their signatures. 

To generate all $(n+1)$-variable unate functions, the above method requires considering all pairs of $n$-variable unate functions, i.e., a total of
$\bigl(U(n)\bigr)^2$ options. Applying the filtering strategy of Section~\ref{subsec-filter} we obtain the value of 
$[U]_n$. Next using Proposition~\ref{prop-nd-eq} we obtain the value of $\nd\!\mbox{-}[U]_n$. 
We could perform this computation for $n\leq 6$. Table~\ref{tab-u-eq} shows the obtained values of $[U]_n$ and $\nd\!\mbox{-}[U]_n$.
To generate all 7-variable unate functions using this option requires considering $\bigl(U(6)\bigr)^2\approx 2^{57.8}$ pairs of functions. This is not feasible on the
computing facility available to us.
\begin{table}[htb]
\centering
	{
	\begin{tabular}{|c|r|r|}
		\hline
		$n$ & \multicolumn{1}{c|}{$[U]_n$} & \multicolumn{1}{c|}{$\nd\!\mbox{-}[U]_n$} \\ \hline
		0 &2 & 2\\ \hline
		1 & 4& 2\\ \hline
		2 &10 &6 \\ \hline
		3 & 34& 24\\ \hline
		4 & 200&166 \\ \hline
		5 &3466 &3266 \\ \hline
		6 & 829774& 826308\\ \hline
	\end{tabular}
	\caption{Number of equivalence classes of $n$-variable unate and non-degenerate unate functions for $0\leq n\leq 6$ [\seqnum{A372495}, \seqnum{A374399}]. \label{tab-u-eq}}
	}
\end{table}

To obtain the set of $n$-variable balanced unate functions, after generating the set of all $n$-variable unate functions, we remove the unbalanced ones. Then to the
resulting set, we apply the technique of Section~\ref{subsec-filter} to obtain the number $[\BU]_n$ of equivalence classes of $n$-variable balanced unate functions. 
Subsequently, we apply Proposition~\ref{prop-nd-eq} to obtain the number $\nd\!\mbox{-}[\BU]_n$ of equivalence classes of $n$-variable non-degenerate balanced
unate functions. Table~\ref{tab-u-b-eq} shows the values of $[\BU]_n$ and $\nd\!\mbox{-}[\BU]_n$.
\begin{table}
\centering
	{
	\begin{tabular}{|c|r|r|}
		\hline
		$n$ & \multicolumn{1}{c|}{$[\BU]_n$} & \multicolumn{1}{c|}{$\nd\!\mbox{-}[\BU]_n$} \\ \hline
		0 & 0& 0\\ \hline
		1 & 2& 2\\ \hline
		2 & 2 &0 \\ \hline
		3 & 6& 4\\ \hline
		4 & 24& 18 \\ \hline
		5 & 254& 230\\ \hline
		6 & 50172&49918 \\ \hline
	\end{tabular}
	\caption{Number of equivalence classes of $n$-variable balanced unate and non-degenerate balanced unate functions for $0\leq n\leq 6$ [\seqnum{A374400}, \seqnum{A374401}]. \label{tab-u-b-eq}}
	}
\end{table}

\subsection{NPN-equivalence:} 
From Proposition~\ref{prop-NN-unate-mono}, we have that the number of NPN-inequivalent $n$-variable unate functions is equal to the number of NPN-inequivalent $n$-variable monotone 
Boolean functions. Also, the number of NPN-inequivalent $n$-variable balanced unate functions is equal to the number of NPN-inequivalent $n$-variable balanced monotone Boolean 
functions. 
As mentioned earlier, the number of NPN-inequivalent unate functions is already available in the OEIS (see \seqnum{A003183}). So we consider the problem of 
counting the number of NPN-inequivalent balanced monotone (or unate) Boolean functions. 
\begin{table}[H]
\centering
	{
	\begin{tabular}{|c|r|r|}
		\hline
		$n$ & \multicolumn{1}{c|}{$\sym{NPN}\mbox{-}\text{inequivalent }M_n$} & \multicolumn{1}{c|}{$\sym{NPN}\mbox{-}\text{inequivalent }\BM_n$} \\ \hline
		0 &1 & 0\\ \hline
		1 & 2& 1\\ \hline
		2 &3 & 1\\ \hline
		3 & 6 & 2\\ \hline
		4 & 17 & 4\\ \hline
		5 &112 & 15\\ \hline
		6 & 8282 & 581\\ \hline
	\end{tabular}
	\caption{Number of NPN-equivalence classes of $n$-variable monotone (or unate) and balanced monotone (or unate) Boolean functions for $0\leq n\leq 6$ 
	(see \seqnum{A003183}, \seqnum{A378300}). \label{tab-NPN-balanced-mono}}
	}
\end{table}

From Proposition~\ref{prop-NN-mono}, to consider NPN-equivalence of monotone Boolean functions, it is sufficient to consider all possible permutations of the input variables
along with simultaneous inversion of all the input variables and the output. Thus, for each monotone Boolean function, there are a total of $2\times n!$ other functions to consider.
We apply this idea in combination with the filtering technique described in Section~\ref{subsec-filter}. Since we are interested in inequivalent balanced monotone Boolean functions, 
we first prepare a list of balanced monotone Boolean functions and to this list, we apply the filtering technique. The number of functions left after the filtering procedure is 
complete is the number of NPN-inequivalent balanced monotone Boolean functions. The numbers of $n$-variable NPN-inequivalent balanced monotone Boolean functions for $n\leq 6$ 
are given in Table~\ref{tab-NPN-balanced-mono}.


\section{Future research \label{sec-conclu}}
We mention some problems that may be tackled by future research.

The first problem is of counting balanced monotone Boolean functions. The recent algorithms designed by
J\"{a}kel~\cite{jakel2023computation} and Van Hirtum et al.~\cite{vanhirtum2023computation} count all monotone Boolean functions. Modifying these algorithms to
count balanced monotone Boolean functions is a possible research problem.
The second problem is to apply the methods developed by Pawelski~\cite{DBLP:journals/tit/Pawelski24} to count the number of inequivalent balanced
monotone Boolean functions.
The third problem is to modify the methods of Pawelski~\cite{DBLP:journals/tit/Pawelski24} to count the number of inequivalent unate functions.


\section{Acknowledgment} We are grateful to an anonymous reviewer of the Ph.D. thesis of the first author for suggesting that the number of $n$-variable non-degenerate unate
functions is equal to $2^n$ times the number of $n$-variable non-degenerate monotone Boolean functions. We also thank the anonymous reviewer for providing valuable comments
and suggestions, which have significantly improved the paper.

\begin{thebibliography}{99}

\bibitem{mono_gen}
Valentin Bakoev, Generating and identification of monotone Boolean functions, 
  in {\em Mathematics and Education in Mathematics: Proc. of the Thirty Second Spring Conference of the Union of Bulgarian Mathematicians}, 2003, pp. 226--232. 
   


\bibitem{baugh72}
Charles~R. Baugh, Generation of representative functions of the {NPN}
  equivalence classes of unate {B}oolean functions,
  {\em {IEEE} Trans. Comput.} {\bf C-21} (1972), 1373--1379.

\bibitem{DBLP:journals/logcom/BaumannS17}
Ringo Baumann and Hannes Strass, On the number of bipolar {B}oolean functions,
  {\em J. Logic Comput.} {\bf 27} (2017), 2431--2449.

\bibitem{berman}
Joel Berman and Peter K\"{o}hler, Cardinalities of finite distributive
  lattices, {\em Mitt. Math. Sem. Giessen} {\bf 121} (1976), 103--124.

\bibitem{Church}
Randolph Church, {Numerical analysis of certain free distributive structures},
  {\em Duke Math. J.} {\bf 6} (1940), 732--734.

\bibitem{church1965enumeration}
Randolph Church, Enumeration by rank of the elements of the free distributive
  lattice with seven generators, {\em Notices Amer. Math. Soc.} {\bf 12}
  (1965), 724.

\bibitem{Dedekind1897103}
Richard Dedekind, { {\"U}ber {Z}erlegung von {Z}ahlen durch ihre
  gr{\"o}ssten gemeinsamen {T}heiler}, \newblock In {\em Festschrift Hoch. Braunschweig u. ges. Werke (II)}, 1897, pp.  103--148.

\bibitem{DBLP:journals/ipl/FidytekMSS01}
Robert Fidytek, Andrzej~W. Mostowski, Rafal Somla, and Andrzej Szepietowski,
  Algorithms counting monotone {B}oolean functions, {\em Inform. Process. Lett.} {\bf 79} (2001), 203--209.

\bibitem{vanHirtum_thesis}
Lennart~Van Hirtum, A path to compute the 9th Dedekind number using FPGA
  supercomputing, Master's thesis, KU Leuven, 2023. Available
at \url{https://hirtum.com/thesis.pdf}.

\bibitem{vanhirtum2023computation}
Lennart~Van Hirtum, Patrick~De Causmaecker, Jens Goemaere, Tobias Kenter,
  Heinrich Riebler, Michael Lass, and Christian Plessl, A computation of the
  ninth {D}edekind number using {FPGA} supercomputing, {\em ACM Transactions on
  Reconfigurable Technology and Systems} {\bf 17} (2024), 1--28.

\bibitem{jakel2023computation}
Christian J\"{a}kel, A computation of the ninth {D}edekind number, {\em J. Comput. Algebra} {\bf 6-7} (2023), 100006.

\bibitem{Kisielewicz1988139}
Andrzej Kisielewicz, A solution of {D}edekind's problem on the number of
  isotone {B}oolean functions, {\em J. Reine Angew. Math.} {\bf 386} (1988), 139--144.

\bibitem{Korshunov2003929}
Aleksej~D. Korshunov, Monotone {B}oolean functions, {\em Russian Math. Surveys}
  {\bf 58} (2003), 929--1001.

\bibitem{DBLP:journals/tit/Pawelski24}
Bart{\l}omiej Pawelski, On the number of inequivalent monotone {B}oolean
  functions of 9 variables, {\em IEEE Trans. Inform. Theory} {\bf 70} (2024),
  5358--5364.

\bibitem{RT09}
Fred Roberts and Barry Tesman, {\em Applied Combinatorics, 2nd edition},
  Chapman and Hall/CRC, 2009.

\bibitem{ListINtSequence}
Neil J.~A. Sloane, The On-Line Encyclopedia of Integer Sequences,
  \url{https://oeis.org/}, 2025.

\bibitem{STEPHEN201415}
Tamon Stephen and Timothy Yusun, Counting inequivalent monotone {B}oolean
  functions, {\em Discrete Appl. Math.} {\bf 167} (2014), 15--24.

\bibitem{Ward}
Morgan Ward, Note on the order of free distributive lattices, {\em Bull. Amer.
  Math. Soc.} {\bf 52} (1946), 423.

\bibitem{Wiedemann19915}
Doug Wiedemann, A computation of the eighth {D}edekind number, {\em Order} {\bf
  8} (1991), 5--6.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification}:
Primary 06E30.

\noindent \emph{Keywords: } Boolean function, unate function, monotone Boolean function, Dedekind number.

\bigskip
\hrule
\bigskip

\noindent (Concerned with the sequences
\seqnum{A000372}, \seqnum{A000618}, \seqnum{A000721}, \seqnum{A003182}, \seqnum{A003183}, \seqnum{A005612}, \seqnum{A006126}, \seqnum{A006602}, \seqnum{A037293}, 
\seqnum{A136094}, \seqnum{A245079}, \seqnum{A304999}, \seqnum{A305000},  \seqnum{A341633}, \seqnum{A371717}, \seqnum{A371718}, \seqnum{A371722}, \seqnum{A372495}, 
\seqnum{A373690}, \seqnum{A373697}, \seqnum{A374399}, \seqnum{A374400}, \seqnum{A374401}, \seqnum{A378300}, and \seqnum{A378302}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received December 16 2023;
revised versions received December 17 2023; December 27 2024; January 28 2025;
April 16 2025.
Published in {\it Journal of Integer Sequences}, April 17 2025.

\bigskip
\hrule
\bigskip

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

\end{document}
