<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}}}

\DeclareMathOperator{\Sum}{Sum}
\DeclareMathOperator{\SumSq}{SumSq}
\DeclareMathOperator{\Fix}{Fix}
\DeclareMathOperator{\Cycl}{Cycl}
\DeclareMathOperator{\Up}{Up}
\DeclareMathOperator{\Down}{Down}

\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 
Fixes of Permutations Acting on \\
\vskip .1in
Monotone Boolean Functions
}
\vskip 1cm
\large
Andrzej Szepietowski\\
Institute of Informatics\\
Faculty of Mathematics,Physics and Informatics \\
University of Gda\'{n}sk \\
80-308 Gda\'{n}sk \\
Poland\\
\href{mailto:matszp@inf.ug.edu.pl}{\tt matszp@inf.ug.edu.pl}\\
\end{center}

\vskip .2in

\begin{abstract}
We present a few algorithms and methods to count fixes of permutations
acting on monotone Boolean functions.
\end{abstract}


\section{Introduction}
Let $B$ denote the set $\{0,1\}$ and $B^n$ the
set of $n$-element sequences of $B$.
A {\it Boolean function with $n$ variables} is any function
from $B^n$ into $B$. There are $2^n$ elements in $B^n$
and $2^{2^n}$ Boolean functions with $n$ variables.
There is the order relation in $B$ (namely: $0\le 0$, $\;0\le1$, $\;1\le1$)
and the partial order in $B^n$:
for any two elements: 
$x=(x_1,\dots,x_n)$, $\;y=(y_1,\dots,y_n)$ in $B^n$,
$$x\le y\quad\hbox{if and only if}\quad x_i\le y_i
\quad \hbox{for all $1\le i\le n$}.$$
The function $h:B^n\to B$ is {\it monotone} if
 $$x\le y \Rightarrow h(x)\le h(y).$$
Let $D_n$ denote the set of monotone functions with $n$ variables
and let $d_n$ denote $|D_n|$.
Known values of $d_n$, for $n=0,\dots,8$ are presented in the table at the end of this paper.
The values $d_n$ for $n\le 4$ were published by Dedekind~\cite{D}, Church~\cite{Ch1,Ch2} gave the values $d_5$ and $d_7$, Ward~\cite{Wa} the value $d_6$, and the last known value $d_8$ was  published by Wiedemann~\cite{W}.
Dedekind numbers were also considered in~\cite{B,C,CW,FMSS, SY}.

We have  the partial order in $D_n$ defined as follows:
$$g\le h\quad\hbox{if and only if}\quad g(x)\le h(x)\quad
\hbox{for all } x\in B^n.$$
We represent the  elements of $D_n$ as strings of bits of
length $2^n$. Two elements of $D_0$ will be represented as 0 and 1;
any element $g\in D_1$ can  be represented as 
a concatenation $g(0)*g(1)$, where $g(0), g(1)\in D_0$ and $g(0)\le g(1)$. Hence, $D_1=\{00, 01, 11\}$. 
Each element $g\in D_2$ is a concatenation (string) of four bits: $g(00)*g(10)*g(01)*g(11)$ which can be  represented as
a concatenation $g_0*g_1$, where $g_0, g_1\in D_1$ and $g_0\le g_1$.
Hence, $D_2=\{0000, 0001, 0011, 0101, 0111, 1111\}$.
Similarly any element $g\in D_n$ can be represented as
a concatenation $g_0*g_1$, where $g_0, g_1\in D_{n-1}$ and $g_0\le g_1$. 


Let $S_n$ denote the set of permutations on $\{1,\ldots,n\}$.
Every permutation $\pi\in S_n$ defines the permutation on $B^n$ by
$\pi(x)=x\circ\pi$
(we treat each element $x\in B^n$ as a function
$x:\{1,\dots,n\}\to \{0,1\}$).
Note that $x\le y$ if and only if $\pi(x)\le\pi(y)$.
The permutation $\pi$ also generates the permutation
on $D_n$. Namely, by $\pi(g)=g\circ \pi$.
Note that $\pi(g)$ is monotone if $g$ is monotone.
Two functions $f, g\in D_n$ are {\it equivalent} if there is a 
permutation $\pi\in S_n$ such that $f=\pi(g)$.
By $R_n$ we denote the set of equivalence classes and by $r_n$
we denote the number of the equivalence classes.
Known values of $r_n$ (for $n\le 8$) are given in the table at the end of this paper.
The number of the equivalence classes can be computed by Burnside's lemma;
see~\cite[\S 38]{M}. Namely,
$$
r_n=\frac{1}{n!}\sum_{\pi\in S_n}|\Fix(\pi,D_n)|,
$$ 
where $\Fix(\pi,D_n)$ is the set of fixes of the permutation $\pi$ acting on $D_n$.
A function $f\in D_n$ is a {\it fix} of $\pi$ if $\pi(f)=f$. 

  In 1985 and 1986 Liu and Hu~\cite{CS1,CS2} used Burnside's lemma 
  to compute $r_n$ for all $n\le 7$.
 Recently, Pawelski~\cite{P} computed $r_8$. 
   
In this paper we propose a new framework to study monotone Boolean functions and present a few algorithms and methods to count fixes of permutations acting on $D_n$. The main contributions  of the paper are Theorem~\ref{Thm} and Lemma~\ref{L4} which give formulas for the set of fixes of the composition $\pi\circ\rho$ of two permutations, provided $\pi$ and $\rho$ satisfy certain conditions. A special case of Lemma~\ref{L4} was used by Pawelski~\cite{P} to count and generate fixes of several permutations  acting on $D_n$. For completeness, in Sections~\ref{S1} and \ref{S2},
we present a method which was used by Pawelski~\cite{P} to compute 
fixes of the permutation $(12)(34)(56)(78)$ acting on $D_8$.
\section{Posets}
A {\it poset (partially ordered set)} $(S,\le)$ consists of a set $S$ (called the {\it carrier}) together with a binary relation (partial order) $\le$ which is reflexive, transitive and antisymmetric.
For two posets $(S,\le)$ and $(T,\le)$ by $S\times T$ we denote the cartesian product with the order defined as follows: $(a,b)\le(c,d) $ iff $a\le c $ and $b\le d$.
For two disjoint posets $(S,\le)$ and $(T,\le)$ by $S+ T$ we denote the disjoint union (sum)  with the order defined as follows:
$$x\le y\quad\hbox{iff}\quad (x,y\in S \quad\hbox{and}\quad x\le y)\quad
\hbox{or}\quad(x,y\in T\quad\hbox{ and }\quad x\le y).$$
Given two posets $(S,\le)$ and $(T,\le)$ a function $f:S \to T$ is {\it monotone}, if   $x \le y$ implies $f(x)\le f(y)$.
By $T^S$ we denote  the poset of all monotone functions from $S$ to $T$ with the partial order  defined as follows:
$$f\le g\quad\hbox{ if and only if}\quad f(x)\le g(x)\hbox{ for all }x\in S.$$

In this paper we use the following notation:
\begin{itemize}
\item $A_n$ denotes an antichain of order $n$, i.e. a poset of $n$ elements,  where no two distinct elements are related.
We only deal with antichains with the carrier being a finite subset of natural numbers.
\item $B$ denotes the poset of two bits $\{0,1\}$ ordered by  $0\le 0$, $0\le1$,  $1\le1$.
\item $B^n$ denotes the poset $B^{A_n}$ of all (monotone) functions from $A_n$ into $B$. Note that each function from 
$A_n$ to $B$ is monotone. The poset $B^n$ is  isomorphic to
\begin{itemize}
\item the poset of all subsets of $\{1,\dots,n\}$ ordered by the inclusion,
\item the poset of all $n$-strings of bits, where $(x_1,\dots,x_n)\le(y_1,\dots,y_n)$ iff $x_i\le y_i$ for all $i$. 
\end{itemize}
\item $D_n$ denotes the poset $B^{B^n}$ of all monotone Boolean functions from $B^n$ into $B$, which are called monotone Boolean functions of $n$ variables.
\item $P_n$ denotes the path (or chain) $P_n=\{p_1&lt;\dots&lt;p_n\}$. Note that $B^{P_n}=P_{n+1}$.
\end{itemize}
We will use the following lemma which is a part of the folklore and can be easily proved.
\begin{lemma}\label{L1} For three posets $R,S,T$,

