On the Number of Distributive Lattices

Marcel Erné, Jobst Heitzig, Jürgen Reinhold

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.


Full Text: PDF