Dedekind-getal

In de wiskunde is het ${\displaystyle n}$-de dedekind-getal ${\displaystyle M(n)}$ het aantal monotone booleaanse functies met ${\displaystyle 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 ${\displaystyle n}$ elementen of het aantal elementen in een vrije distributieve tralie met ${\displaystyle n}$ generatoren.

Exacte waarden voor ${\displaystyle M(n)}$ zijn tot 2023 slechts bekend voor ${\displaystyle n\leq 9}$. Nauwkeurige asymptotische schattingen voor ${\displaystyle M(n)}$ en een exacte uitdrukking als een sommatie, zijn wel bekend. Het probleem van Dedekind om de waarden van ${\displaystyle M(n)}$ te berekenen, blijft daarentegen moeilijk: er is geen uitdrukking bekend voor ${\displaystyle 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 ${\displaystyle M(9)}$ – een getal van slechts (!) 42 cijfers – exact te berekenen; het vergt niet alleen een supercomputer maar een steeds complexer algoritme.^[1] Vermoedelijk zou ${\displaystyle M(10)}$ pas worden gevonden tegen 2044.

De exacte waarden van de dedekind-getallen voor ${\displaystyle n=0,1,\ldots ,9}$ zijn:^[2]

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