(1) If $S$ and $T$ are disjoint, then the poset $R^{S+T}$ is isomorphic to $R^S\times R^T$.

(2) The poset $R^{S\times T}$ is isomorphic to $(R^S)^T$ and to $(R^T)^S$.
\end{lemma}
As a corollary we have the following lemma. 
 Similar lemmas  in other formulations were used by Wiedemann~\cite{W}, by Fidytek, Mostowski, Somla and Szepietowski~\cite{FMSS}, and by Campo~\cite{C} 
 in order to compute $d_n=|D_n|$.
\begin{lemma} 
\leavevmode
\begin{itemize}
\item[(a)] \quad $A_{k+m}=A_{k}+A_{m}$
\item[(b)] \quad $B^{k+m}=B^{k}\times B^{m}$
\item[(c)] \quad $D_{k+m}=(D_k)^{B^m}$
\end{itemize}
\end{lemma}
\begin{proof}
\leavevmode
\begin{itemize}
\item[(a)] is obvious.
\item[(b)] $B^{k+m}= B^{A_{k+m}}=B^{A_{k}+A_{m}}=B^{A_{k}}\times B^{A_{m}}=B^k\times B^m $.
\item[(c)] $D_{k+m}= B^{B^{k+m}}=B^{B^k \times B^m}=(B^{B^k})^{B^m}=(D_k)^{B^m}$.
\end{itemize}
 \end{proof}
\section{Arrays}\label{Sec3}
Let $M(S)$ denote the array of the poset $S$. For $i,j\in S$, we have $M(S)[i,j]=1$ if $i\le j$, and  $M(S)[i,j]=0$ otherwise.
For example, for the poset
$D_1=\{00&lt;01&lt;11\}$,  its array
$$
M(D_1)=\left(
\begin{array}{ccc}
1 &amp; 1&amp; 1\\
0 &amp; 1&amp; 1\\
0 &amp; 0&amp;1
\end{array}
\right)
$$
The poset $D_1$ is equal (isomorphic) to the poset of the path $P_3=\{a&lt;b&lt;c\}$. 

The elements of $M(S)$ describe monotone functions from the poset $B=\{0,1\}$ to $S$.
If $M(S)[i,j]=1$ then there exists a monotone function with $f(0)=i$ and $f(1)=j$.
Thus, if we add the elements of $M(S)$ we obtain $|S^B|$---the number of monotone functions
from $B$ to $S$. For example,
$$\Sum(M(D_1))=6=|D_1^B|=|(B^B)^B|= |B^{B\times B}|=|B^{B^2}| =|D_2|=d_2,$$
where $\Sum(M(D_1))$ denotes the sum of all elements of the array $M(D_1)$.
Similarly, for every $n\ge2$, we have 
$$\Sum(M(D_n))=|D_n^B|=|(B^{B^n})^B|= |B^{B^n\times B}|=|B^{B^{n+1}}| =|D_{n+1}|=d_{n+1}.$$

Consider the product $M(S)^2=M(S)\times M(S)$. Then
$M(S)^2[i,j]=|\{k\in S : i\le k\le j\}|$ which is the number of elements in the interval 
$[i,j]\subset S$. Moreover, the elements of $M(S)^2$ are connected to monotone  functions from the path $P_3=\{a&lt;b&lt;c\}$ to $S$. Indeed, $M(S)^2[i,j]$ is equal to the number of monotone functions with $f(a)=i$ and $f(c)=j$, or in other words to the number of elements which can be chosen for the value of $f(b)$. Hence, $\Sum(M(S)^2)=|S^{P_3}|$.
For example,
$$
M(D_1)^2=\left(
\begin{array}{ccc}
1 &amp; 2&amp; 3\\
0 &amp; 1&amp; 2\\
0 &amp; 0&amp;1
\end{array}
\right)
$$
$M(D_1)^2[1,3]=3$ is equal to the number of elements in the interval 
$[00,11]=\{00,01,11\}$. Furthermore, 
$\Sum(M(D_1)^2)=10$ is equal to $|D_1^{P_3}|$---the number of monotone functions from $P_3$ to  $D_1$, and to  $|(B^{B})^{P_3}|$, and to $|B^{B\times P_3}|$.
Moreover, the squares of the elements of $M(S)^2$ are connected to monotone functions from the cube $B^2=\{00,01,10,11\}$ to $S$. Indeed,  $(M(S)^2[i,j])^2=M(S)^2[i,j]\cdot M(S)^2[i,j]$ is equal to the number of monotone functions with $f(00)=i$ and $f(11)=j$. Note that we can choose $M(S)^2[i,j]$ elements for the value of $f(01)$ and $M(S)^2[i,j]$ elements for the value of $f(10)$. Since these two values can be chosen independently, we have $(M(S)^2[i,j])^2$ monotone functions with 
$f(00)=i$ and $f(11)=j$. Hence, $\SumSq(M(S)^2)=|S^{B^2}|,$
where $\SumSq(M(S)^2)$ denotes the sum of squares of all elements of the array $M(S)^2$.
For example, 
$\SumSq(M(D_1)^2)=20$ is equal to $|D_1^{B^2}|=|(B^B)^{B^2}|=|B^{B\times B^2}|= |B^{B^3}|=d_3$.
Similarly, for every $n\ge 2$, we have
$$\SumSq(M(D_n)^2)=|D_n^{B^2}|=|(B^{B^n})^{B^2}|=|B^{B^n\times B^2}|= |B^{B^{n+2}}|=d_{n+2}.$$
This fact was used in another formulation by  Fidytek, Mostowski, Somla and Szepietowski~\cite{FMSS}.
 
Consider the product $M(S)^3=M(S)\times M(S)\times M(S)$. The elements of $M(S)^3$ are connected  to
monotone functions from the path $P_4=(a&lt;b&lt;c&lt;d)$ to $S$. Indeed,   $M(S)^3[i,j]$ is equal to the number of pairs $x,y$,
such that $i\le x\le y\le j$, and to the number of monotone functions in $S^{P_4}$
with $f(a)=i$ and $f(d)=j$.
Hence, $\Sum(M(S)^3)=|S^{P_4}|$.
For example, 
$$
M(D_1)^3=\left(
\begin{array}{ccc}
1 &amp; 3&amp; 6\\
0 &amp; 1&amp; 3\\
0 &amp; 0&amp;1
\end{array}
\right)
$$
$\Sum(M(D_1)^3)=15$ is equal to $|D_1^{P_4}|$---the number of monotone functions from $P_4$ to  $D_1$, and to  $|(B^{B})^{P_4}|$, and to $|B^{B\times P_4}|$.
\section{Symmetries}
Let $S_n$ denote the set of permutations on $\{1,\dots,n\}$.
Every permutation $\pi\in S_n$ defines the permutation on $B^n$ by
$\pi(x)=x\circ\pi$.
Here we treat elements $x\in B^n$ as functions $x:\{1,\dots ,n\}\to \{0,1\}$.
Note that $x\le y$ if and only if $\pi(x)\le\pi(y)$.
\begin{example} Consider two permutations: $\pi_1=(12)$ and $\pi_2=(123)$, both
acting on $B^3$:

