Fixes of Permutations Acting on Monotone Boolean Functions

Andrzej Szepietowski Institute of Informatics Faculty of Mathematics,Physics and Informatics University of Gdańsk 80-308 Gdańsk Poland

                     matszp@inf.ug.edu.pl

Abstract We present a few algorithms and methods to count fixes of permutations acting on

monotone Boolean functions.

1 Introduction

Let B denote the set {0, 1} and B^{n} the set of n-element sequences of B. A 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 ≤ 0, 0 ≤ 1, 1 ≤ 1) and the partial order in B^{n}: for any two elements: x = (x_{1}, …, x_{n}), y = (y_{1}, …, y_{n}) in B^{n},

x ≤ y if and only if x_{i} ≤ y_{i} for all 1 ≤ i ≤ n.

The function h : B^{n} → B is monotone if

x ≤ y ⇒ h(x) ≤ 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, …, 8 are presented in the table at the end of this paper. The values d_{n} for n ≤ 4 were published by Dedekind [6], Church [4, 5] gave the values d_{5} and d_{7}, Ward [14] the value d_{6}, and the last known value d_{8} was published by Wiedemann [15]. Dedekind numbers were also considered in [1, 2, 3, 7, 13].

We have the partial order in D_{n} defined as follows:

g ≤ h if and only if g(x) ≤ h(x) for all x ∈ 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 ∈ D_{1} can be represented as a concatenation g(0) ∗ g(1), where g(0), g(1) ∈ D_{0} and g(0) ≤ g(1). Hence, D_{1} = {00, 01, 11}. Each element g ∈ 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} ∈ D_{1} and g_{0} ≤ g_{1}. Hence, D_{2} = {0000, 0001, 0011, 0101, 0111, 1111}. Similarly any element g ∈ D_{n} can be represented as a concatenation g_{0} ∗ g_{1}, where g_{0}, g_{1} ∈ D_{n−1} and g_{0} ≤ g_{1}.

Let S_{n} denote the set of permutations on {1, …, n}. Every permutation π ∈ S_{n} defines the permutation on B^{n} by π(x) = x ∘ π (we treat each element x ∈ B^{n} as a function x : {1, …, n} → {0, 1}). Note that x ≤ y if and only if π(x) ≤ π(y). The permutation π also generates the permutation on D_{n}. Namely, by π(g) = g ∘ π. Note that π(g) is monotone if g is monotone. Two functions f, g ∈ D_{n} are equivalent if there is a permutation π ∈ S_{n} such that f = π(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 ≤ 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 [10, §38]. Namely,

r_{n} = \frac{1}{n!} ∑_{π∈S_{n}} | Fix(π, D_{n})|,

where Fix(π, D_{n}) is the set of fixes of the permutation π acting on D_{n}. A function f ∈ D_{n} is a fix of π if π(f) = f.

In 1985 and 1986 Liu and Hu [8, 9] used Burnside’s lemma to compute r_{n} for all n ≤ 7. Recently, Pawelski [11] 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 4 and Lemma 6 which give formulas for the set of fixes of the composition π ∘ ρ of two permutations, provided π and ρ satisfy certain conditions. A special case of Lemma 6 was used by Pawelski [11] to count and generate fixes of several permutations acting on D_{n}. For completeness, in Sections 6.5 and 6.6, we present a method which was used by Pawelski [11] to compute fixes of the permutation (12)(34)(56)(78) acting on D_{8}.

2 Posets

A poset (partially ordered set) (S, ≤) consists of a set S (called the carrier) together with a binary relation (partial order) ≤ which is reflexive, transitive and antisymmetric. For two posets (S, ≤) and (T, ≤) by S × T we denote the cartesian product with the order defined as follows: (a, b) ≤ (c, d) iff a ≤ c and b ≤ d. For two disjoint posets (S, ≤) and (T, ≤) by S + T we denote the disjoint union (sum) with the order defined as follows:

x ≤ y iff (x, y ∈ S and x ≤ y) or (x, y ∈ T and x ≤ y).

Given two posets (S, ≤) and (T, ≤) a function f : S → T is monotone, if x ≤ y implies f(x) ≤ 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 ≤ g if and only if f(x) ≤ g(x) for all x ∈ S.

In this paper we use the following notation:

• 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.

• B denotes the poset of two bits {0, 1} ordered by 0 ≤ 0, 0 ≤ 1, 1 ≤ 1.

• 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

– the poset of all subsets of {1, …, n} ordered by the inclusion,

– the poset of all n-strings of bits, where (x_{1}, …, x_{n}) ≤ (y_{1}, …, y_{n}) iff x_{i} ≤ y_{i} for all i.

• 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.

• P_{n} denotes the path (or chain) P_{n} = {p_{1} < ⋯ < p_{n}}. Note that B^{P_{n}} = P_{n+1}.

We will use the following lemma which is a part of the folklore and can be easily proved.

Lemma 1. For three posets R, S, T, (1) If S and T are disjoint, then the poset R^{S+T} is isomorphic to R^{S} × R^{T}.

(2) The poset R^{S×T} is isomorphic to (R^{S})^{T} and to (R^{T})^{S}.

As a corollary we have the following lemma. Similar lemmas in other formulations were used by Wiedemann [15], by Fidytek, Mostowski, Somla and Szepietowski [7], and by Campo [2] in order to compute d_{n} = |D_{n}|.

Lemma 2.

(a) A_{k+m} = A_{k} + A_{m}

(b) B^{k+m} = B^{k} × B^{m} (c) D_{k+m} = (D_{k})^{B^{m}}

Proof.

(a) is obvious.

(b) B^{k+m} = B^{A_{k+m}} = B^{A_{k}+A_{m}} = B^{A_{k}} × B^{A_{m}} = B^{k} × B^{m}.

(c) D_{k+m} = B^{B^{k+m}} = B^{B^{k}×B^{m}} = (B^{B^{k}})^{B^{m}} = (D_{k})^{B^{m}}.

3 Arrays

Let M(S) denote the array of the poset S. For i, j ∈ S, we have M(S)[i, j] = 1 if i ≤ j, and M(S)[i, j] = 0 otherwise. For example, for the poset D_{1} = {00 < 01 < 11}, its array

M(D_{1}) = ( \begin{matrix}1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{matrix} )

The poset D_{1} is equal (isomorphic) to the poset of the path P_{3} = {a < b < 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×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 ≥ 2, we have

Sum(M(D_{n})) = |D_{n}^{B}| = |(B^{B^{n}})^{B}| = |B^{B^{n}×B}| = |B^{B^{n+1}}| = |D_{n+1}| = d_{n+1}.

Consider the product M(S)^{2} = M(S) × M(S). Then M(S)^{2}[i, j] = |{k ∈ S : i ≤ k ≤ j}| which is the number of elements in the interval [i, j] ⊂ S. Moreover, the elements of M(S)^{2} are connected to monotone functions from the path P_{3} = {a < b < 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} = ( \begin{matrix}1 & 2 & 3 \\ 0 & 1 & 2 \\ 0 & 0 & 1 \end{matrix} )

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×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]·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×B^{2}}| = |B^{B^{3}}| = d_{3}. Similarly, for every n ≥ 2, we have

