On the Number of Distributive Lattices
Open Access
- 1 January 2002
- journal article
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 9 (1) , R24
Abstract
We investigate the numbers $d_k$ of all (isomorphism classes of) distributive lattices with $k$ elements, or, equivalently, of (unlabeled) posets with $k$ antichains. Closely related and useful for combinatorial identities and inequalities are the numbers $v_k$ of vertically indecomposable distributive lattices of size $k$. We present the explicit values of the numbers $d_k$ and $v_k$ for $k < 50$ and prove the following exponential bounds: $$ 1.67^k < v_k < 2.33^k\;\;\; {\rm and}\;\;\; 1.84^k < d_k < 2.39^k\;(k\ge k_0).$$ Important tools are (i) an algorithm coding all unlabeled distributive lattices of height $n$ and size $k$ by certain integer sequences $0=z_1\le\cdots\le z_n\le k-2$, and (ii) a "canonical 2-decomposition" of ordinally indecomposable posets into "2-indecomposable" canonical summands.
Keywords
This publication has 5 references indexed in Scilit:
- Counting Finite LatticesAlgebra universalis, 2002
- The Number of Unlabeled Orders on Fourteen ElementsOrder, 2000
- The number of partially ordered sets with more points than incomparable pairsDiscrete Mathematics, 1992
- On the cardinalities of finite topologies and the number of antichains in partially ordered setsDiscrete Mathematics, 1981
- A Simple Solution to the Word Problem for LatticesCanadian Mathematical Bulletin, 1970