\medskip

\centering
\begin{tabular}[h]{|c||c|c|c|c|c|c|c|c|}
\hline
$x$       &amp;\textnormal{000} &amp;\textnormal{100} &amp;\textnormal{010} &amp;\textnormal{110} &amp;\textnormal{001} &amp;\textnormal{101} &amp;\textnormal{011} &amp;\textnormal{111}\\
\hline
$\pi_1(x)$&amp;\textnormal{000} &amp;\textnormal{010} &amp;\textnormal{100} &amp;\textnormal{110} &amp;\textnormal{001} &amp;\textnormal{011} &amp;\textnormal{101} &amp;\textnormal{111}\\ 
\hline
$\pi_2(x)$&amp;\textnormal{000} &amp;\textnormal{001} &amp;\textnormal{100} &amp;\textnormal{101} &amp;\textnormal{010} &amp;\textnormal{011} &amp;\textnormal{110} &amp; \textnormal{111}\\ 
\hline
\end{tabular}
\end{example}

Each permutation $\pi$ acting on $B^n$ generates a permutation
on $D_n=B^{B^n}$. Namely, $\pi(g)=g\circ \pi$.
Note that $\pi(g)$ is monotone if $g$ is monotone.
Two functions $f, g\in D_n$ are {\it equivalent} if there is a 
permutation $\pi\in S_n$ such that $f=\pi(g)$.
By $R_n$ we denote the set of equivalence classes.
The number of the equivalence classes denoted by $r_n$ can be computed by Burnside's lemma; 
see~\cite[\S 38]{M}.
Known values of $r_n$ (for $n\le 8$) are given in the table at the end of this paper.
By the lemma, the number of equivalence classes in $D_n$ is equal to
$$
r_n=\frac{1}{n!}\sum_{\pi\in S_n}|\Fix(\pi,D_n)|,
$$ 
where $\Fix(\pi,D_n)$ is the set of fixes of the permutation $\pi$ acting on $D_n$.
A function $f\in D_n$ is a {\it fix} of $\pi$ if $\pi(f)=f$. 
Since conjugate group elements have the same number of fixed points, $|\Fix(\pi,D_n)|$ depends only on the cycle type of $\pi$. By the {\it cycle type} of a permutation $\pi$, we mean the data giving the lengths of disjoint cycles whose product is $\pi$ and the number of cycles of each length. Let $k(n)$ denote the number of cycle types of elements of $S_n$ and assume that $\pi_1,\dots,\pi_{k(n)}$ is an (arbitrarily chosen) sequence of representatives of all cycle types in $S_n$. For $1\le i\le k(n)$, let $\mu_i$ be the number of elements of $S_n$ of the same cycle type as $\pi_i$ (see the tables in Section~\ref{appa}). Then
$$r_n=\frac{1}{n!}\sum_{i=1}^{k(n)}\mu_i\cdot|\Fix(\pi_i,D_n)|.$$ 
In this paper we present a few algorithms and methods to count fixes
of permutations acting on $D_n$. 

Consider a permutation $\pi\in S_n$ and suppose that $\pi$ when acting 
on $B^n$ is a product of disjoint cycles 
$\pi=C_1\circ\cdots\circ C_r$, then a monotone function $f:B^n\to B$ is a fix of $\pi$ if and only if $f$ is constant on every cycle $C_i$. 
Let $\Cycl(\pi,B^n)$ denote the set of cycles $\{C_1,\dots, C_r\}$,
and let $\le$ be the partial order defined in the following way: $C_i\le C_j$ if and only if there exist
$x\in C_i$ and $y\in C_j$ such that $x\le y$ (we identify each cycle with the set of its elements).  Hence, the poset $\Fix(\pi, D_n)$ is isomorphic
to the poset $B^{\Cycl(\pi,B^n)}$ of monotone functions from $\Cycl(\pi,B^n)$ to $B=\{0,1\}$ and we can represent fixes in $\Fix(\pi,D_n)$ as sequences of bits of length $|\Cycl(\pi,B^n)|$.

For the identity permutation $e$, each $x\in B^n$ forms  a cycle of length 1, hence
$\Cycl(e,B^n)=B^n$ and $\Fix(e,D_n)=D_n$.     
For $n=1$, we have $D_1=R_1$ and $r_1=d_1=3$.
For $n=2$, we have two permutations:
the identity $e$ with $\Fix(e,D_2)=D_2$ and the inversion $(12)$ with
three cycles $C_1=(00)$, $C_2=(10,01)$, and $C_3=(11)$ which form the
path $P_3=\{C_1&lt;C_2&lt;C_3\}$. There are four monotone functions from the path $P_3$ to $B$ and four fixes in $\Fix((12),D_2)$. By Burnside's lemma, we have
$$r_2=\frac{1}{2}(|\Fix(e,D_2)|+|\Fix((12),D_2)|)=\frac{1}{2}(6+4)=5.$$
Indeed, there are five equivalence classes in $D_2$; namely,
$$R_2=\{\{0000\}, \{0001\}, \{0101,0011\},\{0111\},\{1111\}\}.$$
\section{Main results}
\begin{theorem}\label{Thm}
Consider a partition of the antichain  $A_n=\{1,\dots,n\}$ into two disjoint antichains $A_k=\{1,\dots,k\}$ and $A_m=\{k+1,\dots n\}$, where $n=k+m$; and two permutations: one $\pi$ acting on $A_k$ and $\rho$ acting on $A_m$. Suppose that 
each cycle of $\pi$ has a length which is coprime with the length of every cycle of $\rho$ then
$$\Fix(\pi\circ\rho,D_n)=\Fix(\pi,D_k)^{\Cycl(\rho,B^m)}=
\Fix(\rho,D_m)^{\Cycl(\pi,B^k)}.$$
\end{theorem}
\begin{proof}
The cube $B^n$ is isomorphic
to the cartesian product $B^n=B^k\times B^m$. 
Suppose that we have two cycles: one $C_r$ of $\pi$ acting  on $B^k$ and the other $C_s$ of $\rho$ acting on $B^m$. The lengths of the two cycles are coprime, so the product
$C_r\times C_s$ is a cycle of $\pi\circ \rho$ acting on $B^n$.
Furthermore, each cycle of $\pi$ has a length which is coprime with the length of
every cycle of $\rho$ so
$$\Cycl(\pi\circ\rho, B^n)=\Cycl(\pi, B^k)\times \Cycl(\rho, B^m)$$
and
\begin{align*}
\Fix(\pi\circ\rho,D_n) &amp;=B^{\Cycl(\pi\circ\rho, B^n)}=B^{\Cycl(\pi, B^k)\times \Cycl(\rho, B^m)} \\
&amp;= \Fix(\pi,D_k)^{\Cycl(\rho, B^m)}=
\Fix(\rho,D_m)^{\Cycl(\pi,B^k)}.
\end{align*}
\end{proof}
\begin{example} Consider the partition $A_5=A_3+A_2$, with $A_3=\{1,2,3\}$ and $A_2=\{4,5\}$,
and two permutations: $\pi=(123)$ and $\rho=(45)$.
There are four cycles of $(123)$ acting on $B^3$. Namely,
$C_1=(000)$, $C_2=(100,001,010)$, $C_3=(011,110,101)$, and $C_4=(111)$.
They  are of length 1 or 3 and they form the chain $P_4= (C_1&lt;C_2&lt;C_3&lt;C_4)$.
There are three cycles of $(45)$ acting on $B^2$. Namely,
$c_1=(00)$, $c_2=(10,01)$, and $c_3=(11)$.
They  are of length 1 or 2 and they form the chain $P_3= (c_1&lt;c_2&lt;c_3)$.