SumSq(M(D_{n})^{2}) = |D_{n}^{B^{2}}| = |(B^{B^{n}})^{B^{2}}| = |B^{B^{n}×B^{2}}| = |B^{B^{n+2}}| = d_{n+2}.

This fact was used in another formulation by Fidytek, Mostowski, Somla and Szepietowski [7].

Consider the product M(S)^{3} = M(S) × M(S) × M(S). The elements of M(S)^{3} are connected to monotone functions from the path P_{4} = (a < b < c < d) to S. Indeed, M(S)^{3}[i, j] is equal to the number of pairs x, y, such that i ≤ x ≤ y ≤ 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} = ( \begin{matrix}1 & 3 & 6 \\ 0 & 1 & 3 \\ 0 & 0 & 1 \end{matrix} )

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×P_{4}}|.

4 Symmetries

Let S_{n} denote the set of permutations on {1, …, n}. Every permutation π ∈ S_{n} defines the permutation on B^{n} by π(x) = x ∘ π. Here we treat elements x ∈ B^{n} as functions x : {1, …, n} → {0, 1}. Note that x ≤ y if and only if π(x) ≤ π(y).

Example 3. Consider two permutations: π_{1} = (12) and π_{2} = (123), both acting on B^{3}:

\begin{matrix}x & 000 & 100 & 010 & 110 & 001 & 101 & 011 & 111 \\ π_{1}(x) & 000 & 010 & 100 & 110 & 001 & 011 & 101 & 111 \\ π_{2}(x) & 000 & 001 & 100 & 101 & 010 & 011 & 110 & 111 \end{matrix}

Each permutation π acting on B^{n} generates a permutation on D_{n} = B^{B^{n}}. Namely, π(g) = g ∘ π. Note that π(g) is monotone if g is monotone. Two functions f, g ∈ D_{n} are equivalent if there is a permutation π ∈ S_{n} such that f = π(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 [10, §38]. Known values of r_{n} (for n ≤ 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!} ∑_{π∈S_{n}} | Fix(π, D_{n})|,

where Fix(π, D_{n}) is the set of fixes of the permutation π acting on D_{n}. A function f ∈ D_{n} is a fix of π if π(f) = f. Since conjugate group elements have the same number of fixed points, | Fix(π, D_{n})| depends only on the cycle type of π. By the cycle type of a permutation π, we mean the data giving the lengths of disjoint cycles whose product is π 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 π_{1}, …, π_{k(n)} is an (arbitrarily chosen) sequence of representatives of all cycle types in S_{n}. For 1 ≤ i ≤ k(n), let μ_{i} be the number of elements of S_{n} of the same cycle type as π_{i} (see the tables in Section 8). Then

r_{n} = \frac{1}{n!} ∑_{i=1}^{k(n)} μ_{i} · | Fix(π_{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 π ∈ S_{n} and suppose that π when acting on B^{n} is a product of disjoint cycles π = C_{1} ∘ ⋯ ∘ C_{r}, then a monotone function f : B^{n} → B is a fix of π if and only if f is constant on every cycle C_{i}. Let Cycl(π, B^{n}) denote the set of cycles {C_{1}, …, C_{r}}, and let ≤ be the partial order defined in the following way: C_{i} ≤ C_{j} if and only if there exist x ∈ C_{i} and y ∈ C_{j} such that x ≤ y (we identify each cycle with the set of its elements). Hence, the poset Fix(π, D_{n}) is isomorphic to the poset B^{Cycl(π,B^{n})} of monotone functions from Cycl(π, B^{n}) to B = {0, 1} and we can represent fixes in Fix(π, D_{n}) as sequences of bits of length | Cycl(π, B^{n})|.

For the identity permutation e, each x ∈ 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} < C_{2} < 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}}.

