On the number of distributive lattices

Marcel Erné ; Jobst Heitzig ; Jürgen Reinhold

The electronic journal of combinatorics, Tome 9 (2002)

Résumé

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.

Détail

DOI : 10.37236/1641

Classification : 05A15, 06D05, 05A16, 06A07
Mots-clés : canonical poset, ordinal (vertical) decomposition, combinatorial identities, distributive lattices, indecomposable posets