Furthermore, consider the two cycles
$C_2=(100,001,010\}$ of $\pi$ acting on $B^{\{1,2,3\}}$ and $c_2=\{10,01\}$ of $\rho$ acting on $B^{\{4,5\}}$. Their cartesian product
$$C_2\times c_2=\{10010,00101,01010,10001,00110,01001\}$$ forms one cycle of $\pi\circ\rho$ acting on $B^5=B^3\times B^2$.  
The poset of cycles of $\pi\circ\rho$ acting on $B^5$ is the cartesian product
$P_4\times P_3$ and 
$$|\Fix((123)(45),D_5)| =|B^{P_4\times P_3}|=|P_5^{P_3}|=|P_4^{P_4}|. $$
In order to compute $\Fix((123)(45),D_5)$, let us consider the arrays
$$
M(P_4)=
\left(
\begin{array}{cccc}
1&amp; 1&amp; 1&amp; 1 \\
0&amp; 1&amp; 1&amp; 1 \\
0&amp; 0&amp; 1&amp; 1 \\
0&amp; 0&amp; 0&amp; 1 
\end{array}
\right)
$$
$$
M(P_4)^3=
\left(
\begin{array}{cccc}
1&amp; 3&amp; 6&amp; 10 \\
0&amp; 1&amp; 3&amp; 6 \\
0&amp; 0&amp; 1&amp; 3 \\
0&amp; 0&amp; 0&amp; 1 
\end{array}
\right)
$$
$\Fix((123)(45),D_5)=|P_4^{P_4}|=\Sum(M(P_4)^3)=35$.
We can also use the arrays
$$
M(P_5)=
\left(
\begin{array}{ccccc}
1&amp; 1&amp; 1&amp; 1&amp;1 \\
0&amp; 1&amp; 1&amp; 1&amp;1 \\
0&amp; 0&amp; 1&amp; 1&amp;1\\
0&amp; 0&amp; 0&amp; 1&amp;1\\ 
0&amp; 0&amp; 0&amp; 0&amp;1
\end{array}
\right)
$$
$$
M(P_5)^2=
\left(
\begin{array}{ccccc}
1&amp; 2&amp; 3&amp; 4&amp;5 \\
0&amp; 1&amp; 2&amp; 3&amp;4 \\
0&amp; 0&amp; 1&amp; 2&amp;3\\
0&amp; 0&amp; 0&amp; 1&amp;3\\ 
0&amp; 0&amp; 0&amp; 0&amp;1
\end{array}
\right)
$$
$|\Fix((123)(45),D_5)|=|P_5^{P_3}|=\Sum(M(P_5)^2)=35$.
\end{example}
The following lemma is a direct consequence of the theorem. In the special case with $m=1$ the lemma was used by Pawelski~\cite{P} to count and generate fixes of several permutations  acting on $D_n$.
\begin{lemma}\label{L4}
Suppose that a permutation $\pi$ is acting on $B^k$ and $n&gt;k$.
Then when we consider $\pi$ acting on $B^n$, 
$$\Fix(\pi,D_n)= (\Fix(\pi, D_k))^{B^m} =D_m^{\Cycl(\pi,B^k)}$$
where $m=n-k$.
\end{lemma}
\begin{proof}
The permutation $\pi$ is acting on $\{1,\dots, k\}$ and on $B^k$. We can say that $\pi$ also acts on $\{1,\dots, n\}$ and on $B^n$,
by identifying $\pi$ with $\pi\circ e$. Every cycle in $\Cycl(e,B^m)$ has length 1, hence, $\Cycl(e,B^m)=B^m$ and 
$$\Cycl(\pi\circ e, B^n)=\Cycl(\pi, B^k)\times \Cycl(e, B^m)=\Cycl(\pi, B^k)\times  B^m$$
and
$$\Fix(\pi,D_n)= \Fix(\pi\circ e, D_n)=B^{\Cycl(\pi, B^k)\times  B^m}=(\Fix(\pi, D_k))^{B^m}
=D_m^{\Cycl(\pi,B^k)}.$$
\end{proof}

\section{Applications}
In this section we present a few examples that illustrate concepts from Section~\ref{Sec3}
and applications of Theorem~\ref{Thm} and Lemma~\ref{L4}.

Consider the poset $D_2=B^{B^2}=\{0000,0001,0011,0101,0111,1111\}$ and its array
$$
M(D_2)=\left(
\begin{array}{cc|cc|cc}
1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1 \\
0&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1 \\
\hline
0&amp; 0&amp; 1&amp; 0&amp; 1&amp; 1 \\
0&amp; 0&amp; 0&amp; 1&amp; 1&amp; 1 \\
\hline
0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 1 \\
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1
\end{array}
\right)
$$
Consider the array 
$$
M(D_2)^2=\left(
\begin{array}{cc|cc|cc}
1&amp; 2&amp; 3&amp; 3&amp; 5&amp; 6 \\
0&amp; 1&amp; 2&amp; 2&amp; 4&amp; 5 \\
\hline
0&amp; 0&amp; 1&amp; 0&amp; 2&amp; 3 \\
0&amp; 0&amp; 0&amp; 1&amp; 2&amp; 3 \\
\hline
0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 2 \\
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1
\end{array}
\right).
$$

Now $\Sum(M(D_2)^2)=50$, which is equal to $|D_2^{P_3}|=|(B^{B^2})^{P_3}|=|B^{B^2\times P_3}|=|\Fix((12),D_4)|$; see Lemma~\ref{L4} and Section~\ref{Sec3}. Similarly, 
$\SumSq(M(D_2)^2)=168$, which is equal to $|D_2^{B^2}|=|(B^{B^2})^{B^2}|  =|B^{B^2\times B^2}|=|B^{B^4}|=|D_4|=d_4$. Furthermore, 
$$
M(D_2)^3=\left(
\begin{array}{cc|cc|cc}
1&amp; 3&amp; 6&amp; 6&amp; 14&amp; 20 \\
0&amp; 1&amp; 3&amp; 3&amp; 9&amp; 14 \\
\hline
0&amp; 0&amp; 1&amp; 0&amp; 3&amp; 6 \\
0&amp; 0&amp; 0&amp; 1&amp; 3&amp; 6 \\
\hline
0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 3 \\
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1
\end{array}
\right).
$$
Now $\Sum(M(D_2)^3)=105$, which is equal to 
$|D_2^{P_4}|=|(B^{B^2})^{P_4}|=|B^{B^2\times P_4}|=|\Fix((123),D_5)|$.