5 Main results

Theorem 4. Consider a partition of the antichain A_{n} = {1, …, n} into two disjoint antichains A_{k} = {1, …, k} and A_{m} = {k + 1, … n}, where n = k + m; and two permutations: one π acting on A_{k} and ρ acting on A_{m}. Suppose that each cycle of π has a length which is coprime with the length of every cycle of ρ then

Fix(π ∘ ρ, D_{n}) = Fix(π, D_{k})^{Cycl(ρ,B^{m})} = Fix(ρ, D_{m})^{Cycl(π,B^{k})}.

Proof. The cube B^{n} is isomorphic to the cartesian product B^{n} = B^{k} × B^{m}. Suppose that we have two cycles: one C_{r} of π acting on B^{k} and the other C_{s} of ρ acting on B^{m}. The lengths of the two cycles are coprime, so the product C_{r} × C_{s} is a cycle of π ∘ ρ acting on B^{n}. Furthermore, each cycle of π has a length which is coprime with the length of every cycle of ρ so

Cycl(π ∘ ρ, B^{n}) = Cycl(π, B^{k}) × Cycl(ρ, B^{m})

and

Fix(π ∘ ρ, D_{n}) = B^{Cycl(π∘ρ,B^{n})} = B^{Cycl(π,B^{k})×Cycl(ρ,B^{m})}
= Fix(π, D_{k})^{Cycl(ρ,B^{m})} = Fix(ρ, D_{m})^{Cycl(π,B^{k})}.

Example 5. Consider the partition A_{5} = A_{3} + A_{2}, with A_{3} = {1, 2, 3} and A_{2} = {4, 5}, and two permutations: π = (123) and ρ = (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} < C_{2} < C_{3} < 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} < c_{2} < c_{3}).

Furthermore, consider the two cycles C_{2} = (100, 001, 010} of π acting on B^{{1,2,3}} and c_{2} = {10, 01} of ρ acting on B^{{4,5}}. Their cartesian product

C_{2} × c_{2} = {10010, 00101, 01010, 10001, 00110, 01001}

forms one cycle of π ∘ ρ acting on B^{5} = B^{3} × B^{2}. The poset of cycles of π ∘ ρ acting on B^{5} is the cartesian product P_{4} × P_{3} and

| Fix((123)(45), D_{5})| = |B^{P_{4}×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}) = ( \begin{matrix}1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{matrix} )

M(P_{4})^{3} = ( \begin{matrix}1 & 3 & 6 & 10 \\ 0 & 1 & 3 & 6 \\ 0 & 0 & 1 & 3 \\ 0 & 0 & 0 & 1 \end{matrix} )

Fix((123)(45), D_{5}) = |P_{4}^{P_{4}}| = Sum(M(P_{4})^{3}) = 35. We can also use the arrays

M(P_{5}) = ( \begin{matrix}1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \end{matrix} )

M(P_{5})^{2} = ( \begin{matrix}1 & 2 & 3 & 4 & 5 \\ 0 & 1 & 2 & 3 & 4 \\ 0 & 0 & 1 & 2 & 3 \\ 0 & 0 & 0 & 1 & 3 \\ 0 & 0 & 0 & 0 & 1 \end{matrix} )

| Fix((123)(45), D_{5})| = |P_{5}^{P_{3}}| = Sum(M(P_{5})^{2}) = 35.

The following lemma is a direct consequence of the theorem. In the special case with m = 1 the lemma was used by Pawelski [11] to count and generate fixes of several permutations acting on D_{n}.

Lemma 6. Suppose that a permutation π is acting on B^{k} and n > k. Then when we consider π acting on B^{n},

Fix(π, D_{n}) = (Fix(π, D_{k}))^{B^{m}} = D_{m}^{Cycl(π,B^{k})}

where m = n − k.

Proof. The permutation π is acting on {1, …, k} and on B^{k}. We can say that π also acts on {1, …, n} and on B^{n}, by identifying π with π ∘ e. Every cycle in Cycl(e, B^{m}) has length 1, hence, Cycl(e, B^{m}) = B^{m} and

Cycl(π ∘ e, B^{n}) = Cycl(π, B^{k}) × Cycl(e, B^{m}) = Cycl(π, B^{k}) × B^{m}

and

