The number
of monotone Boolean functions of variables (equivalent to one more than the number of antichains
on the -set
) is called the th Dedkind number. For , 1, ..., is given by 2, 3, 6, 20, 168, 7581, 7828354, 2414682040998,
56130437228687557907788, 286386577668298411128469151667598498812366, ... (OEIS A000372).
The numbers and their discovers are summarized in the following table (Yusun 2011, Jäkel 2023). The last of these values was found by Jäkel (2023) using 5311 GPU-hours and 4257682565 matrix multiplications on Nvidia A100 GPUs.
Church, R. "Numerical Analysis of Certain Free Distributive Structures." Duke Math. J.6, 732-733, 1940.Dedekind,
R. "Über Zerlegungen von Zahlen durch ihre grössten gemeinsammen Teiler."
In Gesammelte Werke, Bd. 1. (Ed. K. May). Heidelberg, Germany: Mohr Siebeck,
pp. 103-148, 1897.Church, R. "Enumeration by Rank of the Elements
of the Free Distributive Lattice with Seven Generators." Not. Amer. Math.
Soc.12, 724, 1965.Jäkel, C. "A Computation of
the Ninth Dedekind Number." 3 Apr 2023. https://arxiv.org/abs/2304.00895.Sloane,
N. J. A. Sequence A000372/M0817
in "The On-Line Encyclopedia of Integer Sequences."Ward, M.
"Note on the Order of the Free Distributive Lattice." Bull. Amer. Math.
Soc.52, 423, 1946.Wiedemann, D. "A Computation of the
Eighth Dedekind Number." Order8, 5-6, 1991.Yusun,
T. J. L. "Dedekind Numbers and Related Sequences." M. S.
thesis. Burnaby, British Columbia, Canada: Simon Fraser University, 2011. https://summit.sfu.ca/item/12001.