\subsection{Permutation (12)}
Consider the permutation $\pi=(12)$. When $\pi$  acts on $B^2$, we have  
three cycles $\Cycl((12),B^2)=P_3$ and $\Fix((12),D_2)=B^{P_3}=P_4$.
When $(12)$ acts on $B^3$, then
$\Cycl((12),B^3)=P_3\times B$ and $\Fix((12),D_3)=B^{P_3\times B}$;
see Lemma~\ref{L4}.
By Section~\ref{Sec3}, the number of fixes can be computed either by
$$|\Fix((12),D_3)|=|B^{P_3\times B}|=|(B^{P_3})^B|=|P_4^B|=\Sum(M(P_4))=10,$$
or by
$$|\Fix((12),D_3)|=|B^{P_3\times B}|=|(B^B)^{P_3}|=|D_1^{P_3}|=\Sum(M(D_1)^2)=10.$$
In a similar way we count fixes when $(12)$ acts on $B^4$, then
$\Cycl((12),B^4)=P_3\times B^2$ and $\Fix((12),D_4)=B^{P_3\times B^2}$.
The number of fixes can be computed either by
$$|\Fix((12),D_4)|=|B^{P_3\times B^2}|=|(B^{P_3})^{B^2}|=|P_4^{B^2}|=\SumSq(M(P_4)^2)=50,$$
or by
$$|\Fix((12),D_4)|=|B^{P_3\times B^2}|=|(B^{B^2})^{P_3}|=|D_2^{P_3}|=\Sum(M(D_2)^2)=50.$$
\subsection{Permutation (123)}
Consider the permutation $\pi=(123)$. When $\pi$  acts on $B^3$, we have  
four cycles $\Cycl((123),B^3)=P_4$ and $\Fix((123),D_3)=B^{P_4}=P_5$.
When $(123)$ acts on $B^4$, then
$\Cycl((123),B^4)=P_4\times B$ and $\Fix((123),D_4)=B^{P_4\times B}$, see Lemma~\ref{L4}.
By Section~\ref{Sec3}, the number of fixes can be computed either by
$$|\Fix((123),D_4)|=|B^{P_4\times B}|=|(B^{P_4})^B|=|P_5^B|=\Sum(M(P_5))=15,$$
or by
$$|\Fix((123),D_4)|=|B^{P_4\times B}|=|(B^B)^{P_4}|=|D_1^{P_4}|=\Sum(M(D_1)^3)=15.$$
In a similar way we can count fixes when $(123)$ acts on $B^5$. Then we have
$\Cycl((123),B^5)=P_4\times B^2$ and $\Fix((123),D_5)=B^{P_4\times B^2}$.
The number of fixes can be computed either by
$$|\Fix((123),D_5)|=|B^{P_4\times B^2}|=|(B^{P_4})^{B^2}|=|P_5^{B^2}|=\SumSq(M(P_5)^2)=105,$$
or by
$$|\Fix((123),D_5)|=|B^{P_4\times B^2}|=|(B^{B^2})^{P_4}|=|D_2^{P_4}|=\Sum(M(D_2)^3)=105.$$
\subsection{Permutation (1234)}
The permutation $(1234)$ acting on $B^4$ has six cycles:
$C_0=\{0000\}$,
$C_1=\{1000,0001,0010,0100\}$,
$C_2=\{1100,1001,0011,0110\}$,
$C_3=\{1010,0101\}$,
$C_4=\{1110,1101,1011,0111\}$,
and $C_5=\{1111\}$.
They are of length 1, 2, or 4 and ordered by
$C_0&lt;C_1&lt;C_2,C_3&lt;C_4&lt;C_5$.
There are 8 fixes of $(1234)$ acting on $D_4$ with the array
$$
M(\Fix((1234),D_4))=\left(
\begin{array}{ccc|cc|ccc}
1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1\\
0&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1 \\
0&amp; 0&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1 \\
\hline
0&amp; 0&amp; 0&amp; 1&amp; 0&amp; 1&amp; 1&amp; 1 \\
0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 1&amp; 1&amp; 1 \\
\hline
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 1&amp; 1 \\
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 1 \\
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1 \\
\end{array}
\right)
$$
$\Sum(M(\Fix((1234),D_4)))=35=|\Fix((1234),D_5))|$, see Lemma~\ref{L4} and Section~\ref{Sec3}. Furthermore, 
$$
M(\Fix((1234),D_4))^2=\left(
\begin{array}{ccc|cc|ccc}
1&amp; 2&amp; 3&amp; 4&amp; 4&amp; 6&amp; 7&amp; 8\\
0&amp; 1&amp; 2&amp; 3&amp; 3&amp; 5&amp; 6&amp; 7 \\
0&amp; 0&amp; 1&amp; 2&amp; 2&amp; 4&amp; 5&amp; 6 \\
\hline
0&amp; 0&amp; 0&amp; 1&amp; 0&amp; 2&amp; 3&amp; 4 \\
0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 2&amp; 3&amp; 4 \\
\hline
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 2&amp; 3 \\
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 2 \\
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1 \\
\end{array}
\right) 
$$
and $\SumSq(M(\Fix((1234),D_4))^2)=494=|\Fix((1234),D_6))|$.
Also
$$
M(\Fix((1234),D_4))^3=\left(
\begin{array}{ccc|cc|ccc}
1&amp;3&amp; 6&amp; 10&amp; 10&amp; 20&amp; 27&amp; 35\\
0&amp; 1&amp; 3&amp; 6&amp; 6&amp; 14&amp; 20&amp;27 \\
0&amp; 0&amp; 1&amp; 3&amp; 3&amp; 9&amp; 14&amp; 20 \\
\hline
0&amp; 0&amp; 0&amp; 1&amp; 0&amp; 3&amp; 6&amp; 10 \\
0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 3&amp; 6&amp; 10 \\
\hline
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 3&amp; 6 \\
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 3 \\
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1 \\
\end{array}
\right)
$$
and 
$\Sum(M(\Fix((1234),D_4))^3)=294=|\Fix((1234)(567),D_7))|$.
\subsection{Permutation (12345)}
The permutation $(12345)$ acting on $B^5$ has eight cycles:
\begin{itemize}
\item $C_0=\{00000\}$,
\item $C_1=\{10000,00001,00010,00100,01000\}$,
\item $C_2=\{11000,10001,00011,00110,01100\}$,
\item $C_3=\{10100,01001,10010,00101,01010\}$,
\item $C_4=\{11100,11001,10011,00111,01110\}$,
\item $C_5=\{10110,01101,11010,10101,01011\}$,
\item $C_6=\{11110,11101,11011,10111,01111\}$,
\item $C_7=\{11111\}$.
\end{itemize}
They are of length 1 or 5 and ordered by
$C_0&lt;C_1&lt;C_2,C_3&lt;C_4,C_5&lt;C_6&lt;C_7$.
There are 11 fixes of $(12345)$ acting on $D_5$ with the array
$$
M(\Fix((12345),D_5))=\left(
\begin{array}{ccc|cc|c|cc|ccc}
1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1\\
0&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1\\
0&amp; 0&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1\\
\hline
0&amp; 0&amp; 0&amp; 1&amp; 0&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1\\
0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1\\
\hline
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1\\
\hline
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 0&amp; 1&amp; 1&amp; 1\\
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 1&amp; 1&amp; 1\\
\hline
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 1&amp; 1\\
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 1\\
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1\\
\end{array}
\right).
$$
We have $\Sum(M(\Fix((12345),D_5)))=64=|\Fix((12345),D_6))|$
and $$
M(\Fix((12345),D_5))^2=\left(
\begin{array}{ccc|cc|c|cc|ccc}
1&amp; 2&amp; 3&amp; 4&amp; 4&amp; 6&amp; 7&amp; 7&amp; 9&amp;10&amp; 11\\
0&amp; 1&amp; 2&amp; 3&amp; 3&amp; 5&amp; 6&amp; 6&amp; 8&amp; 9&amp; 10\\
0&amp; 0&amp; 1&amp; 2&amp; 2&amp; 4&amp; 5&amp; 5&amp; 7&amp; 8&amp; 9\\
\hline
0&amp; 0&amp; 0&amp; 1&amp; 0&amp; 2&amp; 3&amp; 3&amp; 5&amp; 6&amp; 7\\
0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 2&amp; 3&amp; 3&amp; 5&amp; 6&amp; 7\\
\hline
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 2&amp; 2&amp; 4&amp; 5&amp; 6\\
\hline
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 0&amp; 2&amp; 3&amp; 4\\
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 2&amp; 3&amp; 4\\
\hline
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 2&amp; 3\\
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 2\\
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1\\
\end{array}
\right).
$$
By Theorem~\ref{Thm} and Section~\ref{Sec3}, we have 
$\Sum(M(\Fix((12345),D_5))^2)=264=|\Fix((12345)(67),D_7))|$
and by Lemma~\ref{L4}, we have
$$\SumSq(M(\Fix((12345),D_5))^2)=1548=|\Fix((12345),D_7))|.$$
Also
$$
M(\Fix((12345),D_5))^3=\left(
\begin{array}{ccc|cc|c|cc|ccc}
1&amp; 3&amp; 6&amp;10&amp;10&amp;20&amp;27&amp;27&amp;43&amp;53&amp;64\\
0&amp; 1&amp; 3&amp; 6&amp; 6&amp;14&amp;20&amp;20&amp;34&amp;43&amp;53\\
0&amp; 0&amp; 1&amp; 3&amp; 3&amp; 9&amp;14&amp;14&amp;26&amp;34&amp;43\\
\hline
0&amp; 0&amp; 0&amp; 1&amp; 0&amp; 3&amp; 6&amp; 6&amp;14&amp;20&amp;27\\
0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 3&amp; 6&amp; 6&amp;14&amp;20&amp;27\\
\hline
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 3&amp; 3&amp; 9&amp;14&amp;20\\
\hline
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 0&amp; 3&amp; 6&amp;10\\
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 3&amp; 6&amp;10\\
\hline
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 3&amp; 6\\
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 3\\
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1\\
\end{array}
\right)
$$
and
$\Sum(M(\Fix((12345),D_5))^3)=870=|\Fix((12345)(678),D_8))|$; see Theorem~\ref{Thm}.
\subsection{Permutation (12)(34)}\label{S1}
In the following two sections we present a method which was used by Pawelski~\cite{P} to compute fixes of the permutation $(12)(34)(56)(78)$ acting on $D_8$.
 Consider the first partition $A_4=\{1,2,3,4\}=\{1,2\}+\{3,4\}$,