Fix(π, D_{n}) = Fix(π ∘ e, D_{n}) = B^{Cycl(π,B^{k})×B^{m}} = (Fix(π, D_{k}))^{B^{m}} = D_{m}^{Cycl(π,B^{k})}.

6 Applications

In this section we present a few examples that illustrate concepts from Section 3 and applications of Theorem 4 and Lemma 6.

Consider the poset D_{2} = B^{B^{2}} = {0000, 0001, 0011, 0101, 0111, 1111} and its array

M(D_{2}) = ( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} )

Consider the array

M(D_{2})^{2} = ( \begin{matrix}1 & 2 & 3 & 3 & 5 & 6 \\ 0 & 1 & 2 & 2 & 4 & 5 \\ 0 & 0 & 1 & 0 & 2 & 3 \\ 0 & 0 & 0 & 1 & 2 & 3 \\ 0 & 0 & 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} ) .

Now Sum(M(D_{2})^{2}) = 50, which is equal to |D_{2}^{P_{3}}| = |(B^{B^{2}})^{P_{3}}| = |B^{B^{2}×P_{3}}| = | Fix((12), D_{4})|; see Lemma 6 and Section 3. Similarly, SumSq(M(D_{2})^{2}) = 168, which is equal to |D_{2}^{B^{2}}| = |(B^{B^{2}})^{B^{2}}| = |B^{B^{2}×B^{2}}| = |B^{B^{4}}| = |D_{4}| = d_{4}. Furthermore,

M(D_{2})^{3} = ( \begin{matrix}1 & 3 & 6 & 6 & 14 & 20 \\ 0 & 1 & 3 & 3 & 9 & 14 \\ 0 & 0 & 1 & 0 & 3 & 6 \\ 0 & 0 & 0 & 1 & 3 & 6 \\ 0 & 0 & 0 & 0 & 1 & 3 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} ) .

Now Sum(M(D_{2})^{3}) = 105, which is equal to |D_{2}^{P_{4}}| = |(B^{B^{2}})^{P_{4}}| = |B^{B^{2}×P_{4}}| = | Fix((123), D_{5})|.

6.1 Permutation (12)

Consider the permutation π = (12). When π 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} × B and Fix((12), D_{3}) = B^{P_{3}×B}; see Lemma 6. By Section 3, the number of fixes can be computed either by

| Fix((12), D_{3})| = |B^{P_{3}×B}| = |(B^{P_{3}})^{B}| = |P_{4}^{B}| = Sum(M(P_{4})) = 10,

or by

| Fix((12), D_{3})| = |B^{P_{3}×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} × B^{2} and Fix((12), D_{4}) = B^{P_{3}×B^{2}}. The number of fixes can be computed either by

| Fix((12), D_{4})| = |B^{P_{3}×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}×B^{2}}| = |(B^{B^{2}})^{P_{3}}| = |D_{2}^{P_{3}}| = Sum(M(D_{2})^{2}) = 50.

6.2 Permutation (123)

Consider the permutation π = (123). When π 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} × B and Fix((123), D_{4}) = B^{P_{4}×B}, see Lemma 6. By Section 3, the number of fixes can be computed either by

| Fix((123), D_{4})| = |B^{P_{4}×B}| = |(B^{P_{4}})^{B}| = |P_{5}^{B}| = Sum(M(P_{5})) = 15,

or by

| Fix((123), D_{4})| = |B^{P_{4}×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} × B^{2} and Fix((123), D_{5}) = B^{P_{4}×B^{2}}. The number of fixes can be computed either by

| Fix((123), D_{5})| = |B^{P_{4}×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}×B^{2}}| = |(B^{B^{2}})^{P_{4}}| = |D_{2}^{P_{4}}| = Sum(M(D_{2})^{3}) = 105.

6.3 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} < C_{1} < C_{2}, C_{3} < C_{4} < C_{5}. There are 8 fixes of (1234) acting on D_{4} with the array

M(Fix((1234), D_{4})) = ( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} )

Sum(M(Fix((1234), D_{4}))) = 35 = | Fix((1234), D_{5}))|, see Lemma 6 and Section 3. Furthermore,

M(Fix((1234), D_{4}))^{2} = ( \begin{matrix}1 & 2 & 3 & 4 & 4 & 6 & 7 & 8 \\ 0 & 1 & 2 & 3 & 3 & 5 & 6 & 7 \\ 0 & 0 & 1 & 2 & 2 & 4 & 5 & 6 \\ 0 & 0 & 0 & 1 & 0 & 2 & 3 & 4 \\ 0 & 0 & 0 & 0 & 1 & 2 & 3 & 4 \\ 0 & 0 & 0 & 0 & 0 & 1 & 2 & 3 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} )

and SumSq(M(Fix((1234), D_{4}))^{2}) = 494 = | Fix((1234), D_{6}))|. Also

M(Fix((1234), D_{4}))^{3} = ( \begin{matrix}1 & 3 & 6 & 10 & 10 & 20 & 27 & 35 \\ 0 & 1 & 3 & 6 & 6 & 14 & 20 & 27 \\ 0 & 0 & 1 & 3 & 3 & 9 & 14 & 20 \\ 0 & 0 & 0 & 1 & 0 & 3 & 6 & 10 \\ 0 & 0 & 0 & 0 & 1 & 3 & 6 & 10 \\ 0 & 0 & 0 & 0 & 0 & 1 & 3 & 6 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 3 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} )

