Dedekind-getal

<imagemap> Bestand:Monotone Boolean functions 0,1,2,3.svg|400px|thumb|right| De vrije distributieve tralies van monotone Booleaanse functies met 0, 1, 2 en 3 argumenten, met respectievelijk 2, 3, 6 en 20 elementen (beweeg de muis over het rechter-diagramma om een beschrijving te zien)

circle 659 623 30 circle 658 552 35 circle 587 480 35 circle 659 481 35 circle 729 481 35 circle 588 410 35 circle 658 410 35 circle 729 410 35 circle 548 339 30 circle 604 339 30 circle 758 339 30 circle 661 339 35 circle 588 268 35 circle 659 267 35 circle 729 268 35 circle 588 197 35 circle 658 197 35 circle 729 197 35 circle 658 126 35 circle 659 56 30

desc bottom-left </imagemap>

In de wiskunde is het $n$-de dedekind-getal $M(n)$ het aantal monotone booleaanse functies met $n$ variabelen. De dedekind-getallen vormen een snel stijgende rij en zijn genoemd naar de Duitse wiskundige Richard Dedekind, die ze in 1897 definieerde. Een equivalente definitie is het aantal antiketens van deelverzamelingen van een verzameling met $n$ elementen of het aantal elementen in een vrije distributieve tralie met $n$ generatoren.

Exacte waarden voor $M(n)$ zijn tot 2023 slechts bekend voor $n\le 9$. Nauwkeurige asymptotische schattingen voor $M(n)$ en een exacte uitdrukking als een sommatie, zijn wel bekend. Het probleem van Dedekind om de waarden van $M(n)$ te berekenen, blijft daarentegen moeilijk: er is geen uitdrukking bekend voor $M(n)$ die het mogelijk maakt deze getallen te berekenen met een eindig aantal bewerkingen.

De complexiteit van het algoritme neemt dubbelexponentieel toe. Computertechnologie groeit slechts exponentieel. Het duurde 32 jaar om $M(9)$ – een getal van slechts (!) 42 cijfers – exact te berekenen; het vergt niet alleen een supercomputer maar een steeds complexer algoritme. Vermoedelijk zou $M(10)$ pas worden gevonden tegen 2044.

Waarden

De exacte waarden van de dedekind-getallen voor $n=0,1,\dots ,9$ zijn:

• 2
• 3
• 6
• 20
• 168
• 7581
• 7828354
• 2414682040998
• 56130437228687557907788
• 286386577668298411128469151667598498812366