and two permutations: $\pi=(12)$ and $\rho=(34)$. Furthermore, consider 
a partition of $B^4$ into four subcubes:
\begin{align*}
B^4_{00}&amp;=\{0000,1000,0100,1100\}=B^2\times\{00\}\\
B^4_{10}&amp;=\{0010,1010,0110,1110\}=B^2\times\{10\}\\
B^4_{01}&amp;=\{0001,1001,0101,1101\}=B^2\times\{01\}\\
B^4_{11}&amp;=\{0011,1011,0111,1111\}=B^2\times\{11\}.
\end{align*}
Each of these subcubes is isomorphic to $B^2$.
There are three kinds of cycles of $\pi\circ\rho$ acting on $B^4$:
\begin{itemize}
\item $(0000)$, $(1000,0100)$, $(1100)$. They are contained in $B^4_{00}$ and are 
isomorphic to the cycles of $\pi$ acting on $B^2$.
\item $(0011)$, $(1011,0111)$, $(1111)$. They are contained in $B^4_{11}$ and are isomorphic to the cycles of $\pi$ acting on $B^2$.
\item $(0010,0001)$, $(1010,0101)$, $(0110,1001)$, $(1110.1101)$.
Each of the cycles contains two elements $\{x,y\}$ such that $x\in B^4_{10}$, $y\in B^4_{01}$, and $y=\pi\circ\rho(x)$. Moreover, each $x\in B^4_{10}$ belongs to one of these cycles.
\end{itemize}
Suppose that $f$ is a fix of $\pi\circ\rho$ acting on $D_4$ and consider four restrictions:
$f_{00}=f|_{B^4_{00}}$, 
$f_{10}=f|_{B^4_{10}}$,
$f_{01}=f|_{B^4_{01}}$, and
$f_{11}=f|_{B^4_{11}}$.
They satisfy the following conditions:
\begin{enumerate}
\item $f_{00},f_{11}\in \Fix(\pi,D_2)$. Here we identify
$B^2\times\{00\}$ (and $B^2\times\{11\}$) with $B^2$ and functions 
$B^{B^2\times\{00\}}$ (and $B^{B^2\times\{11\}}$) with $B^{B^2}$.
\item $f_{10},f_{01}\in B^{B^2}=D_2$. 
We identify  functions 
$B^{B^2\times\{10\}}$ (and $B^{B^2\times\{01\}}$) with $B^{B^2}$.
\item $f_{10}=\pi(f_{01})$
\item $f_{00}\le f_{10},f_{10}\le f_{11}$.
\end{enumerate}
On the other hand, if for a function $f$, its restrictions 
$f_{00}=f|_{B^4_{00}}$, 
$f_{10}=f|_{B^4_{10}}$,
$f_{01}=f|_{B^4_{01}}$,
$f_{11}=f|_{B^4_{11}}$ satisfy conditions (1--4), then 
$f$ is a fix of $\pi\circ\rho$ acting on $B^4$.

\subsection{Permutation (12)(34)(56)(78)}\label{S2}
 Consider partition $A_{n+2}=\{1,\dots, n+2\}=\{1,\dots, n\}+\{n+1,n+2\}$,
and two permutations: $\pi$ acting on $\{1,\dots, n\}$ and $\rho=(n+1,n+2)$.
and suppose that cycles of $\pi$ are of length 1 or 2.
Consider a partition of $B^{n+2}$ into four subcubes:
\begin{itemize}
\item $B^{n+2}_{00}=B^n\times\{00\}$

\item $B^{n+2}_{10}=B^n\times\{10\}$

\item $B^{n+2}_{01}=B^n\times\{01\}$

\item $B^{n+2}_{11}=B^n\times\{11\}$.
\end{itemize}

There are three kinds of cycles of $\pi\circ\rho$ acting on $B^{n+2}$:
\begin{itemize}
\item Those contained in $B^{n+2}_{00}$; isomorphic to the cycles of $\pi$ acting on $B^n$.
\item Those contained in $B^{n+2}_{11}$; isomorphic to the cycles of $\pi$ acting on $B^n$.
\item 
Each $x\in B^{n+2}_{10}$ belongs to the cycle with $y=\pi\circ\rho(x)\in B^{n+2}_{01}$.
\end{itemize}
Suppose that $f$ is a fix of $\pi\circ\rho$ acting on $D_{n+2}$ and consider 
four restrictions:
\begin{itemize}
\item $f_{00}=f|_{B^{n+2}_{00}}$, 
\item $f_{10}=f|_{B^{n+2}_{10}}$,
\item $f_{01}=f|_{B^{n+2}_{01}}$,
\item $f_{11}=f|_{B^{n+2}_{11}}$.
\end{itemize}

They satisfy the following conditions:
\begin{enumerate}
\item $f_{00},f_{11}\in \Fix(\pi,D_n)$
\item $f_{10},f_{01}\in B^{B^n}=D_n$
\item $f_{10}=\pi(f_{01})$
\item $f_{00}\le f_{10},f_{10}\le f_{11}$.
\end{enumerate}
On the other hand, if for a function $f$, its restrictions
$f_{00}=f|_{B^{n+2}_{00}}$, 
$f_{10}=f|_{B^{n+2}_{10}}$,
$f_{01}=f|_{B^{n+2}_{01}}$,
$f_{11}=f|_{B^{n+2}_{11}}$ satisfy conditions (1--4), then $f$ is a fix of $\pi\circ\rho$ acting on $D_{n+2}$.

\bigskip

