Estimates on the number of partially ordered sets

arXiv1307.1886MaRDI QIDQ6243178FDOQ6243178

Publication date: 7 July 2013

Abstract: Partially ordered sets of type (k, n) are the sets such that a) cardinality of each set is n, b) dimension of each set is two, c) length of the maximal antichain in each set is k. Let alpha_k(n) be the number of partially ordered sets of type (k, n). We prove that alpha_k(n)<min{k^{2n}/((k!)^2), (n-k+1)^{2n}/(((n-k)!)^2)}. Denote by xi_k(n) the number of permutations from S_n such that the maximal decreasing chain of such permutation has length k. We prove that xi_k(n)<k^{2n}/(((k-1)!)^2). We survey connections among the pairs of linear orders, the pairs Young diagrams, two-dimensional arrays of positive integers and matrices of nonnegative integers. This survey is based on papers of Schensted and Knuth. We show the generating function of xi_k(n). It was obtained by Gessen in 1990.

This page was built for publication: Estimates on the number of partially ordered sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6243178)