Details
| Originalsprache | Englisch |
|---|---|
| Seiten (von - bis) | 49-60 |
| Seitenumfang | 12 |
| Fachzeitschrift | Discrete mathematics |
| Jahrgang | 105 |
| Ausgabenummer | 1-3 |
| Publikationsstatus | Veröffentlicht - 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 Sachgebiete
- Mathematik (insg.)
- Theoretische Informatik
- Mathematik (insg.)
- Diskrete Mathematik und Kombinatorik
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
in: Discrete mathematics, Jahrgang 105, Nr. 1-3, 14.08.1992, S. 49-60.
Publikation: Beitrag in Fachzeitschrift › Artikel › Forschung › 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 -