\noindent{\bf Algorithm counting fixes}\\
Input: posets $D_n=B^{B^n}$ and $\Fix(\pi,D_n)$.\\
Output: $|\Fix(\pi\circ\rho, D_{n+2})|$.
\begin{itemize}
\item $\Sum := 0$
\item For each $f_{10}\in D_n$:
\begin{itemize}
\item $f_{01}:=\pi(f_{10})$;
\item $\Down:= |\{g\in \Fix(\pi,D_n): g\le f_{10}\&amp;f_{01}\}|$\qquad//the number of possibilities for choosing $f_{00}$
\item $\Up:= |\{g \in \Fix(\pi,D_n): g\ge f_{10}|f_{01}\}|$ \qquad//the number of possibilities for choosing $f_{11}$
\item $\Sum:= \Sum + \Down\cdot \Up$
\end{itemize}
\item Return $|\Fix(\pi\circ\rho, D_{n+2})|:=\Sum$.
\end{itemize}
Note that for each function $g\in \Fix(\pi,D_n)$ we have

\medskip
   
$g\le f_{10}$ and $g\le f_{01}$ if and only if $g\le f_{10}\&amp;f_{01}$

\medskip

\noindent and

\medskip

$g\ge f_{10}$ and $g\ge f_{01}$ if and only if $g\ge f_{10}|f_{01}$.

A similar algorithm  was used by Pawelski~\cite{P} in order to count  fixes of the permutation $(12)(34)(56)(78)$ acting
on $D_8$.
\begin{example}
Consider the algorithm working on the permutation $(12)(34)$ acting on $D_4$.
Then $D_2=\{0000&lt;0001&lt;0011,0101&lt;0111&lt;1111\}$ and
$\Fix((12),D_2)=\{0000&lt;0001&lt;0111&lt;1111\}$.
\begin{itemize}
\item for $f_{10}=0000$:  $f_{01}=0000$; 
$f_{10}\&amp;f_{01}=0000$; $\Down=1$; 
$f_{10}|f_{01}=0000$; $\Up=4$.
\item for $f_{10}=0001$: $f_{01}=0001$;
$f_{10}\&amp;f_{01}=0001$; $\Down=2$;
$f_{10}|f_{01}=0001$; $\Up=3$.
\item for $f_{10}=0011$: $f_{01}=0101$;
 $f_{10}\&amp;f_{01}=0001$; $\Down=2$;
 $f_{10}|f_{01}=0111$; $\Up=2$.
\item for $f_{10}=0101$: $f_{01}=0011$; 
$f_{10}\&amp;f_{01}=0001$; $\Down=2$; 
$f_{10}|f_{01}=0111$; $\Up=2$.
\item for $f_{10}=0111$: $f_{01}=0111$; 
$f_{10}\&amp;f_{01}=0111$; $\Down=3$;
 $f_{10}|f_{01}=0111$; $\Up=2$.
\item for $f_{10}=1111$: $f_{01}=1111$; 
$f_{10}\&amp;f_{01}=1111$; $\Down=4$; 
$f_{10}|f_{01}=1111 $; $\Up=1$.
\end{itemize}
The algorithm returns $|\Fix((12)(34),D_4)|=
1\cdot 4+2\cdot 3+2\cdot 2+2\cdot 2+3\cdot 2+4\cdot 1=28$.
\end{example}

\section{Generating fixes}
In this section we present one more method to generate  $\Fix(\pi,D_n)$ fixes of a permutation $\pi$ acting on $D_n$.
We start with the poset $\Cycl(\pi,B^n)$ with its array $M(\Cycl(\pi,B^n))$.
For example, consider the permutation $(12)$  acting on $B^3$. The poset
$\Cycl((12),B^3)=\{a&lt;b&lt;c\}\times\{0&lt;1\}=\{a0,b0,c0,a1,b1,c1\}$
has the matrix
$$
M(\Cycl((12)),B^3))=\left(
\begin{array}{cccccc}
1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1\\
0&amp; 1&amp; 1&amp; 0&amp; 1&amp; 1\\
0&amp; 0&amp; 1&amp; 0&amp; 0&amp; 1\\
0&amp; 0&amp; 0&amp; 1&amp; 1&amp; 1\\
0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 1\\
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1\\
\end{array}
\right)
$$
We identify rows of the array with subsets of $\Cycl(\pi,B^n)$
and with functions from $\Cycl(\pi,B^n)$ to $ \{0,1\}$.
It is well known that monotone functions from $\Cycl(\pi,B^n)$ to $\{0,1\}$ may be identified with upsets.
A subset $U\subset \Cycl(\pi,B^n)$ is an {\it upset} if for every $x,y$, we have: 
$$\text{if}\quad x\in U \quad\text{and}\quad x\le y,\quad\text{then}\quad y\in U.$$
Each row in the array $M(\Cycl(\pi,B^n))$ represents the upset
$\Up(c)=\{x\in \Cycl(\pi,B^n):x\ge c\}$.
The set of all upsets can be generated in the following way:
We start with rows of the array $M(\Cycl(\pi,B^n))$. Then we add the zero vector
and the bitwise or $(x|y)$ of every pair $x,y$ already in $\Fix$.

\bigskip

\noindent{\bf Algorithm generating $\Fix(\pi,D_n)$}\\
Input: poset $C=\Cycl(\pi, B^n)$ and its array\\
Output: $\Fix(\pi,D_n)$.
\begin{itemize}
\item $\Fix:=\emptyset$
\item add zero vector to $\Fix$
\item For each $c\in C$:
\begin{itemize}
\item for each $x\in \Fix$ add $x|\Up(c)$ to $\Fix$
\item remove repetitions in $\Fix$
\end{itemize}
\item Return $\Fix(\pi,D_{n}):=\Fix$
\end{itemize}
For example, the algorithm adds four rows to
the array $M(\Cycl((12),B^3))$
$$
\begin{array}{cccccc}
1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1\\
0&amp; 1&amp; 1&amp; 0&amp; 1&amp; 1\\
0&amp; 0&amp; 1&amp; 0&amp; 0&amp; 1\\
0&amp; 0&amp; 0&amp; 1&amp; 1&amp; 1\\
0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 1\\
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1\\
\hline
\hline
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 0\\
0&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1\\
0&amp; 0&amp; 1&amp; 1&amp; 1&amp; 1\\
0&amp; 0&amp; 1&amp; 0&amp; 1&amp; 1\\
\end{array}
$$
These ten rows form the poset $\Fix((12),D_3)$ with the  partial order
defined by
$$x\le y\text{ iff } x|y=y.$$

\section{Tables of fixes}
\label{appa}
In this section we present tables with numbers of fixes of all permutations acting in $D_n$ for $n=3,\ldots,8$.
Values for $n\le 6$ are from~\cite{CS1}, values for $n=7,8$  are from~\cite{CS2,P}.
\begin{center}
$n=3$
\begin{tabular}[h]{|c|c|c|c|}
\hline
 $i$       &amp;$\pi_i$&amp;$\mu_i$ &amp;$|\Fix(\pi_i,D_3)|$\\
\hline
1&amp; $e$      &amp; 1 &amp; 20\\
2&amp; (12)     &amp; 3 &amp; 10 \\
3&amp; (123)    &amp; 2 &amp; 5 \\
\hline
\end{tabular}
\end{center}

\begin{center}
$n=4$
\begin{tabular}[h]{|c|c|c|c|}
\hline
 $i$       &amp;$\pi_i$&amp;$\mu_i$ &amp;$|\Fix(\pi_i,D_4)|$\\
\hline
1&amp; $e$      &amp; 1  &amp; 168\\
2&amp; (12)     &amp; 6  &amp; 50  \\
3&amp; (123)    &amp; 8 &amp; 15 \\ 
4&amp;  (1234)  &amp;  6 &amp;  8 \\
5&amp;  (12)(34)&amp;  3 &amp; 28\\
\hline
\end{tabular}
\end{center}

\begin{center}
$n=5$
\begin{tabular}[h]{|c|c|c|c|}
\hline
 $i$       &amp;$\pi_i$&amp;$\mu_i$ &amp;$|\Fix(\pi_i,D_5)|$\\