and Sum(M(Fix((1234), D_{4}))^{3}) = 294 = | Fix((1234)(567), D_{7}))|.

6.4 Permutation (12345)

The permutation (12345) acting on B^{5} has eight cycles:

• C_{0} = {00000},

• C_{1} = {10000, 00001, 00010, 00100, 01000},

• C_{2} = {11000, 10001, 00011, 00110, 01100},

• C_{3} = {10100, 01001, 10010, 00101, 01010},

• C_{4} = {11100, 11001, 10011, 00111, 01110},

• C_{5} = {10110, 01101, 11010, 10101, 01011},

• C_{6} = {11110, 11101, 11011, 10111, 01111},

• C_{7} = {11111}.

They are of length 1 or 5 and ordered by C_{0} < C_{1} < C_{2}, C_{3} < C_{4}, C_{5} < C_{6} < C_{7}. There are 11 fixes of (12345) acting on D_{5} with the array

M(Fix((12345), D_{5})) = ( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} ) .

We have Sum(M(Fix((12345), D_{5}))) = 64 = | Fix((12345), D_{6}))| and

M(Fix((12345), D_{5}))^{2} = ( \begin{matrix}1 & 2 & 3 & 4 & 4 & 6 & 7 & 7 & 9 & 10 & 11 \\ 0 & 1 & 2 & 3 & 3 & 5 & 6 & 6 & 8 & 9 & 10 \\ 0 & 0 & 1 & 2 & 2 & 4 & 5 & 5 & 7 & 8 & 9 \\ 0 & 0 & 0 & 1 & 0 & 2 & 3 & 3 & 5 & 6 & 7 \\ 0 & 0 & 0 & 0 & 1 & 2 & 3 & 3 & 5 & 6 & 7 \\ 0 & 0 & 0 & 0 & 0 & 1 & 2 & 2 & 4 & 5 & 6 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 3 & 4 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 2 & 3 & 4 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 2 & 3 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} ) .

By Theorem 4 and Section 3, we have Sum(M(Fix((12345), D_{5}))^{2}) = 264 = | Fix((12345)(67), D_{7}))| and by Lemma 6, we have

SumSq(M(Fix((12345), D_{5}))^{2}) = 1548 = | Fix((12345), D_{7}))|.

Also

M(Fix((12345), D_{5}))^{3} = ( \begin{matrix}1 & 3 & 6 & 10 & 10 & 20 & 27 & 27 & 43 & 53 & 64 \\ 0 & 1 & 3 & 6 & 6 & 14 & 20 & 20 & 34 & 43 & 53 \\ 0 & 0 & 1 & 3 & 3 & 9 & 14 & 14 & 26 & 34 & 43 \\ 0 & 0 & 0 & 1 & 0 & 3 & 6 & 6 & 14 & 20 & 27 \\ 0 & 0 & 0 & 0 & 1 & 3 & 6 & 6 & 14 & 20 & 27 \\ 0 & 0 & 0 & 0 & 0 & 1 & 3 & 3 & 9 & 14 & 20 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 3 & 6 & 10 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 3 & 6 & 10 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 3 & 6 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 3 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} )

and Sum(M(Fix((12345), D_{5}))^{3}) = 870 = | Fix((12345)(678), D_{8}))|; see Theorem 4.

6.5 Permutation (12)(34)

In the following two sections we present a method which was used by Pawelski [11] 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: π = (12) and ρ = (34). Furthermore, consider a partition of B^{4} into four subcubes:

B_{00}^{4} = {0000, 1000, 0100, 1100} = B^{2} × {00}
B_{10}^{4} = {0010, 1010, 0110, 1110} = B^{2} × {10}
B_{01}^{4} = {0001, 1001, 0101, 1101} = B^{2} × {01}
B_{11}^{4} = {0011, 1011, 0111, 1111} = B^{2} × {11}.

Each of these subcubes is isomorphic to B^{2}. There are three kinds of cycles of π ∘ ρ acting on B^{4}:

• (0000), (1000, 0100), (1100). They are contained in B_{00}^{4} and are isomorphic to the cycles of π acting on B^{2}.

• (0011), (1011, 0111), (1111). They are contained in B_{11}^{4} and are isomorphic to the cycles of π acting on B^{2}.

• (0010, 0001), (1010, 0101), (0110, 1001), (1110.1101). Each of the cycles contains two elements {x, y} such that x ∈ B_{10}^{4}, y ∈ B_{01}^{4}, and y = π ∘ ρ(x). Moreover, each x ∈ B_{10}^{4} belongs to one of these cycles.

Suppose that f is a fix of π ∘ ρ acting on D_{4} and consider four restrictions: f_{00} = f|_{B_{00}^{4}}, f_{10} = f|_{B_{10}^{4}}, f_{01} = f|_{B_{01}^{4}}, and f_{11} = f|_{B_{11}^{4}}. They satisfy the following conditions:

