Details
| Original language | English |
|---|---|
| Pages (from-to) | 49-60 |
| Number of pages | 12 |
| Journal | Discrete mathematics |
| Volume | 105 |
| Issue number | 1-3 |
| Publication status | Published - 14 Aug 1992 |
Abstract
Let pkn denote the number of unlabeled posets with n points and k unrelated pairs. We show that for k<n, these numbers satisfy a recursion formula of the form Pkn = Σkj=0 cjpk- j,n-j-1, where the coefficients cj can be computed if the numbers qjm of all ordinally indecomposable posets with m points and j unrelated pairs are known for m - 1≤j≤k. The crucial lemma for the proof states that qjm=0 for j<m- 1. From the recursion formula it follows that pkn is a polynomial of degree k in the variable n and that Pkn≥ n-1 k with asymptotic equality for fixed k. For small values of k, we determine these polynomials explicitly. At the other end of the scale, we find that qn-1,n = 2n-3 for n≥3. Similar results are obtained for the number of labeled posets with a fixed linear extension and a given number of unrelated pairs.
ASJC Scopus subject areas
- Mathematics(all)
- Theoretical Computer Science
- Mathematics(all)
- Discrete Mathematics and Combinatorics
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: Discrete mathematics, Vol. 105, No. 1-3, 14.08.1992, p. 49-60.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - The number of partially ordered sets with more points than incomparable pairs
AU - Erné, Marcel
PY - 1992/8/14
Y1 - 1992/8/14
N2 - Let pkn denote the number of unlabeled posets with n points and k unrelated pairs. We show that for kkn = Σkj=0 cjpk- j,n-j-1, where the coefficients cj can be computed if the numbers qjm of all ordinally indecomposable posets with m points and j unrelated pairs are known for m - 1≤j≤k. The crucial lemma for the proof states that qjm=0 for jkn is a polynomial of degree k in the variable n and that Pkn≥ n-1 k with asymptotic equality for fixed k. For small values of k, we determine these polynomials explicitly. At the other end of the scale, we find that qn-1,n = 2n-3 for n≥3. Similar results are obtained for the number of labeled posets with a fixed linear extension and a given number of unrelated pairs.
AB - Let pkn denote the number of unlabeled posets with n points and k unrelated pairs. We show that for kkn = Σkj=0 cjpk- j,n-j-1, where the coefficients cj can be computed if the numbers qjm of all ordinally indecomposable posets with m points and j unrelated pairs are known for m - 1≤j≤k. The crucial lemma for the proof states that qjm=0 for jkn is a polynomial of degree k in the variable n and that Pkn≥ n-1 k with asymptotic equality for fixed k. For small values of k, we determine these polynomials explicitly. At the other end of the scale, we find that qn-1,n = 2n-3 for n≥3. Similar results are obtained for the number of labeled posets with a fixed linear extension and a given number of unrelated pairs.
UR - http://www.scopus.com/inward/record.url?scp=4043150936&partnerID=8YFLogxK
U2 - 10.1016/0012-365X(92)90131-X
DO - 10.1016/0012-365X(92)90131-X
M3 - Article
AN - SCOPUS:4043150936
VL - 105
SP - 49
EP - 60
JO - Discrete mathematics
JF - Discrete mathematics
SN - 0012-365X
IS - 1-3
ER -