Counting Self-Dual Monotone Boolean Functions
Bartłomiej Pawelski and Andrzej Szepietowski
Institute of Informatics
University of Gdańsk
80-952 Gdańsk
Poland
Abstract:
Let Dn denote the set of monotone Boolean functions
with n variables. The cardinality of Dn,
denoted by dn, is known as the n-th Dedekind
number. Elements of Dn can be represented as strings
of bits of length 2n. For each f ∈ Dn,
we have the dual function f* ∈
Dn
which is obtained by reversing and negating all bits. An element
f ∈ Dn is self-dual if
f = f*. Let
Λn denote the set of all self-dual monotone Boolean
functions of n variables and let λn denote
|Λn|. There is a natural action of the permutation
group Sn
on the set of Boolean functions by permutation of
variables. The sets Dn and Λn
are closed under this action. We let
Rn
and
Qn
denote the sets of all equivalence classes in Dn
and Λn, respectively. In this paper, we derive
several algorithms for counting self-dual monotone Boolean
functions and confirm the known result that λ9 equals
423,295,099,074,735,261,880.
Furthermore, we calculate |Q8| to be
6,001,501.
Full version: pdf,
ps,
latex
(Concerned with sequences
A001206
A008840.)
Received February 26 2024; revised versions received December 11 2024; June 12 2025;
October 22 2025.
Published in Journal of Integer Sequences,
October 31 2025.
Return to
Journal of Integer Sequences home page