The th
Dedekind number
is the number of monotone Boolean functions of
variables, for a nonnegative
integer. Equivalently, it counts the antichains,
including the empty one, in the power set of an -element set ordered
by inclusion. For , 1, ..., is given by 2, 3, 6, 20, 168, 7581, 7828354, 2414682040998,
56130437228687557907788, 286386577668298411128469151667598498812366, ... (OEIS A000372).
The numbers and their discoverers 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.Church,
R. "Enumeration by Rank of the Elements of the Free Distributive Lattice with
Seven Generators." Not. Amer. Math. Soc.12, 724, 1965.Dedekind,
R. "Über Zerlegungen von Zahlen durch ihre grössten gemeinsamen Theiler."
In Festschrift der Technischen Hochschule zu Braunschweig bei Gelegenheit der
69. Versammlung Deutscher Naturforscher und Ärzte. Braunschweig, Germany:
Meyer, pp. 1-40, 1897. https://doi.org/10.1007/978-3-663-07224-9_1.
Reprinted in Gesammelte mathematische Werke, Bd. 2 (Ed. R. Fricke,
E. Noether, and Ø. Ore). Braunschweig, Germany: Vieweg, pp. 103-147,
1931. https://gdz.sub.uni-goettingen.de/id/PPN235693928.Jäkel,
C. "A Computation of the Ninth Dedekind Number." J. Comput. Algebra6-7,
100006, 2023. https://doi.org/10.1016/j.jaca.2023.100006.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." Master's thesis.
Burnaby, British Columbia, Canada: Simon Fraser University, 2011. https://summit.sfu.ca/item/12001.
th
Dedekind number 
is the number of monotone Boolean functions of
variables, for a nonnegative
integer 
. Equivalently, it counts the antichains,
including the empty one, in the power set of an 
-element set ordered
by inclusion. For 
, 1, ..., 
is given by 2, 3, 6, 20, 168, 7581, 7828354, 2414682040998,
56130437228687557907788, 286386577668298411128469151667598498812366, ... (OEIS A000372).
