Dedekind-getal

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)

In de wiskunde zijn Dedekind-getallen een snel stijgende rij vernoemd naar de Duitse wiskundige Richard Dedekind, die ze in 1897 definieerde. Het Dedekind-getal $M(n)$ telt het aantal monotone booleaanse functies met $n$ variabelen. Equivalent daarmee, telt het de antiketens van deelverzamelingen van een verzameling met $n$ elementen, het aantal elementen in een vrije distrubutieve tralie met $n$ generatoren.

Nauwkeurige asymptotische schattingen voor $M(n)$ en een exacte uitdrukking als een sommatie, zijn 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. Exacte waarden voor $M(n)$ zijn slechts bekend voor $n\leq 8.$

Waarden

De exacte waarden van de Dedekind-getallen zijn bekend voor $n=0,1,\ldots ,8:$

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788.

Bronnen, noten en/of referenties