Dedekind number
E634841
A Dedekind number is the count of distinct monotone Boolean functions (or equivalently, antichains) on an n-element set, forming a rapidly growing sequence studied in combinatorics and lattice theory.
Statements (47)
| Predicate | Object |
|---|---|
| instanceOf |
combinatorial invariant
ⓘ
integer sequence ⓘ mathematical concept ⓘ |
| alternativeName | Dedekind’s problem sequence NERFINISHED ⓘ |
| appearsIn |
enumerative combinatorics
ⓘ
theory of partially ordered sets ⓘ |
| computationalComplexity | exact computation is extremely difficult for large n ⓘ |
| counts | number of monotone Boolean functions f : {0,1}^n → {0,1} ⓘ |
| describes |
number of antichains of subsets of an n-element set
ⓘ
number of monotone Boolean functions on an n-element set ⓘ |
| equivalentDescription |
number of antichains in the power set of an n-element set ordered by inclusion
ⓘ
number of order ideals of the Boolean lattice B_n ⓘ |
| equivalentDescription | number of monotone subsets of {0,1}^n under product order ⓘ |
| field |
Boolean function theory
ⓘ
combinatorics ⓘ lattice theory ⓘ |
| firstTerms |
M(0) = 2
ⓘ
M(1) = 3 ⓘ M(2) = 6 ⓘ M(3) = 20 ⓘ M(4) = 168 ⓘ M(5) = 7581 ⓘ M(6) = 7828353 ⓘ M(7) = 2414682040996 ⓘ |
| growthRate | super-exponential ⓘ |
| hasLowerBound | 2^(binomial(n,⌊n/2⌋)) ⓘ |
| hasUpperBound | 2^(binomial(n,⌊n/2⌋)(1+o(1))) ⓘ |
| historicalNote | introduced in the 19th century by Richard Dedekind in work on lattices and logic ⓘ |
| namedAfter | Richard Dedekind NERFINISHED ⓘ |
| OEISID | A000372 ⓘ |
| openProblem |
asymptotic behavior is only partially understood
ⓘ
exact formula for general n is unknown ⓘ |
| property |
sequence is strictly increasing in n
ⓘ
values are known only for small n ⓘ |
| relatedConcept |
Bell number
ⓘ
Boolean algebra ⓘ Sperner’s theorem NERFINISHED ⓘ |
| relatedTo |
Boolean lattice
ⓘ
Sperner family ⓘ antichain ⓘ distributive lattice ⓘ monotone Boolean function ⓘ |
| sequenceNotation |
D(n)
ⓘ
M(n) ⓘ |
| usedIn |
enumeration of closure systems
ⓘ
study of free distributive lattices ⓘ theory of monotone Boolean circuits ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.