1. f_{00}, f_{11} ∈ Fix(π, D_{2}). Here we identify B^{2}×{00} (and B^{2}×{11}) with B^{2} and functions B^{B^{2}×{00}} (and B^{B^{2}×{11}}) with B^{B^{2}}.

2. f_{10}, f_{01} ∈ B^{B^{2}} = D_{2}. We identify functions B^{B^{2}×{10}} (and B^{B^{2}×{01}}) with B^{B^{2}}.

3. f_{10} = π(f_{01})

4. f_{00} ≤ f_{10}, f_{10} ≤ f_{11}.

On the other hand, if for a function f, its restrictions f_{00} = f|_{B_{00}^{4}}, f_{10} = f|_{B_{10}^{4}}, f_{01} = f|_{B_{01}^{4}}, f_{11} = f|_{B_{11}^{4}} satisfy conditions (1–4), then f is a fix of π ∘ ρ acting on B^{4}.

6.6 Permutation (12)(34)(56)(78)

Consider partition A_{n+2} = {1, …, n+2} = {1, …, n}+{n+1, n+2}, and two permutations: π acting on {1, …, n} and ρ = (n + 1, n + 2). and suppose that cycles of π are of length 1 or 2. Consider a partition of B^{n+2} into four subcubes:

• B_{00}^{n+2} = B^{n} × {00}

• B_{10}^{n+2} = B^{n} × {10}

• B_{01}^{n+2} = B^{n} × {01}

• B_{11}^{n+2} = B^{n} × {11}. There are three kinds of cycles of π ∘ ρ acting on B^{n+2}:

• Those contained in B_{00}^{n+2}; isomorphic to the cycles of π acting on B^{n}.

• Those contained in B_{11}^{n+2}; isomorphic to the cycles of π acting on B^{n}.

• Each x ∈ B_{10}^{n+2} belongs to the cycle with y = π ∘ ρ(x) ∈ B_{01}^{n+2}. Suppose that f is a fix of π ∘ ρ acting on D_{n+2} and consider four restrictions:

• f_{00} = f|_{B_{00}^{n+2}},

• f_{10} = f|_{B_{10}^{n+2}},

• f_{01} = f|_{B_{01}^{n+2}},

• f_{11} = f|_{B_{11}^{n+2}}. They satisfy the following conditions:

1. f_{00}, f_{11} ∈ Fix(π, D_{n})

2. f_{10}, f_{01} ∈ B^{B^{n}} = D_{n}

3. f_{10} = π(f_{01})

4. f_{00} ≤ f_{10}, f_{10} ≤ f_{11}. On the other hand, if for a function f, its restrictions f_{00} = f|_{B_{00}^{n+2}}, f_{10} = f|_{B_{10}^{n+2}}, f_{01} = f|_{B_{01}^{n+2}}, f_{11} = f|_{B_{11}^{n+2}} satisfy conditions (1–4), then f is a fix of π ∘ ρ acting on D_{n+2}. Algorithm counting fixes Input: posets D_{n} = B^{B^{n}} and Fix(π, D_{n}). Output: | Fix(π ∘ ρ, D_{n+2})|.

• Sum := 0

• For each f_{10} ∈ D_{n}:

– f_{01} := π(f_{10});

– Down := |{g ∈ Fix(π, D_{n}) : g ≤ f_{10}&f_{01}}| //the number of possibilities for choosing f_{00}

– Up := |{g ∈ Fix(π, D_{n}) : g ≥ f_{10}|f_{01}}| //the number of possibilities for choosing f_{11}

– Sum := Sum + Down · Up

• Return | Fix(π ∘ ρ, D_{n+2})| := Sum. Note that for each function g ∈ Fix(π, D_{n}) we have

g ≤ f_{10} and g ≤ f_{01} if and only if g ≤ f_{10}&f_{01} and

g ≥ f_{10} and g ≥ f_{01} if and only if g ≥ f_{10}|f_{01}. A similar algorithm was used by Pawelski [11] in order to count fixes of the permutation

(12)(34)(56)(78) acting on D_{8}. Example 7. Consider the algorithm working on the permutation (12)(34) acting on D_{4}. Then D_{2} = {0000 < 0001 < 0011, 0101 < 0111 < 1111} and Fix((12), D_{2}) = {0000 < 0001 < 0111 < 1111}.

• for f_{10} = 0000: f_{01} = 0000; f_{10}&f_{01} = 0000; Down = 1; f_{10}|f_{01} = 0000; Up = 4.

• for f_{10} = 0001: f_{01} = 0001; f_{10}&f_{01} = 0001; Down = 2; f_{10}|f_{01} = 0001; Up = 3.

• for f_{10} = 0011: f_{01} = 0101; f_{10}&f_{01} = 0001; Down = 2; f_{10}|f_{01} = 0111; Up = 2.

• for f_{10} = 0101: f_{01} = 0011; f_{10}&f_{01} = 0001; Down = 2; f_{10}|f_{01} = 0111; Up = 2.

• for f_{10} = 0111: f_{01} = 0111; f_{10}&f_{01} = 0111; Down = 3; f_{10}|f_{01} = 0111; Up = 2.