\hline
1&amp; $e$      &amp; 1  &amp; 7 581\\
2&amp; (12)     &amp; 10  &amp; 887  \\
3&amp; (123)    &amp; 20 &amp; 105 \\ 
4&amp;  (1234)  &amp;  30 &amp;  35 \\
5&amp;  (12)(34)&amp;  15 &amp; 309\\
6&amp; (12345)  &amp; 24&amp; 11\\
7&amp; (12)(345)&amp; 20 &amp;35\\
\hline
\end{tabular}
\end{center}

\begin{center}
$n=6$
\begin{tabular}[h]{|c|c|c|c|}
\hline
 $i$       &amp;$\pi_i$&amp;$\mu_i$ &amp;$|\Fix(\pi_i,D_6)|$\\
\hline
1&amp; $e$         &amp;1   &amp; 7 828 354\\
2&amp; (12)        &amp;15  &amp; 160 948  \\
3&amp; (123)       &amp;40  &amp; 3 490 \\ 
4&amp; (1234)     &amp;90  &amp;  494 \\

5&amp; (12)(34)   &amp;45  &amp; 24 302\\
6&amp; (12345)     &amp;144 &amp; 64\\
7&amp; (123456)    &amp;120 &amp; 44\\
8&amp; (12)(345)   &amp;120 &amp; 490\\

9&amp; (123)(456)  &amp;40  &amp; 562\\
10&amp;(12)(3456)  &amp;90  &amp; 324\\
11&amp;(12)(34)(56)&amp;15  &amp; 860\\
\hline
\end{tabular}
\end{center}

\begin{center}
$n=7$
\begin{tabular}[h]{|c|c|c|c|}
\hline
 $i$       &amp;$\pi_i$&amp;$\mu_i$ &amp;$|\Fix(\pi_i,D_7)|$\\
\hline
1&amp; $e$            &amp;1   &amp; 2 414 682 040 998\\
2&amp; (12)           &amp;15  &amp; 2 208 001 624  \\
3&amp; (123)          &amp;40  &amp; 2 068 224 \\ 
4&amp;  (1234)        &amp;90  &amp; 60 312 \\
5&amp; (12345)        &amp;144 &amp; 1 548\\
6&amp; (123456)       &amp;120 &amp; 766\\
7&amp; (1234567)      &amp;120 &amp; 101\\

8&amp;  (12)(34)      &amp;45  &amp; 67 922 470\\
9&amp;  (12)(345)     &amp;45  &amp; 59 542\\
10&amp; (12)(3456)    &amp;120 &amp; 26 878\\
11&amp; (12)(34567)   &amp;120 &amp; 264\\

12&amp; (123)(456)    &amp;120 &amp; 69 264\\
13&amp; (123)(4567)   &amp;120 &amp; 294\\

14&amp;(12)(34)(56)   &amp;15  &amp; 12 015 832 860\\
15&amp;(12)(34)(567)  &amp;15  &amp; 10 192\\
\hline
\end{tabular}
\end{center}

\begin{center}
$n=8$
\begin{tabular}[h]{|c|c|c|c|}
\hline
 $i$       &amp;$\pi_i$&amp;$\mu_i$ &amp;$|\Fix(\pi_i,D_8)|$\\
\hline
1&amp; $e$              &amp;1    &amp; 56 130 437 228 687 557 907 788\\
2&amp; (12)             &amp;28   &amp; 101 627 867 809 333 596  \\
3&amp; (123)            &amp;112  &amp; 262 808 891 710 \\ 
4&amp; (1234)           &amp;420  &amp; 424 234 996 \\
5&amp; (12345)          &amp;1344 &amp; 531 708\\
6&amp; (123456)         &amp;3366 &amp; 144 320\\
7&amp; (1234567)        &amp;5760 &amp; 3 858\\
8&amp; (12345678)       &amp;5040 &amp; 2 364\\

9&amp;  (12)(34)        &amp;210 &amp; 182 755 441 509 724\\
10&amp; (12)(345)       &amp;1120&amp; 401 622 018\\
11&amp; (12)(3456)      &amp;2520&amp; 93 994 196\\
12&amp; (12)(34567)     &amp;4032&amp; 21 216\\
13&amp; (12)(345678)    &amp;3360&amp; 70 096\\

14&amp; (123)(456)      &amp;1120&amp; 535 426 780\\
15&amp; (123)(4567)     &amp;3360&amp; 25 168\\
16&amp; (123)(45678)    &amp;2688&amp; 870\\

17&amp; (1234)(5678)    &amp;1260&amp; 3 211 276\\

18&amp;(12)(34)(56)     &amp;420 &amp; 7 377 670 895 900\\
19&amp;(12)(34)(567)    &amp;1680&amp; 16 380 370\\
20&amp;(12)(34)(5678)   &amp;1260&amp; 37 834 164\\

21&amp;(12)(345)(678)   &amp;1120&amp; 3 607 596\\
22&amp;(12)(34)(56)(78) &amp;105 &amp; 2 038 188 253 420\\
\hline
\end{tabular}
\end{center}

\section{Known values of $d_n$ and $r_n$}

\begin{center}
\begin{tabular}[h]{|c|c|c|}
\hline
 $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}
\end{center}

These are sequences \seqnum{A000372} and 
\seqnum{A003182} in the {\it On-Line Encyclopedia of Integer Sequences}
\cite{Sloane}.


\begin{thebibliography}{99}

\bibitem{B}
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. 

\bibitem{C}
 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{CW}
P.  De Causmaecker and S. De Wannemacker, 
On the number of antichains of sets in a finite universe, 
Arxiv preprint 1407.4288v2 [math.CO], 
available at \url{https://arxiv.org/abs/1407.4288}, 2014.

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

\bibitem{Ch2}
R. Church, 
Enumeration by rank of the elements of the free distributive lattice with 7 generators, 
\emph{Notices Amer. Math. Soc.} {\bf 12} (1965) 724.

\bibitem{D}
R. Dedekind, 
\"{U}ber Zerlegungen von Zahlen durch ihre gr\"{o}\ss ten gemeinsamen Teiler,
\emph{Festschrift Hoch. Braunschweig u. ges. Werke II}
(1897) 103--148.

\bibitem{FMSS}
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{CS1}
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{CS2}
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{M}
G. E. Martin, \emph{Counting: The Art of Enumerative Combinatorics,} Springer, 2001.

\bibitem{P}
B. Pawelski, 
On the number of inequivalent monotone Boolean functions of 8 variables, 
\emph{J. Integer Sequences} {\bf 25} (2022), 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL25/Pawelski/pawelski7.html}{Article 22.7.7}.

\bibitem{Sloane}
N. J. A. Sloane et al.,
{\it The On-Line Encyclopedia of Integer Sequences}, 
2022.  Available at \url{https://oeis.org}.
 
\bibitem{SY}
 T. Stephen and T. Yusun, Counting inequivalent monotone Boolean functions, \emph{Discrete Appl. Math.}, {\bf 167} (2014), 15--24.

\bibitem{Wa}
M. Ward, 
Note on the order of the free distributive lattice, 
\emph{Bull. Amer. Math. Soc.}
{\bf 52} (1946) 423.

\bibitem{W}
D. Wiedemann, A computation of the eighth Dedekind number, {\em Order} {\bf 8} (1991), 5--6.
\end{thebibliography}


\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords: } monotone Boolean function,
Dedekind number, equivalence class, fix.


\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A000372} and
\seqnum{A003182}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received May 8 2022;
revised versions received  September 19 2022; October 26 2022.
Published in {\it Journal of Integer Sequences}, November 20 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>