The level polynomials of the free distributive lattices

Abstract

We show that there exist a set of polynomials {Lk{curly logical or}k = 0, 1⋯} such that Lk(n) is the number of elements of rank k in the free distributive lattice on n generators. L0(n) = L1(n) = 1 for all n and the degree of Lk is k-1 for k≥1. We show that the coefficients of the Lk can be calculated using another family of polynomials, Pj. We show how to calculate Lk for k = 1,...,16 and Pj for j = 0,...,10. These calculations are enough to determine the number of elements of each rank in the free distributive lattice on 5 generators a result first obtained by Church [2]. We also calculate the asymptotic behavior of the Lk's and Pj's. © 1980.