• for f_{10} = 1111: f_{01} = 1111; f_{10}&f_{01} = 1111; Down = 4; f_{10}|f_{01} = 1111; Up = 1. The algorithm returns | Fix((12)(34), D_{4})| = 1 · 4 + 2 · 3 + 2 · 2 + 2 · 2 + 3 · 2 + 4 · 1 = 28.

7 Generating fixes

In this section we present one more method to generate Fix(π, D_{n}) fixes of a permutation π acting on D_{n}. We start with the poset Cycl(π, B^{n}) with its array M(Cycl(π, B^{n})). For example, consider the permutation (12) acting on B^{3}. The poset Cycl((12), B^{3}) = {a < b < c} × {0 < 1} = {a0, b0, c0, a1, b1, c1} has the matrix

M(Cycl((12)), B^{3})) = ( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} )

We identify rows of the array with subsets of Cycl(π, B^{n}) and with functions from Cycl(π, B^{n}) to {0, 1}. It is well known that monotone functions from Cycl(π, B^{n}) to {0, 1} may be identified with upsets. A subset U ⊂ Cycl(π, B^{n}) is an upset if for every x, y, we have:

if x ∈ U and x ≤ y, then y ∈ U.

Each row in the array M(Cycl(π, B^{n})) represents the upset Up(c) = {x ∈ Cycl(π, B^{n}) : x ≥ c}. The set of all upsets can be generated in the following way: We start with rows of the array M(Cycl(π, B^{n})). Then we add the zero vector and the bitwise or (x|y) of every pair x, y already in Fix.

Algorithm generating Fix(π, D_{n}) Input: poset C = Cycl(π, B^{n}) and its array Output: Fix(π, D_{n}).

• Fix := ∅

• add zero vector to Fix

• For each c ∈ C:

– for each x ∈ Fix add x| Up(c) to Fix

– remove repetitions in Fix

• Return Fix(π, D_{n}) := Fix For example, the algorithm adds four rows to the array M(Cycl((12), B^{3}))

1 1 1 1 1 1
0 1 1 0 1 1
0 0 1 0 0 1
0 0 0 1 1 1
0 0 0 0 1 1
0 0 0 0 0 1
0 0 0 0 0 0
0 1 1 1 1 1
0 0 1 1 1 1
0 0 1 0 1 1

These ten rows form the poset Fix((12), D_{3}) with the partial order defined by x ≤ y iff x|y = y.

8 Tables of fixes

In this section we present tables with numbers of fixes of all permutations acting in D_{n} for n = 3, …, 8. Values for n ≤ 6 are from [8], values for n = 7, 8 are from [9, 11].

n = 3 \begin{matrix}i & π_{i} & μ_{i} & | Fix(π_{i}, D_{3})| \\ 1 & e & 1 & 20 \\ 2 & (12) & 3 & 10 \\ 3 & (123) & 2 & 5 \end{matrix}

n = 4 \begin{matrix}i & π_{i} & μ_{i} & | Fix(π_{i}, D_{4})| \\ 1 & e & 1 & 168 \\ 2 & (12) & 6 & 50 \\ 3 & (123) & 8 & 15 \\ 4 & (1234) & 6 & 8 \\ 5 & (12)(34) & 3 & 28 \end{matrix}

n = 5 \begin{matrix}i & π_{i} & μ_{i} & | Fix(π_{i}, D_{5})| \\ 1 & e & 1 & 7 581 \\ 2 & (12) & 10 & 887 \\ 3 & (123) & 20 & 105 \\ 4 & (1234) & 30 & 35 \\ 5 & (12)(34) & 15 & 309 \\ 6 & (12345) & 24 & 11 \\ 7 & (12)(345) & 20 & 35 \end{matrix}

n = 6 \begin{matrix}i & π_{i} & μ_{i} & | Fix(π_{i}, D_{6})| \\ 1 & e & 1 & 7 828 354 \\ 2 & (12) & 15 & 160 948 \\ 3 & (123) & 40 & 3 490 \\ 4 & (1234) & 90 & 494 \\ 5 & (12)(34) & 45 & 24 302 \\ 6 & (12345) & 144 & 64 \\ 7 & (123456) & 120 & 44 \\ 8 & (12)(345) & 120 & 490 \\ 9 & (123)(456) & 40 & 562 \\ 10 & (12)(3456) & 90 & 324 \\ 11 & (12)(34)(56) & 15 & 860 \end{matrix} n = 7 \begin{matrix}i & π_{i} & μ_{i} & | Fix(π_{i}, D_{7})| \\ 1 & e & 1 & 2 414 682 040 998 \\ 2 & (12) & 15 & 2 208 001 624 \\ 3 & (123) & 40 & 2 068 224 \\ 4 & (1234) & 90 & 60 312 \\ 5 & (12345) & 144 & 1 548 \\ 6 & (123456) & 120 & 766 \\ 7 & (1234567) & 120 & 101 \\ 8 & (12)(34) & 45 & 67 922 470 \\ 9 & (12)(345) & 45 & 59 542 \\ 10 & (12)(3456) & 120 & 26 878 \\ 11 & (12)(34567) & 120 & 264 \\ 12 & (123)(456) & 120 & 69 264 \\ 13 & (123)(4567) & 120 & 294 \\ 14 & (12)(34)(56) & 15 & 12 015 832 860 \\ 15 & (12)(34)(567) & 15 & 10 192 \end{matrix}

