The Level Polynomials of the Free Distributive Lattices

Author

George Markowsky, Missouri University of Science and TechnologyFollow

Abstract

We show that there exist a set of polynomials {L_k⋎k = 0, 1...} such that L_k(n) is the number of elements of rank k in the free distributive lattice on n generators. L₀(n) = L₁(n) = 1 for all n and the degree of L_k is k-1 for k⩾1. We show that the coefficients of the L_k can be calculated using another family of polynomials, P_j. We show how to calculate Lk for k = 1,...,16 and P_j 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 L_k's and P_j's.

Recommended Citation

G. Markowsky, "The Level Polynomials of the Free Distributive Lattices," Discrete Mathematics, vol. 29, no. 3, pp. 275 - 285, Elsevier, Apr 1980.

The definitive version is available at https://doi.org/10.1016/0012-365X(80)90156-9

Department(s)

Computer Science

International Standard Serial Number (ISSN)

0012-365X

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 1980 Elsevier, All rights reserved.

Publication Date

01 Apr 1980