18

n = 8 \begin{matrix}i & π_{i} & μ_{i} & | Fix(π_{i}, D_{8})| \\ 1 & e & 1 & 56 130 437 228 687 557 907 788 \\ 2 & (12) & 28 & 101 627 867 809 333 596 \\ 3 & (123) & 112 & 262 808 891 710 \\ 4 & (1234) & 420 & 424 234 996 \\ 5 & (12345) & 1344 & 531 708 \\ 6 & (123456) & 3366 & 144 320 \\ 7 & (1234567) & 5760 & 3 858 \\ 8 & (12345678) & 5040 & 2 364 \\ 9 & (12)(34) & 210 & 182 755 441 509 724 \\ 10 & (12)(345) & 1120 & 401 622 018 \\ 11 & (12)(3456) & 2520 & 93 994 196 \\ 12 & (12)(34567) & 4032 & 21 216 \\ 13 & (12)(345678) & 3360 & 70 096 \\ 14 & (123)(456) & 1120 & 535 426 780 \\ 15 & (123)(4567) & 3360 & 25 168 \\ 16 & (123)(45678) & 2688 & 870 \\ 17 & (1234)(5678) & 1260 & 3 211 276 \\ 18 & (12)(34)(56) & 420 & 7 377 670 895 900 \\ 19 & (12)(34)(567) & 1680 & 16 380 370 \\ 20 & (12)(34)(5678) & 1260 & 37 834 164 \\ 21 & (12)(345)(678) & 1120 & 3 607 596 \\ 22 & (12)(34)(56)(78) & 105 & 2 038 188 253 420 \end{matrix}

9 Known values of d_{n} and r_{n}

\begin{matrix}n & d_{n} & r_{n} \\ 0 & 2 & 2 \\ 1 & 3 & 3 \\ 2 & 6 & 5 \\ 3 & 20 & 10 \\ 4 & 168 & 30 \\ 5 & 7 581 & 210 \\ 6 & 7 828 354 & 16 353 \\ 7 & 2 414 682 040 998 & 490 013 148 \\ 8 & 56 130 437 228 687 557 907 788 & 1 392 195 548 889 993 358 \end{matrix}

These are sequences \underline{A000372} and \underline{A003182} in the On-Line Encyclopedia of Integer Sequences [12].

References

[1] V. Bakoev, One more way for counting monotone Boolean functions, in Thirteenth International Workshop on Algebraic and Combinatorial Coding Theory, Pomorie, Bulgaria (2012), pp. 47–52.

[2] F. a Campo, Relations between powers of Dedekind numbers and exponential sums related to them, J. Integer Sequences 21 (2018) Article 18.4.4.

[3] 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 https://arxiv.

org/abs/1407.4288, 2014.

[4] R. Church, Numerical analysis of certain free distributive structures, Duke Math. J. 6 (1940) 732–734.

[5] R. Church, Enumeration by rank of the elements of the free distributive lattice with 7 generators, Notices Amer. Math. Soc. 12 (1965) 724.

[6] R. Dedekind, Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler, Festschrift Hoch. Braunschweig u. ges. Werke II (1897) 103–148.

[7] R. Fidytek, A. W. Mostowski, R. Somla, and A. Szepietowski, Algorithms counting monotone Boolean functions, Inform. Process. Lett. 79 (2001), 203–209.

[8] C. C. Liu and S. B. Hu, A mechanical algorithm of equivalent classification for free distributive lattices, Chinese J. Comput. 3 (2) (1985), 128–135. In Chinese.

[9] C. C. Liu and S. B. Hu, A note on the problem of computing the number of equivalence classes of free distributive lattices, J. Wuhan Univ. Natur. Sci. Ed. (1986), no. 1, 13–17. In Chinese.

[10] G. E. Martin, Counting: The Art of Enumerative Combinatorics, Springer, 2001.

[11] B. Pawelski, On the number of inequivalent monotone Boolean functions of 8 variables, J. Integer Sequences 25 (2022), Article 22.7.7.

[12] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2022. Available

at https://oeis.org.

[13] T. Stephen and T. Yusun, Counting inequivalent monotone Boolean functions, Discrete Appl. Math., 167 (2014), 15–24.

[14] M. Ward, Note on the order of the free distributive lattice, Bull. Amer. Math. Soc. 52 (1946) 423.

[15] D. Wiedemann, A computation of the eighth Dedekind number, Order 8 (1991), 5–6.

2020 Mathematics Subject Classification: Primary 06E30. Keywords: monotone Boolean function, Dedekind number, equivalence class, fix.

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

Received May 8 2022; revised versions received September 19 2022; October 26 2022. Published in Journal of Integer Sequences, November 20 2022.

Return to Journal of Integer Sequences home page.